3

我有这个简单的代码：

std::vector<std::map<double,double>> v;
//populate v

//we know each map already has correct key order (enforced by c++)
//but i also want to make sure the different maps have correct key order
//this is how I do it using a pointer:

const double *last_key = nullptr;
for (const auto &map : v)
{
  if (map.size() > 0) //ignore empty maps
  {
    if (last_key)
    {
      const auto &new_key = map.cbegin()->first;
      if (!(*last_key < new_key))
        throw std::runtime_error("invalid key order");
    }
    last_key = &(--map.cend())->first;
  }
}

这对指针有用吗？你会怎么做呢？

我知道的唯一真正的选择（如果我想避免使用指针）是这样做：

double last_key;
bool last_key_has_been_set = false;

这可行，但它要求密钥是默认可构造的，并且涉及不必要的密钥复制（与 不同的密钥类型的问题double）。

4

4 回答 4

2

好的，因为我现在（想我）理解你的代码是关于什么的，这是我的看法：

auto iter = v.begin();
auto end = v.end();
while (iter != end && iter->empty())
  ++iter;
if (iter != end)
{
  while (true) // loop and a half
  {
    auto next = iter+1; // at this point, we know iter != end
    while (next != end && next->empty())
      ++next;
    if (next == end)
      break;
    auto lhslast = lhs.end();
    --lhslast;
    if (lhslast->first > next->begin()->first)
      throw std::runtime_error("invalid key order");
    iter = next;
  }
}

编辑：

上面的代码可以使用另一种算法进一步改进：

代替

while (iter != end && iter->empty())
  ++iter;

和

iter = std::find_if(iter, end,
                    [](std::map<double, double> const& m) { return m.empty(); });

和next循环类似。

另一种选择是注意，如果它不是空地图，您可以只使用adjacent_find. 因此，另一种选择是利用 Boostfilter_iterator来摆脱空地图。这样做

#include <boost/iterator/filter_iterator.hpp>

struct is_not_empty
{
  template<typename Container> bool operator()(Container const& c) const
  {
    return !c.empty();
  }
};

然后在你的代码的地方

auto fbegin = boost::make_filter_iterator(is_not_empty(), v.begin(), v.end());
auto fend =  boost::make_filter_iterator(is_not_empty(), v.end(), v.end());

if (std::adjacent_find(fbegin, fend,
                       [](std::map<double, double> const& lhs,
                          std::map<double, double> const& rhs) -> bool
                       {
                         auto lhslast = lhs.end();
                         --lhslast;
                         return lhslast->first > rhs.begin()->first;
                       }) != fend)
  throw std::runtime_error("invalid key order");

过滤器迭代器确保只考虑非空映射。

于 2013-06-29T11:49:46.820 回答
1

我认为标准库中没有合适的预定义算法可以做到这一点。特别是，如果您要为它定义一个相对复杂和有状态的谓词，则std::adjacent_find 可以使用它，但这实际上等于误std::adjacent_find用.std::for_eachstd::adjacent_find

但是，您应该使用迭代器，而不是裸指针。我还建议将检查代码放入一个单独的函数中，也许命名为check. 这是我的建议：

#include <vector>
#include <map>
#include <iostream>

bool check(const std::vector<std::map<double,double>> &v)
{
  /* Fast-forward to the first non-empty entry. */
  auto it = begin(v);
  for( ; it != end(v) ; ++it)
    if (!it->empty())
      break;

  /* We might be done by now. */
  if (it == end(v))
    return true;

  /* Else, go through the remaining entries,
     skipping empty maps. */
  auto prev = it->end();
  advance(prev,-1);
  ++it;

  for ( ; it != end(v) ; ++it)
    {
      if (!it->empty())
        {
          if (it->begin()->first < prev->first)
            return false;
          prev = it->end();
          advance(prev,-1);
        }
    }

  return true;
}

int main()
{
  std::vector<std::map<double,double>> v;

  /* Two entries for the vector, invalid order. */    
  v.push_back({ {1.0,1.0} , {2.0,4.0} });
  v.push_back({ {3.0,9.0} , {1.0,16.0} });

  if (!check(v))
    throw std::runtime_error("Invalid order of the maps in the vector.");

  return 0;
}

注意：check如果将函数定义为采用一系列迭代器的算法，而不是对容器的引用，那么它会更像 C++（或者，至少更像标准库中的算法） ，如争论。重写函数以匹配这个概念是直截了当的。

注意 2：使用迭代器而不是裸指针的优点是您可以更好、更清晰地抽象出您需要的东西：引用映射中的项目的东西，而double*指针可能指向各种东西。然而，使用迭代器也有一个缺点：如果你要修改你的算法，使它在迭代向量时改变映射，迭代器可能会失效，而指针不会（除非你删除它指向的元素） . （不过，如果您更改向量，指针可能会失效。）

但只要检查过程仅用于检查而不是其他用途（我的代码通过将代码放入专用于此目的的单独函数中，并将向量作为常量引用来表明这一点），迭代器失效不是问题。

于 2013-06-29T11:54:28.093 回答
0

最佳注释给出了答案：使用adjacent_find.

首先一点逻辑。如果有 n < m 个索引验证 key[n] > key[m]，则存在索引 i，n <= i < m 其中 key[i] > key[i+i]。

你可以用荒谬的推理来证明这一点：如果没有这样的 i，那么对于 n 和 m 之间的所有 i，我们都有顺序，并且因为顺序关系是传递的，key[n] <= key[m] ：荒谬。这意味着，忽略空映射，如果您的键顺序错误，那么您有两个相邻的键顺序错误。

所以你的算法应该是：

typedef map<double, double> map_t;
vector<map_t> v;
remove_if(v.begin(), v.end(), [](map_t const& m){return m.empty();});
if(adjacent_find(v.begin(), v.end(), [](map_t const& l, map_t const& r)
    {
        return (--l.cend())->first > r.cbegin()->first;
    }) != v.end())
    throw std::runtime_error("invalid key order");

当然，这是如果您可以先从矢量中删除空地图。（我们可以假设，因为空地图可能没有那么有意义，但这肯定取决于整体情况）。

于 2013-06-29T12:05:48.617 回答
0

这使用了 C++1y 特性 ( std::tr2::optional)，但应该适用于任何容器以及容器元素的任何排序：

struct compare_key_order {
  template<typename LHS, typename RHS>
  bool operator()( LHS const& lhs, RHS const& rhs ) {
    return lhs.first < rhs.first;
  }
};

template<typename ContainerOfContainers, typename Ordering>
bool are_container_endpoints_ordered( ContainerOfMaps&& meta, Ordering&& order=compare_key_order()  )
{
  using std::begin; using std::end;

  // or boost::optional:
  std::tr2::optional< decltype( begin(begin(meta)) ) > last_valid;

  for( auto&& Map : std::forward<Meta>(meta) ) {
    auto b = begin(Map);
    auto e = end(Map);
    if (b==e)
      continue;
    if (last_valid)
      if (!order( **last_valid, *b ))
        return false;
    last_valid = e;
  }
  return true;
}

optional是一种处理“这个元素可能存在也可能不存在”的更漂亮、更不容易出错的方式，而不是指针可以是nullptr。如果您正在使用boost或可以访问 a std::tr2::optional（或者您将来正在阅读此内容，如果std::optional存在），那么它比指针更好。

您还可以将“是否存在last_valid状态异常并进入程序代码位置：

struct compare_key_order {
  template<typename LHS, typename RHS>
  bool operator()( LHS const& lhs, RHS const& rhs ) {
    return lhs.first < rhs.first;
  }
};

template<typename ContainerOfContainers, typename Ordering>
bool are_container_endpoints_ordered( ContainerOfMaps&& meta, Ordering&& order=compare_key_order()  )
{
  using std::begin; using std::end;

  auto it = begin(meta);
  while( it != end(meta) && (begin(*it) == end(*it)) {
    ++it;
  }
  if ( it == end(meta) )
    return true;
  auto last_valid_end = end(*it);
  for( ++it; it != end(meta); ++it ) {
    auto b = begin(*it);
    auto e = end(*it);
    if (b==e)
      continue;
    if (!order( *last_valid_end, *b ))
      return false;
    last_valid = e;
  }
  return true;
}

这将使相同的算法在vectors-of-vectors-of-pairs上运行，或者甚至检查vector-of-vectors是否具有排序的端点（具有不同的order）。

于 2013-06-29T12:49:04.130 回答