C++map
1. 关联式容器
vector、list、deque、forward_list(C++11)等STL容器，其底层为线性序列的数据结构，里面存储的是元素本身，这样的容器被统称为序列式容器。而map、set是一种关联式容器，关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。map和set的键是唯一的，但是mutimap和multiset支持多个同名且有不同映射的键共存。
2. 键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value, key代表键值，value表示与key对应的信息。比如：学生的姓名和他的学号是一一对应的，那么就可以通过查找学生的姓名来查找到对应的学号。map容器是Key Value结构，允许修改value，且允许多个相同的value存在。但map不允许存在相同的key（multimap除外），且key不可修改（因为会破坏内部的红黑树结构）。
3. map容器
形参含义：
key:键值对应key的类型
T：键值对应value的类型
Compare:比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下（内置类型元索）该参数不需要传递，如果无法比较时（自定义类型），需要用户自己显式传递比较规则（一般情况下按照函数指针或者仿函数来传递）
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
4. map的成员变量
map中键是不允许被修改的（因为修改键会破坏搜索二叉树的结构），但是映射可以被修改。map在value_type中使用了pair来保护键。map实例化的格式，实际上是调用了pair模板的显式实例化。
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)
{}
};
5. map的成员函数
5.1 map的成员函数介绍
map的构造：
| 函数声明 | 功能介绍 |
|---|---|
| map<K,V>m() | 构造一个空的map |
map的迭代器：
| 函数声明 | 功能介绍 |
|---|---|
| begin()和end() | begin:首元素的位置；end：下一个元素的位置 |
| cbegin()和cend() | c指const，cbegin和cend指向的内容不能修改 |
| rbegin()和rend() | 反向迭代器，rbegin从end开始，rend从begin开始，其++和–的方向相反 |
| crbegin()和crend() | 与前一个功能相同，但指向的内容不能修改 |
map的容量与元素访问：
| 函数名 | 函数声明 | 功能介绍 |
|---|---|---|
| empty | bool empty() const | 检测map中的元素是否为空，为空返回ture，不为空返回false |
| size | size_type size() const | 返回map中有效元素的个数 |
| operator[] | mapped type& operator[] (const key_type& k | 返回key对应的value |
| at | mapped_type& at (const key_type& k);const mapped_type& at (const key_type& k) const; | 返回key对应的value |
注意：
在元素访问时，at()（该函数不常用）函数，于operator[]功能相同但有一点区别：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value, at()函数直接抛异常。
map的修改：
| 函数名 | 函数声明 | 功能介绍 |
|---|---|---|
| insert | pair<iterator,bool> insert (const value_type& val) | 在map中插入键值对x，注意x是一个键值对，返回值也是键值对；iterator代表新插入元素的位置，bool代表插入成功 |
| erase | void erase (iterator position) | 删除position位置上的元素 |
| size_type erase (const key_type& k) | 删除键值为x的元素 | |
| void erase (iterator first, iterator last) | 删除**[first,last)**区间中的元素 | |
| swap | void swap (map& x) | 交换两个map中的元素 |
| clear | void clear() | 删除map里所有的元素 |
map的比较:
| 函数名 | 函数声明 | 功能介绍 |
|---|---|---|
| key_comp | ||
| value_comp |
map的操作：
| 函数名 | 函数声明 | 功能介绍 |
|---|---|---|
| find | iterator find (const key_type& k) | 搜索map里键等于k的元素，如果找到返回一个映射的迭代器，找不到返回end的迭代器 |
| count | size_type count (const key_type& k) const | 搜索map里键等于k的元素，找到返回1，找不到返回0 |
| lower_bound | iterator lower_bound (const key_type& k) | 在map里找>=k的元素，返回符合情况的最小键的迭代器 |
| upper_bound | iterator upper_bound (const key_type& k) | 在map里找>k的元素，返回符合情况的最小键的迭代器 |
| equal_range | pair<iterator,iterator>equal_range (const key_type& k) |
5.2 insert
insert的返回值是一个pair类模板，而它的参数val也有一个pair类模板。**insert使用pair类模板使得它同时具有插入和搜索的功能。**bool值用来判断map中需要插入的值是否已经存在，iterator是指向val值的迭代器。
insert的返回值:
如果insert搜索的val值存在，bool值就为false（判断插入失败），iterator会指向map中已经存在的val值；如果insert搜索的val值不存在，bool值就为true（判断插入成功），iterator会指向新插入的val值。
使用insert进行搜索：
由于insert使用pair类模板，所以它也有搜索的功能：
#include<iostream>
#include<map>
#include<string.h>
using namespace std;
int main()
{
string arr[] = { "张三","李四","王五","张三","张三","李四","张三","李四","王五","张三" };
map<string, int> countmap;
for (auto& e : arr)//传引用是为了拷贝临时变量浪费资源
{
pair<map<string, int>::iterator, bool>ret = countmap.insert(make_pair(e, 1));
if (ret.second == false)
{
ret.first->second++;
}
}
for (auto& i : countmap)
{
cout << i.first << ":" << i.second << endl;
}
return 0;
}
5.3 operator[]
map的operator[]是借助inert来实现的：
因此map的operator[]同时具有插入、查找和修改的功能：
#include<iostream>
#include<map>
#include<string.h>
using namespace std;
int main()
{
map<string, string> m;
m.insert(make_pair("first", "first"));
m.insert(make_pair("second", "second"));
cout << "before:" << endl;
for (auto& i : m)
{
cout << i.first << " : " << i.second << endl;
}
m["third"];//插入
printf("\n");
cout << m["first"] << endl;//查找
m["first"] = "x";//修改
m["fourth"] = "xxxx";//插入+修改
printf("\n");
cout << "after:" << endl;
for (auto& i : m)
{
cout << i.first << " : " << i.second << endl;
}
return 0;
}
6. map的特点
stl里的map和set用的是同一颗红黑树来实现的。
set：
注意：Rb_tree里有一个key_type和一个value_type，但set应该是key和key的映射关系，所以在成员变量里，stl把key_type和value_type都定义了为_key
map：
而在stl的map里，value_type则定义了一个pair,这样做的目的就是为了复用同一颗红黑树
所以从set和map的底层来看，它们的实现方法分别是：
set<K.>->rb_tree<K, K>
map<K, V>->rb_tree<K ,pair<const K, V>>
这种写法实际上是由stl_tree.h文件中的val模板决定你是key的set，还是key/value的map：
