1.关联式容器和键值对
1. 关联式容器
在之前的学习中，我们学习了vector，list，deque等容器，这些容器被统称为序列式容器，因为其底层是线性的数据结构，内部存放的是元素本身，那么关联式容器是什么呢？关联式容器也是用来存放数据的，只是关联式容器中存放数据是以<key,value>键值对的方式存储的，在数据检索的时候效率更高。
其实也可以理解成使用了更高级的数据结构，除了单纯的存储数据外，加上了一些特殊的存储逻辑。比如map和set就使用了二叉搜索树这种高级的数据结构。
STL中一共实现了两种不同类型的关联式容器：树形结构和哈希结构。
其中树形结构的容器有：map、multimap、set、multiset四个。其底层都是使用了**平衡搜索树（红黑树）**实现的，容器中的元素是一个有序的序列。
2. 键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。
在SGI- STL中对于键值对pair的定义如下
template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; //key T2 second; //value pair() : first(T1()), second(T2()) //默认构造 {} pair(const T1& a, const T2& b) : first(a), second(b) //构造函数 {} };
其中一般使用first表示key，second表示value。
make_pair
按照一般的调用方式，如果我们想创建一个pair的匿对象，需要使用以下代码
pair<string,string>("apple","苹果");
写了这么长一串就是为了创建一个匿名的pair对象多少是有点麻烦的，所以干脆就封装出一个函数模版make_pair,用于快速创建出一个pair对象，使用方式
make_pair("apple","苹果");//调用此函数就返回一个pair对象
在底层，这个函数是这样实现的
template<class T1, class T2> pair<T1,T2> make_pair(T1 first, T2 second) { return (pair<T1,T2>(first,second));//本质上还是调用了pair的构造函数 }
2. 树形结构的关联式容器——set
首先还是老样子，挂一下set的使用文档
上述的英文看起来可能对某些同学很吃力，所以我们总结一下
- set是按照特定顺序存储唯一元素的容器，里面不会出现重复的内容（可以用来去重）
- set虽然是采用了键值对的方式存储数据，但是在set中，key==value，可以对照二叉搜索树中的K模型来看。所以在插入数据时只需要插入value即可，不需要构造键值对。
- set中的元素一般是const修饰的，不能被修改，但是可以插入或者删除元素
- set中的数据的排序方式是可以自己传入的，默认使用的是仿函数less<T>。
- set通常比unordered_set更慢，通过其key访问单个元素，但允许根据其顺序对子集进行直接迭代。
- set中查找某个元素的时间复杂度为log2n
1. 模版参数列表
接下来我们来看看set的模版参数列表
第一个参数是其内部存放元素类型，实际在其内部存放的是<value,value>键值对；第二个参数看到是Compare就知道是仿函数啦，这是用来决定set中数据的排序方式的，默认按照小于来排序；Alloc是set中元素空间的管理方式，默认使用STL提供的空间配置器。
2. 默认成员函数
1. 构造函数
set的构造方式就非常简洁，一个默认构造，一个迭代器区间构造，还有一个拷贝构造
void Test1() { set<int> s1;//默认构造 vector<int> v = {1,3,5,2,6,3,5,1}; set<int> s2(v.begin(), v.end());//迭代器区间构造 set<int> s3(s2);//拷贝构造 cout << "s1:"; for(auto e : s1) { cout << e << " "; } cout << endl; cout << "s2:"; for(auto e : s2) { cout << e << " "; } cout << endl; cout << "s3:"; for(auto e : s3) { cout << e << " "; } cout << endl; }
2. 析构函数和赋值重载
很显然，在构造set对象的时候有资源申请，所以在析构函数的时候，需要进行资源释放。
析构函数和赋值重载的使用与其他容器非常相似，这里就不赘述了。
