一. pair键值对
1. 概念
用来表示具有一一对应关系的一种数据结构，该结构中只包含两个成员变量key和value，key代表关键字，value表示关键字对应的值。比如：现在要建立一个英译汉的词典，那该词典中必然有英文单词和与其对应的中文含义，而且，英文单词与中文含义是一一对应的关系，即通过该单词，在词典中就可以找到与其对应的中文含义。
SGI-STL中关于pair键值对的定义：
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) {} };
2. 构造方法
pair();
构造一个空的pair，其中first和second的值为对应类型的默认值
// 构造一个空的pair pair<int,int> p; cout<<p.first<<":"<<p.second<<endl;// 0:0
template<class k, class v> pair (const pair<k,v>& pr);
拷贝构造相同的pair，内部实现为浅拷贝
pair<int,int> p1; pair<int,int> p2(p1);// 用p1拷贝构造p2 cout<<p2.first<<":"<<p2.second<<endl;// 0:0
pair (const first_type& a, const second_type& b);
最常用的构造方式，直接传first和second的值
pair<int,string> p(1,"hello world"); cout<<p.first<<":"<<p.second<<endl;// 1:hello world
make_pair构造一个临时对象
底层通过封装构造函数来实现，它可以自动识别我们传入数据的类型，通常用来构造临时对象作为参数传入。
make_pair(1,"haha"); make_pair(2,"hehe");
二. set
1. 概念
set是按照一定次序存储元素的容器，它的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序，在底层使用红黑树实现。在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素被const保护)，但是可以从容器中插入或删除它们。
set的模板参数列表
- T: set中存放元素的类型，实际在底层存储的是<value, value>键值对。
- Compare：set中元素默认按照小于来比较。
- Alloc：set中元素空间的管理方式，默认使用STL提供的空间配置器。
2. 补充说明
- 头文件：#include< set >
- set中插入元素时，只需要插入value即可，不需要构造键值对
- set中的元素不可以重复(因此可以使用set进行去重)。
- set中的元素不允许修改，因为这会打乱红黑树的结构，要修改的话只能先删除在插入。
- 使用set的迭代器遍历set中的元素，可以得到有序序列，因为底层是红黑树
- set中的元素默认按照小于来比较（即less< T >），若要更改比较方式第二个参数传入greater< T >即可。
- set中查找某个元素，时间复杂度为logN
2. 使用介绍
2.1 set的构造
2.2 set增加元素 — insert
pair<iterator,bool> insert (const T& val)
功能：插入一个值为val的节点
返回值：返回一个pair<iterator, bool>的键值对。如果添加成功iterator就是这个元素的迭代器，bool为true。如果添加失败（已经存在该元素），iterator返回已经存在的那个元素的迭代器，bool为false。
参数：需要存储的key数据
样例：
set<int> s; s.insert(1); s.insert(3); s.insert(2); for(auto& e : s) { cout<<e<<endl; }
编译运行：
2.3 set删除元素 — erase
void erase (iterator position);
功能：删除set中position迭代器位置上对应的节点
size_t erase (const T& val);
功能：删除值为val的节点
返回值：删除了的元素的数量
样例：
set<int> s; s.insert(1); s.insert(2); s.insert(3); for(auto& e : s) { cout<<e<<endl; } // 删除值为3的节点 s.erase(3); for(auto& e : s) { cout<<e<<endl; }
编译运行：
2.4 set查找元素 — find
iterator find (const T& val) const;
功能：查找值为val的节点
参数：要查找的节点的值
返回值：找到了返回节点的迭代器，找不到返回set::end，即最后一个节点的下一个位置的迭代器。
样例：
set<int> s; s.insert(1); s.insert(2); s.insert(3); // 查找3这个元素 set<int>::iterator it = s.find(3); if(it!=s.end()) { cout<<*it<<endl;// 3 }
三. multiset
1. 介绍
multiset相当于set 2.0，只不过其中元素是可以重复的，multi这个前缀的意思“多”，底层实现也是红黑树。
2. multiset与set的区别
性质上的区别在与set不能存储值相同的元素，而multiset可以。
使用上的差别比如对于insert这个函数：set返回的是一个pair<iterator, bool>键值对，而multiset返回的是新插入节点的迭代器。
四. map
1. 概念
map是关联容器，它按照特定的次序(按照key来比较)，存储由关键字key和值value组合而成的pair键值对。在map中，关键字key通常用于排序和惟一地标识元素，而值value中存储与此关键字key关联的内容。key和value的类型可能相同，也可能不同。
map的模板参数列表
- key: 键值对中key的类型
- T： 键值对中value的类型
- Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(比如自定义类型)，需要用户自己显式传递比较规则(仿函数类型)。
- Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。
2. 补充说明
头文件：#include< map >
map支持下标访问符，即在[ ]中放入key，就可以找到与key对应的value
map的底层为红黑树
3. 使用介绍
3.1 map的构造
map(）
功能：构造一个空的map
map<int double> m1; map<double,int> m2;
3.2 map增加元素 — insert
pair<iterator,bool> insert (const pair<k,v>& val);
功能：插入一个键值对val
参数：要插入的pair键值对
返回值：返回一个pair<iterator, bool>的键值对。如果添加成功iterator就是这个元素的迭代器，bool为true。如果添加失败（已经存在该元素），iterator返回已经存在的那个元素的迭代器，bool为false。
样例：
// 演示insert string fruits[]={"西瓜","香蕉","苹果","苹果","西瓜","香蕉"}; map<string,int> m; // 统计各种水果的数量 for(auto& e : fruits) { pair<map<string,int>::iterator,bool> p = m.insert(make_pair(e,1)); if(p.second == false) { ++(p.first->second); } } // 打印map for(auto& e : m) { cout<<(e.first)<<":"<<(e.second)<<endl; }
编译运行：
3.3 map删除元素 — erase
size_t erase (const k& k);
功能：删除关键字key=k的节点
参数：要删除的关键字k
返回值：删除节点的个数
void erase (iterator position);
功能：通过迭代器来删除节点
参数：要删除节点的迭代器
返回值：无
3.4 map查找元素 — find
iterator find (const k& k);
const_iterator find (const k& k) const;
功能：查找一个值为k的节点
参数：需要查找的关键字k
返回值：如果找到了，返回该节点的迭代器；如果没找到返回最后一个节点的下一个位置的迭代器，即end()。
样例：
// 演示find string fruits[]={"西瓜","香蕉","苹果","苹果","西瓜","香蕉"}; map<string,int> m; // 统计各种水果的数量 for(auto& e : fruits) { map<string,int>::iterator it = m.find(e); if(it!=m.end()) { ++(it->second); } else { m.insert(make_pair(e,1)); } } // 打印map for(auto& e : m) { cout<<(e.first)<<":"<<(e.second)<<endl; }
编译运行：
3.5 map修改元素 — [ ]
v& operator[ ] (const k& k);
功能
- 查看：传入关键字k，就可以得到对应值的引用
- 插入：传入关键字k，如果不存在的话就会插入pair(k,v())这个节点，并返回其值的引用；如果存在直接返回该节点的值的引用。
- 修改：因为返回的是节点键值对的值value的引用，所以我们拿到后可以修改它。
PS：我们一般不用[ ] 来查看键值对的value，因为如果没有的话它会自动插入，造成不必要的麻烦。查看的话通常还是用find()。
底层原理
内部其实是对insert()进行了封装，为什么不用find()进行封装？因为find()如果查找失败只是返回一个没有作用的迭代器，自然也拿不到它的value，这与[ ]的特性不匹配（方括号的特性是无论如何都要拿到key所对应的value），而insert()不论插入成功亦或失败都可以节点的迭代器，继而拿到value。
// []底层其实是调用下面这个式子的 (*((this->insert(make_pair(k,mapped_type()))).first)).second
样例：
// 演示[] string fruits[]={"西瓜","香蕉","苹果","苹果","西瓜","香蕉"}; map<string,int> m; // 统计各种水果的数量 for(auto& e : fruits) { ++(m[e]); } // 打印map for(auto& e : m) { cout<<(e.first)<<":"<<(e.second)<<endl; }
编译运行：
五. multimap
1. 介绍
multimaps也是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容，底层实现也是红黑树。
2. multimap与map的区别
在性质上，前者可以存储相同key值的节点（至于value相同与否无所谓），而后者key必须唯一。
在使用上，区别比如insert()：前者返回插入节点的迭代器，后者返回pair<iterator,bool>的键值对。另外就是前者没有重载方括号[ ]；而后者重载了，因为map只有唯一的key。
