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 に答える