C++ で HashMap を使用する

C++ でハッシュマップを使うには std::unordered_map を使用します。std::map は、キーを順序付けて保持する関連するキーと値のコンテナです。どちらも連想コンテナであり、各キーは一意で、対応する値を識別します。異なるキーが同じ値を持つことはできます。キーによる検索が必要な場合はどちらも使えます。順序どおりの走査が必要かどうかで選びましょう。

標準規格は std::map の具体的な内部実装を定めていません。外から見える順序はキーの比較方法に従い、既定の比較関数では昇順になります。一方、std::unordered_map はハッシュ関数とバケットを使い、反復順序は規定されていません。ある実行でたまたま見えた順序に依存しないでください。

C++ のハッシュマップの仕組み

<map> または <unordered_map> をインクルードし、キーと値の型を宣言します。たとえば std::map<int, std::string> のように指定します。insert はキーがまだ存在しない場合にのみキーと値の組を追加します。operator[] による代入では、必要に応じて値初期化された値を挿入してから代入します。int などのスカラー型では、値初期化によって代入前にゼロになります。既存のキーに代入すると、その値が更新され、重複キーは作られません。値を使う前にキーの有無を確認したい場合は find を使います。at でもキーを検索できますが、キーが見つからない場合は std::out_of_range を報告します。

提供された実行記録では、元の例がどちらも正常に実行されています。以下の std::map の出力は記録された出力です。後半の非順序コンテナの例には走査ループが追加されているため、変更後の例について特定の出力順序は示していません。

順序付きキーには std::map を使う

キーを比較関数の順序で走査したい場合や、指定した値以上の最初のキーを見つけるなどの順序付き操作が必要な場合は、std::map を使います。検索、挿入、削除にかかる時間は、要素数を n とすると対数時間の O(log n) です。この予測しやすい計算量と順序付き走査は、レポート、範囲検索、ソート済み一覧に役立ちます。標準規格が保証するのは順序の動作であり、特定の木構造による実装ではありません。

次の例を実行します。

このセクションのコードと表示されるラベルや出力は英語のままです。

#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<int, std::string> players;
  players.emplace(2, "Lin Dan");
  players.emplace(1, "Chen Long");

  const auto found = players.find(1);
  if (found != players.end()) {
    std::cout << found->first << ": " << found->second << '\n';
  }
  for (const auto& entry : players) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
}

1: Chen Long
1: Chen Long
2: Lin Dan

検索結果としてキー 1 が出力されます。ループは比較関数の順序でキーを走査するため、挿入順に関係なく 1 が 2 より先になります。

ハッシュベースの検索には std::unordered_map を使う

キー検索を優先し、ソート済みの走査が不要な場合は std::unordered_map を選びます。検索、挿入、削除は平均 O(1) ですが、多数のキーが衝突する場合など、最悪時には O(n) かかることがあります。再ハッシュによって反復順序が変わり、イテレーターが無効になる場合もあります。このコンテナにはハッシュと等価性の要件があります。等価なキーからは同じハッシュ値が生成されなければなりません。

次の例を実行します。

このセクションのコードと表示されるラベルや出力は英語のままです。

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
  std::unordered_map<std::string, int> scores;
  scores["Ada"] = 8;
  scores["Lin"] = 11;

  const auto found = scores.find("Ada");
  if (found != scores.end()) {
    std::cout << found->first << ": " << found->second << '\n';
  }
  for (const auto& entry : scores) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
  std::cout << "Players: " << scores.size() << '\n';
}

範囲ベースのループは scores 内のすべてのエントリーを走査します。エントリーの順序は任意であり、標準規格もこの例も特定の順序を保証しません。表示順が必要な場合は、キーを別のリストに集めてソートしてください。

std::map と std::unordered_map の選び方

単語の出現頻度を数える場合や、順序が関係しないキャッシュでは、std::unordered_map が自然な選択になることがよくあります。ソート済みの出力やキーによる範囲検索には std::map を使います。非順序コンテナの検索性能が用途に合っていても、表示順を整えたい場合は、反復順序を前提にせず、出力前にキーを集めてソートしてください。選択では平均速度だけでなく必要な動作も考慮します。性能が重要なアプリケーションでは、実際の用途を代表するデータでベンチマークを行ってください。

どちらのコンテナもキーと値を扱えますが、反復と性能に関する保証は異なります。キーを順序どおりに出力する走査には std::map を、順序が重要でないハッシュベースの検索には std::unordered_map を使います。順序付き走査の別の例については、C++ の中順走査を参照してください。