11

これに関する情報が見つからないようなので、stackoverflow を参照します。C++のstd::tr1::unordered_mapの反復子はどのくらい効率的ですか? 特に、たとえばリスト イテレータと比較すると。効率的な反復を可能にするために、リスト内のすべてのキーも保持するラッパー クラスを作成することは理にかなっていますか (私のコードでは、unordered_map 内のキーに対して多くの反復を使用しています)。ブーストをお勧めする人には、（何らかの理由で）使用できません。

4

4 に答える 4

9

TR1 はチェックしていませんが、N3035 (C++0x ドラフト) には次のように書かれています。

イテレータのすべてのカテゴリは、特定のカテゴリに対して一定時間 (償却) で実現可能な関数のみを必要とします。したがって、反復子の要件テーブルには複雑さの列がありません。

標準は、複雑さ以外の効率性を保証するものではないため、listとの比較は、unordered_map両方とも償却された定数時間 (つまり、コンテナーの完全な反復の線形時間) であることを除いて保証されていません。

実際には、ハッシュマップが非常にまばらに入力されていない限り、unordered_mapイテレータは少なくとも の近くにあると予想されます。完全な反復の複雑さには、O (バケット数) 項が含まれる場合があります。しかし、特に C++ 向けの実装を 1 つも見たことがないので、単純な「リンクされたリストの配列」ハッシュテーブルの実装でどのような装飾が期待できるかわかりません。「典型的な」プラットフォームでテストする場合、すべての C++ 実装で間違いなく最速のコードを書こうとしている場合は、運が悪く、できません ;-)listunordered_map

于 2010-03-23T12:37:41.373 に答える
5

残念ながら、何かを試して結果を測定しない限り、何かが十分に効率的であるかどうかはわかりません。標準ライブラリ、TR1、Boost クラスには多くの注目が集まっていると言えます。おそらく、ほとんどの一般的なユースケースで得られるのと同じくらい高速です。コンテナーのウォークは、確か​​に一般的なユース ケースです。

以上のことから、いくつかの質問を自問する必要があります。

  1. 自分の言いたいことを最も明確に伝える方法は何ですか? ラッパー クラスを作成すると、コードが不要に複雑になる場合があります。 最初に正しくしてから、速くします。

  2. listを と並行して維持するための余分なメモリと時間を確保できますunordered_mapか?

  3. 本当にunordered_map正しいデータ構造ですか? 最も一般的なユース ケースが最初から最後までトラバーサルである場合はvector、メモリが連続していることが保証されているため、使用したほうがよい場合があります。

于 2010-03-23T13:02:36.617 に答える
5

unordered_map イテレーターは基本的に、ハッシュテーブルの内部ツリー構造をたどる必要があります。これは、ポインタをたどることを意味するだけなので、かなり効率的です。もちろん、unordered_map を頻繁に使用している場合は、そもそも間違ったデータ構造を使用している可能性があります。いずれにせよ、これに対する答えは、すべてのパフォーマンスの問題と同様に、特定のコードの時間を計って、それが十分に高速かどうかを確認することです。

于 2010-03-23T12:27:23.260 に答える
2

ここのベンチマークで回答https://stackoverflow.com/a/25027750/1085128 unordered_map は、ベクターと反復のためのマップの中間にあります。マップよりもはるかに高速です。

于 2016-03-12T00:24:51.663 に答える