かくかくしかじか・・・

ゆるく、てきとうに

連想配列とは【C++】

連想配列とは

「連想配列クラス」とは検索可能なキーと、キーに対応する値の組（ペア）を要素とするコンテナクラスで、保持している要素から、キーを指定して値を高速に取り出せるクラス
例えば、string 型の人名と int 型の年齢を組にした要素を保持しておくと、名前をキーにして年齢を高速に取得することができる。名前から年齢への写像（mapping）のようなものなので map というクラス名を持つ。
普通の配列は、0から連続した整数を添え字として配列の要素にアクセスすることができます。それに対して、連想配列というのは、整数以外（例えば文字列）の値を添え字として要素にアクセスすることができます。
mapのイメージとして、最もわかりやすい例としてあげられるのが、辞書でしょう。辞書では、調べたい単語のページを調べると、その意味が得られます。この、調べたい単語にあたる部分を、キーと言い、意味にあたるものが、要素になります。

mapとunordered_mapの違い

実装方法の違い
- mapは平行二分探索木、unordered_mapはハッシュテーブルで実装されている。
キーの順番を保持したい場合は、map
キーの順番を保持しなくても良い場合は、unordered_mapの方が性能的には優れている。
ハッシュを使っているために、キーから要素を取り出す処理時間が O(1) とさらに高速である。

検証結果

  map<string, int>mp = {
    {"Tanaka Taro", 1},
    {"Nobi Nobita", 2},
    {"Toireno Hanako", 3},
  };

  for(auto i=mp.begin(); i!=mp.end(); i++){
    cout << "key = " << i->first;
    cout << ", val = " << i->second << endl;
  }

キー(名前)がソートされて、名前順(アルファベット順)に出力される

key = Nobi Nobita, val = 2
key = Tanaka Taro, val = 1
key = Toireno Hanako, val = 3

参考サイト