トップ > C++ > mapとunordered_mapの違いについてまとめておく

mapとunordered_mapの違いについてまとめておく

C++ データ構造

NLPだとstd::mapとtr1::unordered_mapなら後者を使うことになることが多いと思うけど、あれこれ混乱してきたのでメモる。NLPerなら押さえておくべき常識のはず。。。

それぞれの特徴

データ構造 std::map tr1::unordered_map
実装 赤黒木 ハッシュテーブル
find log n Average case: O(1), Worset case: O(n)
insert log n Average case: O(1), Worset case: O(n)
delete log n Average case: O(1), Worset case: O(n)
メリット キーでソート済みなことが保障されているので、ある範囲でiterationさせたいとき、deleteするなどの操作を効率的に行うことができる バケット数を最初にきちんと設定しておけば大体の操作が定数で済む*1。mapよりもメモリが少なくて済む

Effective STL―STLを効果的に使いこなす50の鉄則

Effective STL―STLを効果的に使いこなす50の鉄則

  • 作者: スコットメイヤーズ,Scott Meyers,細谷昭
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2002/01
  • メディア: 単行本
  • 購入: 9人 クリック: 155回
  • この商品を含むブログ (95件) を見る
にはmapをソート済みvectorに置き換えよう、ということが書いてあったりして、なんだかmapさんがかわいそうに思えてきた。。。ちなみにmapとvectorを走査するときの速度の違いはこの辺に。

参考

*1:3/4くらい埋まるとrehashする仕様みたい。Rehashは重い操作なので、なるべく回数を少なくしたい