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

1

Item1 (map::find で検出) が Item2 からどれだけ離れているかについての質問は完全ではありません。場合によっては、 new を作成する方が効率的map::findです。場合によっては、イテレータを繰り返し処理して、2 番目の項目がどこにあるかを見つけることができます。検索だけを使用map::findすると、O（log n）の複雑さになり、約10〜20ステップになる可能性があります。

したがって、 Item2 がそれほど遠くないことがわかっている場合は、ititerator を反復して見つけることができます。ここで最も重要なことは、検索を停止する必要があることを確認する方法です。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 に答える