目录
1. 关联容器和map容器概述
map容器是关联容器的一种。在关联容器中，对象的位置取决于和它关联的键的值。键可以是基本类型也可以是类类型。关联容器是与非关联容器（顺序容器）相对应的，顺序容器中元素的位置不依赖于元素的值，而是和该元素加入容器时的位置有关。关联容器的类型有下面八种：
按关键字有序保存元素
map 关联数组；保存关键字-值对
set 关键字即值，只保存关键字的容器
multimap 关键字可以重复出现的map
multiset 关键字可以重复出现的set
无序关联容器
unordered_map 用哈希函数组织的map，无序
unordered_set 用哈希函数组织的set，无序
unordered_multimap 哈希组织的map；关键字可以重复
unordered_multiset 哈希组织的set，关键字可以重复
map容器有四种，每一种都是由类模板定义的。所有类型的map容器保存的都是键值对的元素。map容器的元素是pair<const K, T>类型的对象，这种对象封装了一个T类型的对象和一个与其关联的K类型的键。pair元素中的键是const，因为修改键会扰乱容器中元素的顺序。每种map容器的模板都有不同的特性：
1、map容器：map的底层是由红黑树实现的，红黑树的每一个节点都代表着map的一个元素。该数据结构具有自动排序的功能，因此map内部的元素都是有序的，元素在容器中的顺序是通过比较键值确定的。默认使用 less<K> 对象比较。
2、multimap容器：与map容器类似，区别只在于multimap容器可以保存键值相同的元素。
3、unordered_map容器：该容器的底层是由哈希(又名散列)函数组织实现的。元素的顺序并不是由键值决定的，而是由键值的哈希值确定的，哈希值是由哈希函数生成的一个整数。利用哈希函数，将关键字的哈希值都放在一个桶（bucket）里面，具有相同哈希值的放到同一个桶。unordered_map内部元素的存储是无序的，也不允许有重复键值的元素，相当于java中的HashMap。
4、unordered_multimap容器：也可以通过键值生成的哈希值来确定对象的位置，但是它允许有重复的元素。
map和multimap容器的模板都定义在map头文件中，unordered_map和unordered_multimap容器的模板都定义在unordered_map头文件中中。
- multi前缀表明键值不必唯一，但是如果没有这个前缀，键值必须唯一。
- unordered前缀表明容器中元素的位置是通过其键值所产生的哈希值来决定的，而不是通过比较键值决定的，即容器中的元素是无序的。如果没有这个前缀，则容器中元素是由比较键值决定的，即有序。
2. map容器
下图展示了一个用名称作为键值 map<K, T>容器，对象是整数，用来表示年龄。
前面讲过map容器的底层是由红黑树（一种非严格意义上的平衡二叉树）实现的，元素检索的时间复杂度是O(logN)，相比于顺序检索的线性时间复杂度还是很快的。
2.1 map的创建以及初始化列表
map类模板有四个类型参数，但是一般只需要指定前两个模板参数的值。第一个是键值的类型，第二个是所保存对象的类型。我们通常所用的一种构造一个map对象的方法是：
Map<string, int> mapStudent;当初始化一个map时，必须提供关键字类型和值类型。我们将每个关键字-值对包围在花括号中： {key，value} 来指出它们一起构成了map中的一个元素。初始化列表有两种方式：
map<string, string> authors = { {"Joyce", "James"},
{"Austen", "Jane"},
{"Dickens", "Charles"} };或者：
map<string, string> authors { {"Joyce", "James"}, {"Austen", "Jane"}, {"Dickens", "Charles"} };但是需要注意的是：初始化列表的方式是C++11的新特性，对版本比较早的编译器不支持这一特性。
2.2 map容器的一般常用属性（方法）
size 返回有效元素个数
max_size 返回容器支持的最大元素个数
empty 判断容器是否为空，为空是返回true，否则返回false
clear 清空map容器2.3 插入数据
在构造map容器后，我们就可以往里面插入数据了。这里讲三种常见的数据插入方法。
第一种：用insert函数插入pair数据
map<string, int> mapStudent;//创建map
mapStudent.insert(pair<string, int>("student_one", 22));
mapStudent.insert(pair<string, int>("student_two", 25));
mapStudent.insert(pair<string, int>("student_three", 21));
或者使用make_pair
map<string, int> mapStudent;
mapStudent.insert(make_pair("student_one", 22));
mapStudent.insert(make_pair("student_two", 25));
mapStudent.insert(make_pair("student_three", 21));第二种：用insert函数插入value_type数据
map<string, int> mapStudent;//创建map
mapStudent.insert(map<string, int>::value_type("student_one", 22));
mapStudent.insert(map<string, int>::value_type("student_two", 25));
mapStudent.insert(map<string, int>::value_type("student_three", 21));第三种：用数组方式插入数据
map<string, int> mapStudent;//创建map
mapStudent["student_one"] = 22;
mapStudent["student_two"] = 25;
mapStudent["student_three"] = 21;第四种：用emplace函数插入数据
map<string, int> mapStudent;
mapStudent.emplace("student_one", 22);
mapStudent.emplace("student_two", 25);
mapStudent.emplace("student_three", 21);这几种插入方法的区别：
- 用insert函数的效果是一样的，在数据的插入上涉及到集合的唯一性这个概念，即当map中有某个关键字时，insert操作是失败的。
- emplace插入效果跟insert效果一样。
- 用数组方式插入数据就不同，它可以覆盖以前该关键字对应的值。
2.4 数据的访问和遍历
map访问和查找元素的常用方法有：
==========================================================================================
operator[] 访问元素，也可以用于修改某个元素的value值；不进行下标（关键字）是否存在的检查（即如果关键字不存在，程序运行不会出错），访问到某个元素时，
如果该元素的键值不存在则直接创建该元素，返回是初始的值（比如int型的初始为0，则返回0，string初始为NULL，则返回NULL）
at 访问元素，也可以用于修改某个元素的value值；会进行下标（关键字）是否存在的检查，如果关键字不存在，则会拋出 out_of_range 异常。
==========================================================================================
利用迭代器访问元素
******************************************************************************************
map<K, T>::iterator it;
(*it).first; // the key value (of type Key)
(*it).second; // the mapped value (of type T)
(*it); // the "element value" (of type pair<const Key,T>)
元素的键值和value值分别是迭代器的first和second属性。也可以用迭代器指针直接访问。
it->first; // same as (*it).first (the key value)
it->second; // same as (*it).second (the mapped value)
*****************************************************************************************
迭代器的成员函数：
begin 返回指向容器起始位置的迭代器（iterator）
end 返回指向容器末尾位置的迭代器
cbegin 返回指向容器起始位置的常迭代器（const_iterator）
cend 返回指向容器末尾位置的常迭代器（当不需要对元素进行写访问时使用常迭代器）
rbegin 返回指向容器起始位置的反向迭代器（reverse_iterator）
rend 返回指向容器末尾位置的反向迭代器
#########################################################################################
查找某键值的元素是否存在：
count 若存在，返回1；不存在返回0
find 若存在返回指向元素的迭代器指针，不存在返回end()
map的遍历
① 使用前向迭代器遍历map
//使用前向迭代器遍历map
map<string, int>::iterator iter;
for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout << iter->first << " " << iter->second << endl;
//当然也可以使用迭代器指针解引用的形式访问
for (map<string, int>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout << (*iter).first << " " << (*iter).second << endl;当然，这两种形式的访问都是可以改变元素中的value值的，即可以进行写访问。例子如下：
map<string, int> mapStudent;//创建map
mapStudent["student_one"] = 22;
mapStudent["student_two"] = 25;
mapStudent["student_three"] = 21;
map<string, int>::iterator iter;
for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
(*iter).second = 100; //将mapStudent中的元素value值全部改为100
for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout << iter->first << " " << iter->second << endl; //遍历
/*
输出结果如下：
student_one 100
student_three 100
student_two 100
*/如果改用const_iterator，则两种方式都不能进行写访问。
② 使用反向迭代器遍历map
map<string, int>::reverse_iterator iter;
for (iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)
cout << iter->first << " " << iter->second << endl; //反向遍历反向迭代器，顾名思义，就是倒着访问容器中元素的。
③ 使用auto关键字
C++中auto关键字具有自动进行类型检查的功能，可以少些不少代码。比如可以将①中的代码直接改为：
for (auto it = mapStudent.begin(); it != mapStudent.end(); it++)
cout << it->first << " " << it->second << endl; //遍历当然你还可以使用范围for语句更简练的遍历map容器：
for (auto x : mapStudent){
cout << x.first << " " << x.second << endl;
}如果需要对元素进行写操作的话，循环变量x必须要声明成引用类型。
④ 使用数组的方式遍历数组，略~
2.5 数据的删除
map容器中删除一个元素要使用erase函数，只要有以下几种用法。
//使用关键字删除
int res = mapStudent.erase("student_one"); //删除成功返回1，失败返回0；只有使用关键字删除时才有返回值
cout << "res=" << res << endl;
//使用迭代器删除
map<string, int>::iterator iter;
iter = mapStudent.find("student_two");
mapStudent.erase(iter);
//使用迭代器删除一个范围的元素
auto it = mapStudent.begin();
mapStudent.erase(it, mapStudent.find("student_two"));2.6 map中关键词的排序
STL map中重载operator()<的运算符，默认是采用小于号来排序的，以上代码在排序上是不存在任何问题的，因为上面的关键字是string类型，它本身支持小于号运算。string类型的关键字排序是按照字符串中的字符的顺序，如果第一个字符相同就比较第二个，如果前两个都相同就比较第三个，以此类推….. 如果关键词是int型的话，就直接按照大小排序了。
在一些特殊情况，比如关键字是一个结构体，涉及到排序就会出现问题，因为它没有小于号操作，insert等函数在编译的时候过不去，下面给出两个方法解决这个问题。
第一种：小于号重载，程序举例
#include <iostream>
#include <string>
#include <map>
using namespace std;
typedef struct tagStudentInfo
{
int nID;
string strName;
}StudentInfo, *PStudentInfo; //学生信息
int main()
{
int nSize;
//用学生信息映射分数
map<StudentInfo, int>mapStudent;
map<StudentInfo, int>::iterator iter;
StudentInfo studentInfo;
studentInfo.nID = 1001;
studentInfo.strName = "student_one";
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));
studentInfo.nID = 1002;
studentInfo.strName = "student_two";
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));
for (iter=mapStudent.begin(); iter!=mapStudent.end(); iter++)
cout<<iter->first.nID<<endl<<iter->first.strName<<endl<<iter->second<<endl;
}
/****以上程序是无法编译通过的，只要重载小于号，就OK了，如下：******/
typedef struct tagStudentInfo
{
int nID;
string strName;
bool operator < (tagStudentInfo const& _A) const
{
//这个函数指定排序策略，按nID排序，如果nID相等的话，按strName排序
if(nID < _A.nID) return true;
if(nID == _A.nID) return strName.compare(_A.strName) < 0;
return false;
}
}StudentInfo, *PStudentInfo; //学生信息第二种：仿函数的应用，这个时候结构体中没有直接的小于号重载，定义一个比较函数，程序说明
#include <iostream>
#include <string>
#include <map>
using namespace std;
typedef struct tagStudentInfo
{
int nID;
string strName;
}StudentInfo, *PStudentInfo; //学生信息
class sort
{
public:
bool operator() (StudentInfo const &_A, StudentInfo const &_B) const
{
if(_A.nID < _B.nID) return true;
if(_A.nID == _B.nID) return _A.strName.compare(_B.strName) < 0;
return false;
}
};
int main()
{
int nSize;
//用学生信息映射分数
map<StudentInfo, int>mapStudent;
map<StudentInfo, int>::iterator iter;
StudentInfo studentInfo;
studentInfo.nID = 1001;
studentInfo.strName = "student_one";
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));
studentInfo.nID = 1002;
studentInfo.strName = "student_two";
mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));
for (iter=mapStudent.begin(); iter!=mapStudent.end(); iter++)
cout<<iter->first.nID<<endl<<iter->first.strName<<endl<<iter->second<<endl;
system("pause");
return 0;
}3. multimap容器
multimap容器保存的是有序的键/值对，但是可以保存重复的元素。multimap中会出现具有相同键值的元素序列。multimap大部分成员函数的使用方式和map相同。因为重复键的原因，multimap有一些函数的使用方式和map有一些区别。
3.1 访问元素
multimap 不支持下标运算符，因为键并不能确定一个唯一元素。和 map 相似，multimap 也不能使用 at() 函数。
find函数
multimap 的成员函数 find() 可以返回一个键和参数匹配的元素的迭代器。例如：
std::multimap<std::string, size_t> people {{"Ann",25},{"Bill", 46}, {"Jack", 77}, {"Jack", 32},{"Jill", 32}, {"Ann", 35} };
std::string name {"Bill"};
auto iter = people.find(name);
if (iter ! = std::end (people))
std::cout << name << " is " << iter->second << std::endl;
iter = people.find ("Ann");
if (iter != std::end(people))
std::cout << iter->first << " is " << iter->second <<std::endl;如果没有找到键，会返回一个结束迭代器，所以我们应该总是对返回值进行检查。第一个 find() 调用的参数是一个键对象，因为这个键是存在的，所以输出语句可以执行。第二个 find() 调用的参数是一个字符串常量，它说明参数不需要和键是相同的类型。对容器来说，可以用任何值或对象作为参数，只要可以用函数对象将它们和键进行比较。最后一条输出语句也可以执行，因为有等于 “Ann” 的键。事实上，这里有两个等于 “Ann” 的键，你可能也会得到不同的运行结果。
equal_range
如果我们想访问给定键对应的所有元素。成员函数 equal_range() 就可以做到这一点。它会返回一个封装了两个迭代器的 pair 对象，这两个迭代器所确定范围内的元素的键和参数值相等。例如：
auto pr = people.equal_range("Ann");
if(pr.first != std::end(people))
{
for (auto iter = pr.first ; iter != pr.second; ++iter)
std:cout << iter->first << " is " << iter->second << std::endl;
}equal_range() 的参数可以是和键同类型的对象，或是不同类型的但可以和键比较的对象。返回的 pair 对象的成员变量 first 是一个迭代器，它指向第一个大于等于参数的元素；如果键和参数相等的元素存在的话，它是第一个键和参数相同的元素。如果键不存在，pair 的成员变量 first 就是容器的结束迭代器，所以应该总是对它们进行捡查。
lower_bound 和 upper_bound
multimap 的成员函数 lower_bound() 会返回一个迭代器，它指向键值和参数相等或大于参数的第一个元素，或者指向结束迭代器。upper_bound() 也返回一个迭代器，它指向键值大于函数参数的第一个元素，如果这样的元素不出现的话，它就是一个结束迭代器。所以，当存在一个或多个相等键时，这些函数会返回一个开始迭代器和一个结束迭代器，它们指定了和参数匹配的元素的范围，这和 equal_range() 返回的迭代器是相同的。因而前面的代码段可以这样重写：
auto iter1 = people.lower_bound("Ann");
auto iter2 = people.lower_bound("Ann");
if(iter1 != std::end(people))
{
for(auto iter = iterl ; iter != iter2; ++iter)
std::cout << iter->first << " is " << iter->second << std::endl;
}它和前一个代码段的输出结果是相同的。
count函数
通过调用 multimap 的成员函数 count() 可以知道有多少个元素的键和给定的键相同。
3.2 删除元素
erase函数
multimap 的成员函数 erase() 有 3 个版本：
- 以待删除兀素的迭代器作为参数，这个函数没有返回值；
- 以一个键作为参数，它会删除容器中所有含这个键的元素，返回容器中被移除元素的个数；
- 接受两个迭代器参数，它们指定了容器中的一段元素，这个范围内的所有元素都会被删除，这个函数返回的迭代器指向最后一个被删除元素的后一个位置。