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するなどの操作を効率的に行うことができる バケット数を最初にきちんと設定しておけば大
![mapとunordered_mapの違いについてまとめておく - yasuhisa's blog](https://cdn-ak-scissors.b.st-hatena.com/image/square/25cb8d787ce6974bc50a0e2f995065753270fc1a/height=288;version=1;width=512/http%3A%2F%2Fecx.images-amazon.com%2Fimages%2FI%2F41W5R878R7L.jpg)