キーの参照に関するstd :: mapの動作

Question

std :: mapを使用して数値シミュレーション用のプログラムを作成して、いくつかのキーと値のペアを格納しています。このマップは、シミュレーション中に発生した状態を保存するために使用されます。キーのタイプは整数であり、キーに対応する値は同じキーに対していくつのコピーが存在するか、すなわちstd :: mapを指示する。シミュレーションの各ステップについて、私は同じキーのためにそこにあるどのように多くの値を計算する必要があるので、私は次のコード

if (map[key]>0) {do something here with the number of copies} 

によりしかし、私はすぐにこのコードがあるために動作しないことが判明することを確認しますそのようなキーがマップに存在しない場合でも、[key]マップを呼び出すたびに、そのキーのプレースホルダが生成され、その値がゼロに設定されます。したがって、私は常にstd :: map.size（）でキーの総数をオーバーカウントします。代わりに

if (map.find(key)!=map.end()) {...} 

キーを検索するために従うように私は後でだから、キーがマップに存在するかどうかをチェックするための唯一かつ最速の方法ですコードを変更しますか？私は数百万回もシミュレーションを実行するつもりですし、キーをチェックするために非常に頻繁にコードを呼び出すでしょう。代わりにmap.find（）を使用するのが遅すぎますか？ありがとう。

Answer 1

std::mapまたはハッシュテーブル（std::unordered_map）では、find関数は、[]添え字演算子を使用するのと同じくらい高速です。実際には、エレメントを挿入する必要がないため、エレメントが見つからない場合は速くなります。

Answer 2

findメンバー関数はおそらく、キーがすでにマップ内にあるかどうかを調べる最速の方法です。つまり、マップ内の項目を順番に処理する必要がない場合は、代わりにstd::unordered_mapを使用するとパフォーマンスが向上する可能性があります。

Answer 3

キーの存在を確認する方法は、速度に大きな違いがあるとは思いません。一方、あなたのキーが整数であり、範囲がわかっているならば、配列を使うだけかもしれません。

BTW： 私は単純な配列、ベクトル、マップ、および順序付けられていないマップの速度に興味がありました。

• 配列：1.27s
• ベクター：1.36s
Iは、nは0〜10000の結果の範囲内の乱数である100000000コンテナ[N] ++を行い、簡単なプログラムを書かれています
• 順序付けられていないマップ：2.6s
• map：11.6s この単純なケースでのループ+インデックス計算のオーバーヘッドは〜0.8sです。

したがって、どれくらいの時間が他の場所で費やされているかによって異なります。かなり多くの場合（100000000回の繰り返し）、それはあなたが使用するものはそれほど重要ではありません。しかし、そうでなければ、それはかなり異なることがあります。

Answer 4

hash_mapを使用すると、キー値タイプの中で最も速いデータ構造です。

マップを使用することもできますが、hash_mapよりも遅い