c++的map容器有4种，它们都保存了键值对类型的元素。map容器的元素是pair<const K,T>类型的对象，以K为键，T为值。pair实际上可以看作一个内部有两个元素的结构体，且这两个元素的类型是可以指定的[1] 。
struct pair
{
typeName1 first;
typeName2 second;
};
同时我们注意到pair元素中的键是const指针来修饰的，这表明我们不能去修改它，因为如果修改的话会扰乱容器中元素的顺序。下面我们来具体了解一下这四种容器的具体实现。
1. map<K,T> #
这个容器中的元素是有序的，通过less 。
1.1 创建容器 #
创建一个map容器的方法如下：
map<string, int> people;
map<string, int> people{ {"Alice",20},{"Bob",25} };
map<string, int> people{ pair<string, int>("Alice",20),
pair<string, int>("Bob",25)
};
可以先创建对象，后续再往里面加元素，也可以在初始化的时候添加一些元素。
1.2 插入元素 #
具体添加元素的api是insert函数，插入的元素类型可以有以下几种，第一种很容易理解，因为map里存放的就是pair类型的对象，第二种在保证类型正确的情况下也能保证正确插入，第三种方式则是根据map的value_type方式来插入。
people.insert(pair<string, int>("Tom", 20));
people.insert({ "John", 21 });
people.insert(map<string, int>::value_type("Li Hua", 22));
除了上面的三种方式以外还可以用类似于数组的方式来插入元素，下表事key，值对应着value。
people["Tom"] = 20;
people["John"] = 21;
people["Li Hua"] = 22;
1.3 删除元素 #
删除元素可以用erase函数来实现，首先传入的参数可以是key的值，代码如下所示：
string name = "John";
if (people.erase(name)) {
cout << "after erase--------------" << endl;
for (iter = people.begin(); iter != people.end(); iter++)
cout << iter->first << ' ' << iter->second << endl;
}
else{
cout << "erase error!" << endl;
}
这是一种很直观的方式，通过函数返回的结果来判断删除是否成功。同样可以采用指向删除元素的迭代器作为erase函数的参数。这种情况下，返回的迭代器将会指向被删除元素的下一个位置。如果迭代器参数指向的是容器的最后一个元素，会返回end迭代器。
在这种方式之下如果我们要删除全部的元素，第一种方式就是使用for循环一个一个删除，另一种方式就是使用erase的重载函数，指定删除的范围。
map<string, int>::iterator iter;
cout << "people map has " << people.size() << " element" << endl;
for (iter = people.begin(); iter != people.end(); iter++)
cout << iter->first << ' ' << iter->second << endl;
//用迭代器的方式来删除元素
map<string, int>::iterator delete_item_iter;
delete_item_iter = people.find("John");
map<string, int>::iterator next_iter = people.erase(delete_item_iter);
cout << "next iterartor is " << next_iter->first << ' ' << next_iter->second << endl;
people.erase(people.begin(), people.find("Tom"));
cout << "people map has " << people.size() << " element" << endl;
//删除全部的元素
map<string, int>::iterator next_iter2 = people.erase(people.begin(), people.end());
cout << "people map has " << people.size() << " element" << endl;
为了方便，我们可以结合下面的控制台输出来看这个删除的结果。在最开始可以看到总共有三个元素，分别是John, Li hua和Tom。然后我们用迭代器的方式删除John这个元素，这时函数返回的迭代器就会指向它的下一个元素Li hua。然后我们利用迭代器指定删除的范围，从begin()开始，到Tom结束，可以看到返回的结果显示还有一个元素，也就是说Tom其实是没有被删除掉的。所以我们需要注意这个指定的范围是不包括最后一个迭代器的。
这个特点同样可以用最后的例子来说明，如果删除全部的元素，最后的迭代器应该是end()，但是end()指向的是最后一个元素之后的位置，如果包括这个值的话程序执行就会报错了。
1.4 更新元素 #
更新元素比较简单，只需要根据对应的key去修改掉值就行了，只需要注意一下map<K,T>的K是不能修改的。
void updateMap(map<string, int>& map, string key, int value) {
map[key] = value;
}
//用迭代器的方式
void updateMap(map<string, int>& map, string key, int value) {
map.find(key)->second = value;
}
1.5 查找元素 #
查找元素主要用到的是find函数，这个在之前就已经出现过了，传入key的值就会返回对应的迭代器。或者直接用数组的方式也能得到对应的结果。这里需要注意以下如果找不到元素，数组的形式返回的结果是0，而迭代器返回的是map的end()这个迭代器。
cout << "tom's age is " << people["Tom"] << endl;
cout << "Li Hua 's age is " << people.find("Li Hua")->second << endl;
1.6 其他操作 #
map最基本的操作肯定是增删改查，但是初次之外还有一些比较好用的Api，这里贴出来一些供大家参考[2] 。
| 函数 | 功能 |
|---|---|
| clear(） | 删除所有元素 |
| count() | 返回指定元素出现的次数 |
| empty() | 如果map为空则返回true |
| equal_range() | 返回特殊条目的迭代器对 |
| get_allocator() | 返回map的配置器 |
| key_comp() | 返回比较元素key的函数 |
| lower_bound() | 返回键值>=给定元素的第一个位置 |
| max_size() | 返回可以容纳的最大元素个数 |
| rbegin() | 返回一个指向map尾部的逆向迭代器 |
| rend() | 返回一个指向map头部的逆向迭代器 |
| size() | 返回map中元素的个数 |
| swap() | 交换两个map |
| upper_bound() | 返回键值>给定元素的第一个位置 |
| value_comp() | 返回比较元素value的函数 |
2. multimap<K,T> #
这个容器和map<K,T>类似，同样会对元素排序，但是不同的是它允许使用重复的键，所以一个multimap容器可以保存多个具有相同键和值的<const K,T>元素。下面我们主要讨论和map<K,T>用法不一致的内容。
首先是插入元素，map可以利用数组的方式插入，但是multimap如果用这种方式可能会没法保证有唯一的key，所以不能用数组的方式来插入。用pair方式插入的代码和效果如下：
multimap<string, int> multi_people;
multi_people.insert(pair<string, int>("Tom", 20));
multi_people.insert(pair<string, int>("Tom", 20));
multi_people.insert({ "John", 21 });
multi_people.insert(map<string, int>::value_type("Li Hua", 22));
multimap<string, int>::iterator multi_iter;
cout << "multi_people map has " << multi_people.size() << " element" << endl;
for (multi_iter = multi_people.begin(); multi_iter != multi_people.end(); multi_iter++)
cout << multi_iter->first << ' ' << multi_iter->second << endl;
在上图中可以明显看到有两个一模一样的Tom被成功插入了。当我们用find函数去查找的时候会返回第一个找到的内容。同样的，如果去更新它的值，也会更新第一个找到的内容。
3. unordered_map<K,T> #
unordered_map要求键是唯一的，可以类比Java语言的HashMap。容器中的内容不是有序的，其位置完全由键的哈希值来确定。在这种情况下，容器内部的数据组织方式就可以采用哈希表的形式来组织，查询的时间复杂度也直接变成了 。
理论上只要是哈希函数就会产生哈希碰撞，在产生哈希碰撞之后要么就是将要插入的值加到下一个哈希槽中，要么在原来的位置后加一个链表来存储，可以根据不同的情况来选择不同的实现。
我们不难发现这种实现方式相比较map容器来说，在底层进行了很大的改变，也成功使得查询的时间复杂度变成了 ，但是从功能上来说确是和map达成了高度的一致，也要求key的唯一性。所以封装的API也和map的基本一致，只需要改变以下声明的类型就行。
4. unordered_multimap<K,T> #
unordered_multimap可以允许插入重复的键值对，同时底层的实现类似于unordered_map，功能的效果类似于multimap，所以在实践中可以类比这两部分来进行编程。
参考 #
- ^ https://blog.csdn.net/qq_46527915/article/details/115210318?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.no_search_link&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.no_search_link
- ^ https://www.cnblogs.com/fnlingnzb-learner/p/5833051.html
Last modified on 2021-12-23