阅读量:0
1.关联式容器
在初阶阶段，我们接触过STL中的部分容器，比如; vector list deque等，这些容器被称为序列式容器，因为底层为线性序列的数据结构，里面储存的是元素本身，那什么是关联式容器呢？它与序列式容器有什么区别？
关联式容器存储的也是数据，与序列式容器不同的是，里面存储的是<key , value>结构的键值对，在数据检索时比序列式容器更高效。
2.键值对
用来表示具有一一对应关系的一种结构，该结构中一般存储两个变量，key表示键值，value表示与key对应的信息；
比如：现在建立一个英汉互译的词典，那么字典中英文单词必然对应一个中文意思，那么找到该单词，就能找到其对应的中文含义
SGI-STL中关于键值对的定义：
template <class T1, class T2> 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存放的类型，实际在底层存储<value，value>的键值对
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<string, string> dict; pair<string, string> kv1("sort", "排序"); dict.insert(kv1);//构造一个pair类，kv1插入 dict.insert(pair<string, string>("right", "右边"));//匿名对象pair dict.insert(make_pair("left", "左边"));//make_pair是一个函数模板，返回的pair dict.insert({ "string","字符串" });//隐式类型转换 map<string, string>::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[]操作；
