c++ - 使用上限和下限在 C++ 映射中找到正确的条目

Question

我正在尝试使用 upper_bound 函数优化我在 C++ map 中的搜索: map 是变量 table:

Foo& search(uint64 id, uint64 hash) {

   std::map<std::pair<uint64, uint64>, Foo>::const_iterator iter;

   std::pair<uint64, uint64> key(id, hash);
   iter = table.upper_bound(key);
   // for completeness I search for those elements which may be a match
   // they may fall into a different hash range

   for( ; iter != table.end() || iter != table.begin(); --iter ) {
         const Foo foo = iter->second;
         if(foo.id() == foo.first_hash() <= hash &&
            hash <= foo.second_hash()) {
            if( foo.state() == NORMAL) {
                   return foo;
            }
            else {
            // do something else
            }
        }
   }

但是，当我执行程序时它只是挂起...看起来搜索根本不起作用，而且我没有日志告诉我错误在哪里...我做错了什么这里？当我进行线性搜索时，它工作正常，但现在当我尝试改进算法时它失败了......

Answer 1

你的循环条件

for( ; iter != table.end() || iter != table.begin(); --iter )

是无限循环的来源，因为它始终为真。

从评论来看，你想做的是使用反向迭代器:

   map<int,int> a;
   for (int i = 0; i < 100; i++) {
      a[i] = 2*i;
   }
   auto it = a.upper_bound(5);
   reverse_iterator<map<int,int>::iterator> rev_it (it);
   for (; rev_it != a.rend(); rev_it++) {
      cout << rev_it->first;
   }

这将打印 543210。