C++映射从迭代器位置开始搜索

Question

我的问题如下：

在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)

提前感谢

Answer 1

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

还要注意，您必须弄清楚是要在当前位置之前还是之后进行搜索，并指定current、end()（如果在之后）和begin(), current（如果在之前）。如果是以前的，您将希望进行反向搜索（如果内存可用，则为find_end），因为目标可能接近该范围的末尾。

Answer 2

关于Item1（通过map:：find找到）离Item2有多远的问题还不完整。在某些情况下，制作新的map::find更有效；在某些情况下，你可以迭代迭代器来找到第二个项目的位置。只需搜索map::find，它的复杂性为O（logn），大约需要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) 时相同