关联型容器

在学习序列式容器时，我们知道，容器中元素的顺序都是由程序员决定的，程序可以随意指定新元素的的插入位置，而对于关联型容器，它的所有元素都是经过排序的，关联型容器都是有序的。它的每一个元素都有一个键（key），容器中的元素是按照键的取值升序排列的。

关联型容器内部实现为一个二叉树，在二叉树中，每个元素都有一个父节点和两个子节点，左子树的所有元素都比自己小，右子树的所有元素都比自己大，如图1所示。

图1 二叉树

关联型容器内部结构都是以这种二叉树结构实现，这也使得它可以高效的来查找容器中的每一个元素，但却不能实现任意位置的操作。

标准库提供了四种关联型容器：set（集合）、multiset（多重集合）、map（映射）、multimap（多重映射），其中set与multiset包含在头文件set中，map与multimap包含在头文件map中，如下所示：

#include<set>
#include<map>

接下来我们就对这四种容器的存储及访问特点进行讲解。

1、set与multiset

set与multiset都是集合，都是存储一组相同数据类型的元素。两者的区别是set用来存储一组无重复的元素，而multiset允许存储有重复的元素。

用户可以将数据存入集合或者从集合中删除元素，也可以快速判断某值是否在集合内。容器内部的二叉树节点值即容器所存储的元素值。集合中的元素值不可以被直接修改，因为这些元素是自动排序的，如果想要修改某一个元素值，必须先删除原有的元素，再插入新的元素。

2、map与multimap

映射与集合的主要区别在于，集合的元素本身是键本身，而映射的元素类型是由键和附加数据所构成的二元组，它很像“字典”，通过给定前一个类型的值，需要快速找出与该值对应的后一个类型的值。因此，在映射的二叉树节点中需要存储两种类型的数据，用来定位的数据称为键，另一个存储元素值的数据称为值，通常也说映射中存储的是一对键值对，它的一种通常用法也是根据键来查找对应的值。

映射又分为单重映射（map）与多重映射（multimap），两者的主要区别是map存储的是无重复键值的元素对，而multimap允许相同的键值重复出现，即一个键值可以对应多个值，如图2所示。

图2 map与multimap

这四种容器中，set与multiset，map与multimap的用法差不多，只是几个成员函数上有细微的差别，其差异主要是针对键是否必须唯一。接下来我们就学习一下这四种容器较为常用的操作方法。