c++ - std::mapで双方向イテレータのインデックスを取得するには?

Question

std::vector のイテレータのインデックスを取得する最も効果的な方法は何ですか? std::vectororの方法を説明しますstd::listが、どうstd::mapですか?

Answer 1

これを行う最もクリーンな方法は、次のstd::distance関数を使用することです。

auto index = std::distance(myMap.begin(), myMapItr);

ただし、これは O(n) 時間で実行されるため、大規模なマップでは非効率的です。

マップまたはその他の順序付きコレクションへの反復子のインデックスを決定する必要がある場合は、効率的な (O(1) または O( log n)) ツリー内の特定の値のインデックスの時間ルックアップ。

または、ツリーを手動で反復処理している場合は、ある要素から次の要素にトラバースするたびにインクリメントする反復子の横にカウンターを配置しておくことができます。これにより、反復子のインデックスの O(1) 時間ルックアップが得られますが、完全に一般的ではありません。

お役に立てれば！