2

我的问题如下：

在 std::map 上使用 find 以获取指向所需元素对的迭代器后，是否可以在后续 find() 上重用该迭代器以利用知道我之后查找的元素接近第一个发现元素？就像是：

std::map<key, value> map_elements;
std::map<key, value>::iterator it;

it = map_elements.find(some_key);
it = it.find(a_close_key)

先感谢您

4

2 回答 2

3

如果您确定它真的就在附近，您可以使用std::find（而不是map::find）对该项目进行线性搜索。如果它在当前位置的大约 log(N) 个项目内，这很可能是一场胜利（其中 N 是地图中的项目数）。

另请注意，您必须确定是否要在当前位置之前或之后进行搜索，并指定current，end()是否在之后，以及begin(), current是否在之前。如果是之前，您将需要进行反向搜索（find_end如果没有记错的话），因为目标可能接近该范围的末尾。

于 2013-07-21T04:35:05.460 回答
1

关于 Item1（由 map::find 找到）与 Item2 的距离，您的问题并不完整。在某些情况下，制作新的更有效map::find；在某些情况下，您可以迭代您的迭代器以找到您的第二个项目可以在哪里。仅使用搜索map::find将是 O(log n) 复杂度，大约需要 10-20 步。

所以，如果你知道你的 Item2 还没有那么远，你可以迭代it迭代器来找出它。这里最重要的是如何检查您必须停止搜索。std::map默认情况下用于std::less<T>排列项目，因此可用于找出容器根本不包含 Item2。像这样的东西（未测试）：

std::map<key, value> map_elements;
std::map<key, value>::iterator it, it2;

it2 = it = map_elements.find(some_key);
bool found=false;
while( it2!=map_elements.end() && !(a_close_key < it2->first) ) {
   if( !(a_close_key < it2->first) && !(it2->first < a_close_key) ) {
      //Equivalency is not ==, but its what used in std::map
      found=true;
      break;
   }
   it2++;
}
if( found ) {
   //.... use it2
}

在if( found )块内部，您的迭代器it2值应该与您调用时相同map_elements.lower_bound(a_close_key)

于 2013-07-21T04:56:09.970 回答