1.关联式容器

在初阶阶段，我们接触过STL中的部分容器，比如; vector list deque等，这些容器被称为序列式容器，因为底层为线性序列的数据结构，里面储存的是元素本身，那什么是关联式容器呢？它与序列式容器有什么区别？

关联式容器存储的也是数据，与序列式容器不同的是，里面存储的是结构的键值对，在数据检索时比序列式容器更高效。

2.键值对

用来表示具有一一对应关系的一种结构，该结构中一般存储两个变量，key表示键值，value表示与key对应的信息；

比如：现在建立一个英汉互译的词典，那么字典中英文单词必然对应一个中文意思，那么找到该单词，就能找到其对应的中文含义

SGI-STL中关于键值对的定义：

template  struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair(): first(T1()), second(T2()) {} pair(const T1& a, const T2& b): first(a), second(b) {} };

3.树形结构的关联式容器

STL总共实现了两种不同结构的关联式容器：树形结构和哈希结构；

树形结构的关联式容器主要有四种: map set multimap mmultiset . 这四种容器的共同点是使用平衡二叉树(红黑树)作为底层结果，容器中的元素是一个有序的序列；

3.1 set

1.set的模板参数列列表

T:set存放的类型，实际在底层存储的键值对

compare: set中默认按照小于来比较

2.set的修改操作

insert可以插入数据，当插入已有元素的时候，他会不执行插入操作，也就是set可以去重，默认的set是按升序排序，可以去重的

erase支持迭代器删除，也可以删除值为val的元素，也可以删除区间元素，比如：

clear()可以清理set里的元素，清空size;

注意：

1.set中的元素不能修改。可以从容器中插入或者删除，

2.set可以使用迭代器遍历元素，得到有序序列，

3.set查找元素，时间复杂度是logN，

4.set的底层使用二叉搜索树(红黑树)来实现；

3.2 multiset

multiset可以不去重，允许有重复的元素出现，也是默认按照升序的方式打印出来

注意：

multiset和set的区别就是multiset中的元素可以重复

3.3 map

1.map是关联容器，他按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素，

2.在map中，键值key通常用于排序和唯一的标识元素，而值value中存储于此键值key相关联的内容，key和value的类型可能不同，并且在map内部，key与value通过成员类型value_type绑定在一起，取名为pair

int main() { 	map dict;  	pair kv1("sort", "排序"); 	dict.insert(kv1);//构造一个pair类，kv1插入  	dict.insert(pair("right", "右边"));//匿名对象pair  	dict.insert(make_pair("left", "左边"));//make_pair是一个函数模板，返回的pair  	dict.insert({ "string","字符串" });//隐式类型转换  	map::iterator it = dict.begin(); 	while (it != dict.end()) 	{ 		//cout << (*it).first << ":" << (*it).second << "\n"; 		 		//map中key不能修改，value可以修改 		//it->first += 'x'; 		it->second += 'x'; 		cout << it->first << ":" << it->second << "\n";  		it++; 	}  	//operator[]的用法 	//operator[]可以修改key对应的value，如果key不存在，那么就插入一个新的key 	//如果key存在，那么就可以更改对应的value 	dict["string"] = "好字符串";  	return 0; }

3.4 multimap

multimap和map的区别就是multimap中key是可以重复的

multimap没有重载operator[]操作；