C++のstd::mapとstd::unordered_mapの実装の違いを知らなくて恥ずかしい思いをしたので、調べた結果をまとめておきます。 記事のまとめ std::mapは平衡二分探索木、std::unordered_mapはハッシュテーブルで実装されている。 キーの順番を保持したい場合はmapを使用したほうが良いが、そうでない場合はunordered_mapの方が性能的には優れている。 map mapとは何か? マップはキーの順番を保持している連想配列*1です。キーの順番を保持しているので、このようにイテレーションを回すこともできます。 // map.cpp #include <iostream> #include <string> #include <map> using namespace std; int main(void) { // キーがstring型, 値がint型のs