map和set
一、关联式容器 键值对
序列式容器
vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。
关联式容器
也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高
键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息
源码中关于键值对的描述：
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)
{}
};
根据应用场景不同，STL总共实现了两种不同结构的关联式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结构，容器中的元素是一个有序的序列。
二、pair 和 make_pair
这个类将一对可能是不同类型的值（T1 和 T2）耦合在一起。 可以通过其公共成员first和second访问各个值,键值对就是这样被耦合在一起的，这有许多益处，比如用pair类型作为返回值，可以同时返回键值对的两个数据。
make_pair用来构造一个 pair 对象，它的第一个元素设置为 x，第二个元素设置为 y，在map和set中会经常使用：
三、K模型 & KV模型
K模型和KV模型都是二叉搜索树的应用：
K模型：
K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
KV模型：
每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
比如：实现一个简单的英汉词典，可以通过英文找到与其对应的中文，实现方式如下：
<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较
Key
查询英文单词时，只需给出英文单词，就可快速找到与其对应的Value
四、set
-
set是按照一定次序存储元素的容器
-
在set中，元素的key标识它,类型为T，并且每个值必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
-
set中的元素总是按照所指示的特定排序准则进行排序。
-
set在底层是用二叉搜索树(红黑树)实现的。
set的特点：
- set中插入元素时，只需要插入value即可，不需要构造键值对。
- set中的元素不可以重复，因此可以使用set进行去重。
- 使用set的迭代器遍历set中的元素，可以得到有序序列
- set中的元素默认按照小于来比较
- set中查找某个元素，时间复杂度为logN
set常用接口
1.构造相关接口
2.迭代器相关接口
和其他容器类似
3.增删查相关接口
在set中插入元素x，实际插入的是<x, x>构成的键值对
如果插入成功，返回
<该元素在set中的位置，true>
如果插入失败，说明x在set中已经存在，返回
<x在set中的位置，false>
从容器中删除所有元素，使容器的大小为 0
返回set中值为x的元素的位置
4.容量相关接口
五、map
key: 键值对中key的类型
T： 键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况
下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则
(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
map介绍
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
- 在map中，键值key通常用于排序和惟一标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过pair绑定在一起
- map支持下标访问符，即在[ ]中放入key，就可以找到与key对应的value。
- map通常被实现为二叉搜索树((红黑树)
map的特点
- map中的key是唯一的，并且不能修改
- 默认按照小于的方式对key进行比较
- map中的元素如果用迭代器去遍历，可以得到一个有序的序列
- map的底层为平衡搜索树(红黑树)，查找效率比较高，logN
- 支持[ ]操作符，注意 [ ] 中的是key
map常用接口
1.构造相关接口
(1) 空容器构造函数（默认构造函数）
构造一个没有元素的空容器。
(2) 范围构造函数
构造一个包含与范围 [first,last) 一样多的元素的容器，其中每个元素都由该范围内的对应元素构成。
(3) 拷贝构造函数
构造一个容器，其中包含 x 中每个元素的拷贝。
2.迭代器相关接口
与set十分类似，不赘述
3.容量相关接口
bool empty ( ) const 检测map中的元素是否为空，是返回true，否则返回false
size_type size() const 返回map中有效元素的个数
4.增删查相关接口
插入接口涉及了两个pair,相关用法可以通过例子学习：
// map::insert (C++98)
#include <iostream>
#include <map>
int main ()
{
std::map<char,int> mymap;
// first insert function version (single parameter):
mymap.insert ( std::pair<char,int>('a',100) );
mymap.insert ( std::pair<char,int>('z',200) );
std::pair<std::map<char,int>::iterator,bool> ret;
ret = mymap.insert ( std::pair<char,int>('z',500) );
if (ret.second==false) {
std::cout << "element 'z' already existed";
std::cout << " with a value of " << ret.first->second << '\n';
}
// second insert function version (with hint position):
std::map<char,int>::iterator it = mymap.begin();
mymap.insert (it, std::pair<char,int>('b',300)); // max efficiency inserting
mymap.insert (it, std::pair<char,int>('c',400)); // no max efficiency inserting
// third insert function version (range insertion):
std::map<char,int> anothermap;
anothermap.insert(mymap.begin(),mymap.find('c'));
// showing contents:
std::cout << "mymap contains:\n";
for (it=mymap.begin(); it!=mymap.end(); ++it)
std::cout << it->first << " => " << it->second << '\n';
std::cout << "anothermap contains:\n";
for (it=anothermap.begin(); it!=anothermap.end(); ++it)
std::cout << it->first << " => " << it->second << '\n';
return 0;
}
swap，clear，find也和set类似，不赘述
[ ]的使用 及 count接口
例子十分清楚：
计算具有特定键的元素
在容器中搜索键等于 k 的元素并返回元素个数
因为map容器中的所有元素都是唯一的，所以该函数只能返回 1（如果找到元素）或零（否则）