1

我正在尝试C++ map通过使用upper_bound函数来优化我的搜索： The mapis the variable 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
            }
        }
   }

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

4

1 回答 1

2

你的循环条件

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.

于 2013-02-28T04:38:22.313 回答