map和multimap都需要#include，唯一的不同是，map的键值key不可重复，而multimap可以，也正是由于这种区别，map支持[ ]运算符，multimap不支持[ ]运算符。在用法上没什么区别。
image.png
C++中map提供的是一种键值对容器，里面的数据都是成对出现的,如下图：每一对中的第一个值称之为关键字(key)，每个关键字只能在map中出现一次；第二个称之为该关键字的对应值。
Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据 处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。

1、基本操作函数

  1.      begin()         返回指向map头部的迭代器
  3.      clear()        删除所有元素
  5.      count()         返回指定元素出现的次数
  7.      empty()         如果map为空则返回true
  9.      end()           返回指向map末尾的迭代器
  11.      equal_range()   返回特殊条目的迭代器对
  13.      erase()         删除一个元素
  15.      find()          查找一个元素
  17.      get_allocator() 返回map的配置器
  19.      insert()        插入元素
  21.      key_comp()      返回比较元素key的函数
  23.      lower_bound()   返回键值>=给定元素的第一个位置
  25.      max_size()      返回可以容纳的最大元素个数
  27.      rbegin()        返回一个指向map尾部的逆向迭代器
  29.      rend()          返回一个指向map头部的逆向迭代器
  31.      size()          返回map中元素的个数
  33.      swap()           交换两个map
  35.      upper_bound()    返回键值>给定元素的第一个位置
  37.      value_comp()     返回比较元素value的函数

2、声明

  1. #include<map>//头文件
  3. map<int, string> ID_Name;
  5. // 使用{}赋值是从c++11开始的，因此编译器版本过低时会报错，如visual studio 2012
  6. map<int, string> ID_Name = {
  7.                 { 2015, "Jim" },
  8.                 { 2016, "Tom" },
  9.                 { 2017, "Bob" } };

3、迭代器

共有八个获取迭代器的函数： begin, end, rbegin,rend 以及对应的 cbegin, cend, crbegin,crend。
二者的区别在于，后者一定返回 const_iterator，而前者则根据map的类型返回iterator 或者 const_iterator。const情况下，不允许对值进行修改。如下面代码所示：

  1. map<int,int>::iterator it;
  2. map<int,int> mmap;
  3. const map<int,int> const_mmap;
  5. it = mmap.begin(); //iterator
  6. mmap.cbegin(); //const_iterator
  8. const_mmap.begin(); //const_iterator
  9. const_mmap.cbegin(); //const_iterator

返回的迭代器可以进行加减操作，此外，如果map为空，则 begin = end。
map/multimap - 图2

4、插入操作（insert）

4.1、用insert插入pair数据

  1. //数据的插入--第一种：用insert函数插入pair数据  
  2. #include <map>    
  3. #include <string>  
  4. #include <iostream>  
  5. using namespace std;  
  7. int main()  
  8. {  
  9.     map<int, string> mapStudent;  
  10.     mapStudent.insert(pair<int, string>(1, "student_one"));  
  11.     mapStudent.insert(pair<int, string>(2, "student_two"));  
  12.     mapStudent.insert(pair<int, string>(3, "student_three"));  
  13.     map<int, string>::iterator iter;  
  14.     for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
  15.        cout<<iter->first<<' '<<iter->second<<endl;  
  16. }

4.2、用insert函数插入value_type数据

  1. //第二种：用insert函数插入value_type数据，下面举例说明  
  3. #include <map>    
  4. #include <string>    
  5. #include <iostream>    
  6. using namespace std;  
  8. int main()    
  9. {    
  10.     map<int, string> mapStudent;    
  11.     mapStudent.insert(map<int, string>::value_type (1, "student_one"));    
  12.     mapStudent.insert(map<int, string>::value_type (2, "student_two"));    
  13.     mapStudent.insert(map<int, string>::value_type (3, "student_three"));    
  14.     map<int, string>::iterator iter;    
  15.     for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
  16.          cout<<iter->first<<' '<<iter->second<<endl;    
  17. }

4.3、用insert函数进行多个插入

  1. // 插入单个键值对，并返回插入位置和成功标志，插入位置已经存在值时，插入失败
  2. pair<iterator,bool> insert (const value_type& val);
  4. //在指定位置插入，在不同位置插入效率是不一样的，因为涉及到重排
  5. iterator insert (const_iterator position, const value_type& val);
  7. // 插入多个
  8. void insert (InputIterator first, InputIterator last);
  10. //c++11开始支持，使用列表插入多个   
  11. void insert (initializer_list<value_type> il);
  1. #include <iostream>
  2. #include <map>
  4. int main()
  5. {
  6.     std::map<char, int> mymap;
  8.     // 插入单个值
  9.     mymap.insert(std::pair<char, int>('a', 100));
  10.     mymap.insert(std::pair<char, int>('z', 200));
  12.     //返回插入位置以及是否插入成功
  13.     std::pair<std::map<char, int>::iterator, bool> ret;
  14.     ret = mymap.insert(std::pair<char, int>('z', 500));
  15.     if (ret.second == false) {
  16.         std::cout << "element 'z' already existed";
  17.         std::cout << " with a value of " << ret.first->second << '\n';
  18.     }
  20.     //指定位置插入
  21.     std::map<char, int>::iterator it = mymap.begin();
  22.     mymap.insert(it, std::pair<char, int>('b', 300));  //效率更高
  23.     mymap.insert(it, std::pair<char, int>('c', 400));  //效率非最高
  25.     //范围多值插入
  26.     std::map<char, int> anothermap;
  27.     anothermap.insert(mymap.begin(), mymap.find('c'));
  29.     // 列表形式插入
  30.     anothermap.insert({ { 'd', 100 }, {'e', 200} });
  32.     return 0;
  33. }

4.4、用数组方式插入数据

  1. //第三种：用数组方式插入数据，下面举例说明  
  3. #include <map>    
  4. #include <string>    
  5. #include <iostream>    
  6. using namespace std;  
  8. int main()    
  9. {    
  10.     map<int, string> mapStudent;    
  11.     mapStudent[1] = "student_one";   
  12.     mapStudent[2] = "student_two";    
  13.     mapStudent[3] = "student_three";    
  14.     map<int, string>::iterator iter;    
  15.     for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)    
  16.         cout<<iter->first<<' '<<iter->second<<endl;    
  17. }

以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的，当然了第一种和第二种在效果上是完成一样的，用insert函数插入数据，在数据的 插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的，但是用数组方式就不同了，它可以覆盖以前该关键字对 应的值，用程序说明
mapStudent.insert(map::value_type (1, “student_one”));
mapStudent.insert(map::value_type (1, “student_two”));
上面这两条语句执行后，map中1这个关键字对应的值是“student_one”，第二条语句并没有生效，那么这就涉及到我们怎么知道insert语句是否插入成功的问题了，可以用pair来获得是否插入成功，程序如下：
pair::iterator, bool> Insert_Pair;
Insert_Pair = mapStudent.insert(map::value_type (1, “student_one”));
我们通过pair的第二个变量来知道是否插入成功，它的第一个变量返回的是一个map的迭代器，如果插入成功的话Insert_Pair.second应该是true的，否则为false。

  1. 验证插入函数的作用效果
  3. #include <map>    
  4. #include <string>    
  5. #include <iostream>    
  6. using namespace std;  
  8. int main()    
  9. {  
  10.     map<int, string> mapStudent;  
  11.     pair<map<int, string>::iterator, bool> Insert_Pair;    
  12.     Insert_Pair = mapStudent.insert(pair<int, string>(1, "student_one"));    
  13.     if(Insert_Pair.second == true)  
  14.         cout<<"Insert Successfully"<<endl;    
  15.     else    
  16.         cout<<"Insert Failure"<<endl;    
  17.     Insert_Pair = mapStudent.insert(pair<int, string>(1, "student_two"));    
  18.     if(Insert_Pair.second == true)    
  19.         cout<<"Insert Successfully"<<endl;    
  20.     else    
  21.         cout<<"Insert Failure"<<endl;    
  22.     map<int, string>::iterator iter;   
  23.     for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)    
  24.        cout<<iter->first<<' '<<iter->second<<endl;    
  25. }  
  28. 验证数组形式插入数据的效果   
  29. #include <map>    
  30. #include <string>    
  31. #include <iostream>    
  32. using namespace std;  
  34. int main()    
  35. {    
  36.     map<int, string> mapStudent;    
  37.     mapStudent[1] = "student_one";    
  38.     mapStudent[1] = "student_two";    
  39.     mapStudent[2] = "student_three";    
  40.     map<int, string>::iterator iter;    
  41.     for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)    
  42.        cout<<iter->first<<' '<<iter->second<<endl;  
  43. }

5、查找、删除、交换

  1. 查找：
  2. // 关键字查询，找到则返回指向该关键字的迭代器，否则返回指向end的迭代器
  3. // 根据map的类型，返回的迭代器为 iterator 或者 const_iterator
  4. iterator find (const key_type& k);
  5. const_iterator find (const key_type& k) const;
  8. 删除：
  9. // 删除迭代器指向位置的键值对，并返回一个指向下一元素的迭代器
  10. iterator erase( iterator pos )
  11. // 删除一定范围内的元素，并返回一个指向下一元素的迭代器
  12. iterator erase( const_iterator first, const_iterator last );
  13. // 根据Key来进行删除， 返回删除的元素数量，在map里结果非0即1
  14. size_t erase( const key_type& key );
  15. // 清空map，清空后的size为0
  16. void clear();
  19. 交换：
  20. // 就是两个map的内容互换
  21. void swap( map& other );

6、容量

  1. // 查询map是否为空
  2. bool empty();
  4. // 查询map中键值对的数量
  5. size_t size();
  7. // 查询map所能包含的最大键值对数量，和系统和应用库有关。
  8. // 此外，这并不意味着用户一定可以存这么多，很可能还没达到就已经开辟内存失败了
  9. size_t max_size();
  11. // 查询关键字为key的元素的个数，在map里结果非0即1
  12. size_t count( const Key& key ) const; //

7、排序

map中的元素是自动按Key升序排序，所以不能对map用sort函数；
这里要讲的是一点比较高深的用法了,排序问题，STL中默认是采用小于号来排序的，以上代码在排序上是不存在任何问题的，因为上面的关键字是int 型，它本身支持小于号运算，在一些特殊情况，比如关键字是一个结构体或者自定义类，涉及到排序就会出现问题，因为它没有小于号操作，insert等函数在编译的时候过 不去，下面给出两个方法解决这个问题。

7.1 小于号 < 重载

  1. #include <iostream>  
  2. #include <string>  
  3. #include <map>  
  4. using namespace std;
  6. typedef struct tagStudentinfo
  7. {
  8.     int      niD;
  9.     string   strName;
  10.     bool operator < (tagStudentinfo const& _A) const
  11.     {     //这个函数指定排序策略，按niD排序，如果niD相等的话，按strName排序  
  12.         if (niD < _A.niD) return true;
  13.         if (niD == _A.niD)
  14.             return strName.compare(_A.strName) < 0;
  15.         return false;
  16.     }
  17. }Studentinfo, *PStudentinfo; //学生信息  
  19. int main()
  20. {
  21.     int nSize;   //用学生信息映射分数  
  22.     map<Studentinfo, int>mapStudent;
  23.     map<Studentinfo, int>::iterator iter;
  24.     Studentinfo studentinfo;
  25.     studentinfo.niD = 1;
  26.     studentinfo.strName = "student_one";
  27.     mapStudent.insert(pair<Studentinfo, int>(studentinfo, 90));
  28.     studentinfo.niD = 2;
  29.     studentinfo.strName = "student_two";
  30.     mapStudent.insert(pair<Studentinfo, int>(studentinfo, 80));
  31.     for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
  32.         cout << iter->first.niD << ' ' << iter->first.strName << ' ' << iter->second << endl;
  33.     return 0;
  34. }

7.2 仿函数的应用

  1. //第二种：仿函数的应用，这个时候结构体中没有直接的小于号重载，程序说明  
  3. #include <iostream>  
  4. #include <map>  
  5. #include <string>  
  6. using namespace std;
  8. typedef struct tagStudentinfo
  9. {
  10.     int      niD;
  11.     string   strName;
  12. }Studentinfo, *PStudentinfo; //学生信息  
  14. class sort
  15. {
  16. public:
  17.     bool operator() (Studentinfo const &_A, Studentinfo const &_B) const
  18.     {
  19.         if (_A.niD < _B.niD)
  20.             return true;
  21.         if (_A.niD == _B.niD)
  22.             return _A.strName.compare(_B.strName) < 0;
  23.         return false;
  24.     }
  25. };
  27. int main()
  28. {   
  29.     //用学生信息映射分数  
  30.     map<Studentinfo, int, sort>mapStudent;
  31.     map<Studentinfo, int>::iterator iter;
  32.     Studentinfo studentinfo;
  33.     studentinfo.niD = 1;
  34.     studentinfo.strName = "student_one";
  35.     mapStudent.insert(pair<Studentinfo, int>(studentinfo, 90));
  36.     studentinfo.niD = 2;
  37.     studentinfo.strName = "student_two";
  38.     mapStudent.insert(pair<Studentinfo, int>(studentinfo, 80));
  39.     for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
  40.         cout << iter->first.niD << ' ' << iter->first.strName << ' ' << iter->second << endl;
  41.     system("pause");
  42. }

8、unordered_map

在c++11标准前，c++标准库中只有一种map，但是它的底层实现并不是适合所有的场景，如果我们需要其他适合的map实现就不得不使用比如boost库等三方的实现，在c++11中加了一种map unordered_map,unordered_set,他们的实现有什么不同呢？
map底层采用的是红黑树的实现查询的时间复杂度为O(logn),看起来并没有unordered_map快，但是也要看实际的数据量，虽然unordered_map的查询从算法上分析比map快，但是它有一些其它的消耗，比如哈希函数的构造和分析，还有如果出现哈希冲突解决哈希冲突等等都有一定的消耗，因此unordered_map的效率在很大的程度上由它的hash函数算法决定，而红黑树的效率是一个稳定值。
unordered_map的底层采用哈希表的实现，查询的时间复杂度为是O(1)。所以unordered_map内部就是无序的，数据是按散列函数插入到槽里面去的，数据之间无顺序可言，如果我们不需要内部有序，这种实现是没有问题的。unordered_map属于关联式容器，采用std::pair保存key-value形式的数据。用法与map一致。特别的是，STL中的map因为是有序的二叉树存储，所以对key值需要有大小的判断，当使用内置类型时，无需重载operator < ；但是用用户自定义类型的话，就需要重载operator < 。 unoredered_map全程使用不需要比较元素的key值的大小，但是，对于元素的==要有判断，又因为需要使用hash映射，所以，对于非内部类型，需要程序员为其定义这二者的内容，对于内部类型，就不需要了。unordered库使用“桶”来存储元素，散列值相同的被存储在一个桶里。当散列容器中有大量数据时，同一个桶里的数据也会增多，造成访问冲突，降低性能。为了提高散列容器的性能，unordered库会在插入元素是自动增加桶的数量，不需要用户指定。但是，用户也可以在构造函数或者rehash()函数中，指定最小的桶的数量。
还有另外一点从占用内存上来说因为unordered_map才用hash结构会有一定的内存损失，它的内存占用回高于map。
最后就是她们的场景了，首先如果你需要对map中的数据排序，就首选map，他会把你的数据按照key的自然排序排序（由于它的底层实现红黑树机制所以会排序），如果不需要排序，就看你对内存和cpu的选择了，不过一般都会选择unordered_map，它的查找效率会更高。
至于使用方法和函数，两者差不多，由于篇幅限制这里不再赘述，unordered_multimap用法亦可类推。