c++STL系列：map & multimap

红黑树

map/multimap 也是以红黑树为底层结构。
红黑树的左旋右旋、性质在这里先不深究。

map/multimap

和set不同的是map/multimap是以pair的key为排序对象，在G2.9的实现截图如下：

map/multimap给定的默认仿函数为less<_Ty>，默认的取值仿函数是select1st<pair<const int, string>>。
map也提供[]的操作符重载：

需要注意的是如果存在要查找的值就返回，否则返回要查找的值应该出现的位置。