C++ 头文件系列(map)

简介

该头文件包含两个概念相似的容器----map、multimap。 而这两个容器反映的概念就是 映射。

这两个容器 相同 的属性有：

• 关联性
• 映射
• 动态增长
• 键（Key）唯一性

这两个不相同的属性是：

• 映射关系

容器类别

既然说到关联性容器，自然得说说标准库的容器类别。 C++库容器主要能分成以下几类：

1. 序列性容器： 将存储对象组织成线性模型，使用户能够像线性数组那样存取。
2. 关联性容器： 将存储内容以键（Key）相关联 ，通过键来存取内容。
3. 乱序容器： 存储对象以乱序存储，不具有顺序。
4. 容器适配器： 通过适配的方式实现，内部使用的是其它已有的容器。

map

map为单映射容器，所谓单映射，就是一对一映射的意思。 每种信息都以 键 -> 值 的形式被存储，由键 映射到 值，这是该类容器与vector等容器最大的不同。

实现

典型的map是以Binary Search Tree实现的，但也有可能使用其他合适的数据结构。 例如sgi stl使用的就是红黑树。

operator [ ]

除了迭代器，存取map元素时使用的较多的就是这个运算符了。 但实际上这个函数的语义不像看上去那么简单，这主要是因为这个函数对特殊情况的处理非常罕见（相比而言，C++11新增的at成员函数就比较符合正常逻辑）。 函数传入一个键k：

如果键k在map中，函数返回k映射的内容值；

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

Observers

这里有两个特别的函数，它们在C++标准文档里被成为Observers（可能是因为通过这两个函数能够一定程度上的观察键值对，一定程度是因为它们只能对键值对进行比较）。

key_compare     key_comp() const;
value_compare   value_comp() const;

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

lower_bound、upper_bound

这两个函数比较晦涩难懂，这里提出来说明一下。

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

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

两个函数这样设计的话：

1. 传入同一个键，能正确地将一个range分成上下两部分。
2. 用迭代器表示的range，开始和结尾分别以闭区间和开区间表示，这两个函数的返回至可以非常直观的代表range。

特殊函数

因为映射容器的特殊性，map和multimap具有其他容器所没有的一些特殊函数：

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

multimap

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

因为是一对多映射的关系，该库没有提供像map::operator []、map::at那样的元素存取函数， 而是想让用户依赖于lower_bound、upper_bound这些函数。

语义完整的函数

同时，因为允许一个键有对应多个值，某些函数也得到了它真正的意义：

• count（不止是返回0、1）
• equal_range（不止是返回空范围或包含一个元素的范围）

语义有异的函数

• find（如果有多个值，返回任意一个）