[解決済み】C++でHashMapを使用する最良の方法は何ですか？

質問

STLにHashMap APIがあることは知っていますが、これに関する良い例と完全なドキュメントを見つけることができません。

何か良い例があれば教えてください。

どのように解決するのですか？

標準ライブラリには、順序付きマップと非順序付きマップ ( std::map と std::unordered_map ) コンテナです。順序付きマップでは、要素はキーでソートされ、挿入とアクセスは O(log n) . 通常、標準ライブラリは内部で 赤黒い木 は、順序付きマップのためのものです。しかし、これは実装の細部に過ぎない。非順序型マップでは、挿入とアクセスはO(1)である。これは、ハッシュテーブルの別名に過ぎない。

(順序付き)での例 std::map :

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

出力します。

23
キー：hello 値：23

もしコンテナ内で順序付けが必要で、O(log n) の実行時間でも構わないのであれば、単に std::map .

その他、本当にハッシュテーブル（O(1)挿入/アクセス）が必要な場合は、以下をチェックしてください。 std::unordered_map と同じような機能を持つ std::map API（例：上記の例では、検索と置換を行うだけです。 map で unordered_map ).

は、その unordered_map コンテナが導入されました。 C++11標準 のリビジョンです。したがって、コンパイラによっては、C++11の機能を有効にする必要があります（たとえば、GCC 4.8を使う場合、C++11に対応するために -std=c++11 をCXXFLAGSに追加してください)。

C++11のリリース以前からGCCは unordered_map - を名前空間 std::tr1 . したがって、古いGCCコンパイラでは、次のように使ってみることができます。

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

また、boostの一部であり、すなわち、対応する ブーストヘッダー を使用すると、移植性が向上します。