C++/map

<map>头文件声明了关联性容器map与multimap。这两个容器对应的是映射抽象容器。

map为单映射有序关联容器。存储的信息为“键->值”的形式。按照键排序。排序函数为构造函数的参数Compare。各种访问操作基本是对数时间复杂度。典型的map以二叉搜索树实现，SGI版本的stl使用红黑树实现。

multimap为一对多映射容器，即一个Key可能映射到多个值。

运算符

operator [] 对特殊情况的处理非常罕见。 函数传入一个键k：

• 如果键k在map中，函数返回k映射的内容值；
• 如果键k不在map中，那么函数会插入一个新的键值对，对插入的值进行默认构造，并且返回这个值得引用。

Observers

• key_comp() const;
• value_comp() const;

返回comparison object，可以分别对键、值进行比较。

lower_bound与upper_bound

• lower_bound返回传入键的下界，包括该键（如果存在的话）：
• upper_bound返回传入键的上界，不包括该键（如果存在的话）:

特殊函数

• find：如果有多个值，返回任意一个
• count：key所对应的value数量。因为map是单映射，所以它的返回至只可能是1或0。
• equal_range：返回给定键的元素范围，因为map是单映射，返回的范围为空或包含一个元素。 返回值为迭代器pair，分别等于调用lower_bound和upper_bound的结果。