STL

目前有三个容器我不太了解其内部实现，打算通过 <c++ primer> 进行学习

1. map
2. multimap
3. unordered_map

map

map 是目前最简单的结构，实现的方法是 BST（binary search tree）。因此，其时间复杂度等都与 BST 相同，搜索，增加，删除基本时间都是 log(n)。

use map when

1. 数据有序
2. 需要按照有序的顺序获得元素

unordered_map

unordered_map 则是通常所说的 hash table，哈希表，搜索，增加，删除都是以hash表为主，较好的情况是o(1)，也就是hash函数可以较好的把元素分布到表中，如果 hash 函数比较糟糕，则每一次添加删除查找，都是完整遍历一个表。

use unordered_map when

1. 对数据计数
2. 只需要根据 key 访问 value

简单来讲，就是当你需要使用 vector 来计数的时候，可以用 unordered_map 来代替。

| map             | unordered_map
---------------------------------------------------------
Ordering        | increasing  order   | no ordering
                | (by default)        |

Implementation  | Self balancing BST  | Hash Table
                | like Red-Black Tree |

search time     | log(n)              | O(1) -> Average
                |                     | O(n) -> Worst Case

Insertion time  | log(n) + Rebalance  | Same as search

Deletion time   | log(n) + Rebalance  | Same as search

multimap

multimap containers are generally slower than unordered_multimap containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.