std::map と std::unordered_map

　map というデータ構造は連想配列にあたるものと単純に理解していた。unordered_map について追って知ることとなり、初めて map のキーが自動的にソートされることを知る。

#include <map>
#include <unordered_map>

int main()
{
  std::map<int, int> mymap1;
  std::unordered_map<int, int> mymap2;

  int numbers[5] = {3, 1, 4, 1, 5};
  for (int i = 0; i < 5; ++i)
  {
    mymap1[numbers[i]]++;
    mymap2[numbers[i]]++;
  }

  std::printf("map\n");
  for (auto x : mymap1)
  {
    std::printf("%d: %d\n", x.first, x.second);
  }

  std::printf("\n");

  std::printf("unordered_map\n");
  for (auto x : mymap2)
  {
    std::printf("%d: %d\n", x.first, x.second);
  }

  return 0;
}

# 実行結果
map
1: 2
3: 1
4: 1
5: 1

unordered_map
5: 1
4: 1
1: 2
3: 1

　両者について、要素へのアクセスの時間計算量は、要素数をNとして次のようになる。

	complexity
map	O(logN)
unordered_map	O(1) (まれにO(N))

　unordered_map のアクセス速度が悪化するのは、要素数が増えてコンテナサイズの拡張が必要となるケースにおいてである。これは要素数が多くなるにつれて線的に悪化する。とはいえ平均的には O(1) で実行されるため、用途に応じて配慮するほかない。

　いうまでもなく、任意のサブセットに対してイテレートを行うようなときには、ソートが保証される map がより効率的である。他方で、任意の要素に繰り返しアクセスする必要があるような場合には、定数時間で処理できる unordered_map に軍配があがる。