C++ 头文件系列(map)

时间:2021-06-10 09:01:30

简介

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

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

  • 关联性
  • 映射
  • 动态增长
  • 键(Key)唯一性

这两个不相同的属性是:

  • 映射关系

C++ 头文件系列(map)

容器类别

既然说到关联性容器,自然得说说标准库的容器类别。 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返回传入键的下界,包括该键(如果存在的话):

C++ 头文件系列(map)

upper_bound返回传入键的上界,不包括该键(如果存在的话):

C++ 头文件系列(map)

两个函数这样设计的话:

  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(如果有多个值,返回任意一个