アルゴリズムC++のstd::mapとstd::unordered_mapの実装の違いを知らなくて恥ずかしい思いをしたので、調べた結果をまとめておきます。記事のまとめstd::mapは平衡二分探索木、std::unordered_mapはハッシュテーブルで実装されている。キーの順番を保持したい場合はmapを使用したほうが良いが、そうでない場合はunordered_mapの方が性能的には優れている。mapmapとは何か?マップはキーの順番を保持している連想配列*1です。キーの順番を保持しているので、このようにイテレーションを回すこともできます。オプションをつけてコンパイル・実行してあげると、ちゃんと名前順にソートされているのが確認できます。(赤黒木など)で実装されている環境が多いようです。キーが木のノードになり、そのキーに対応する値と、2つの子となるキーへの参照を持っているイメージです。下記ページに視覚的にわかりやすい図も掲載されています。平衡二分探索木のそれと同じです。(ポインタのサイズ)は最低限使用する形になるでしょうか。unordered_mapunordered_mapとは何か?unordered_mapもmapと同じようにキーと値のペアを保持する連想配列なのですが、名前の通りキーの順番を保持しません。mapの部分で紹介したコードをunordered_mapに変えて実行してみると、キーの順番がバラバラになって保持されていることが確認できます。86実装unordered_mapはハッシュテーブルを使用して実装されているようです。どの程度のサイズのハッシュテーブルを確保しているかに依存します。実装されているのではないか、とのことです。実際にmapとunordered_mapのサイズを比較している記事も結構あって、確かにunordered_mapの方が小さくなっていることの方が多いです。アーカイブおすすめの本はてなブログをはじめよう!kanohkさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。