【C++】Map和Set -- 详解（下）

【C++】Map和Set -- 详解（上）https://developer.aliyun.com/article/1515227?spm=a2c6h.13148508.setting.31.11104f0e63xoTy

🔺operator[] 函数介绍

map::operator= - C++ Reference (cplusplus.com)

前面学习的 vector 容器里面的 vector::operator[] 是传入元素下标，返回对该元素的引用。

而 map 中的 operator[] 访问元素函数，和其它容器有挺大区别的，已经不是传统的数组下标访问了。

• operator[] 底层实际上调用的 insert() 函数。

map容器中的 map::operator[] 是传入键值 key，通过该元素的 key 查找并判断是否在 map 中：

• 如果在 map 中，说明 insert 插入失败，insert 函数返回的 pair 对象会带出指向该元素的迭代器，通过这个迭代器，我们可以拿到该元素 key 对应的映射值 value，然后函数返回其对应映射值 value 的引用。
• 如果不在 map 中，说明 insert 插入成功，插入了这个新元素 ，然后函数返回其对应映射值 value 的引用。

注意：这里插入新元素时，该 value() 是一个缺省值，是调用 value 类型的默认构造函数构造的一个匿名对象。（比如是 string 类型就调用 string 的默认构造）

【operator[]总结】

使用 map::operator[] 函数，传入元素的键值 key：

• 如果 key 在map中，返回 key 对应映射值 value 的引用。
• 如果 key 不在map中，插入该元素 < key, value() >，返回 key 对应映射值 value 的引用。
• 拿到函数返回的映射值 value，我们可以对其修改。

这个函数非常的强大，即有查找功能，也有插入功能，还可以修改：

map<string, string> dict;
 
// 这里的意思是，先插入pair("tree", "")，再修改"tree"对应的value值为"树"
dict["tree"] = "树";
 
// 等价于：
dict["tree"];        // 插入pair("string", "")
dict["tree"] = "树"; // "tree"已存在，修改了"tree"对应的value值为"树"

【补充】

• 类似的成员函数 map::at 在元素存在时和 map::operator[] 具有相同的行为，区别在于，当元素不存在时 map::at 会抛出异常。

🔺insert 函数介绍

map::insert - C++ Reference (cplusplus.com)

功能：向 map 中插入元素（pair 对象）时，先通过该元素的 key 查找并判断是否在 map 中：

• 如果在，返回一个 pair 对象：<指向该元素的迭代器, false>。
• 如果不在，插入该元素 ，返回一个 pair 对象：<指向该元素的迭代器, true>。

• 【举例】实现一个字典 —— 可通过单词查找到对应的中文含义
  

定义 map，向 map 中插入元素（键值对），map 有两种插入元素方式：一般用第二种。

// 定义map
map<string, string> dict;
 
// 向map中插入元素，2种方式：
// 1、将键值对<"sort", "排序">插入map中，直接构造pair匿名对象(键值对)
dict.insert(pair<string, string>("sort", "排序"));
 
// 2、将键值对<"sort", "排序">插入map中，用make_pair函数来构造pair对象(键值对)
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("tree", "树"));

用迭代器遍历 map 元素：

需要注意的是，遍历 map 中元素的方式和其它迭代器有些不同，下面这种是错误示范：

这里的 it 是指向当前元素的迭代器，解引用 *it 是一个 pair 对象（键值对），而 map 中没有流插入运算符的重载，所以不能这样输出。

// 错误示范❌
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
    // cout << *it << endl; // error!
    it++;
}

这里调用的是 it.operator*() 解引用运算符重载函数，所以 *it 只是得到了当前节点中存储 pair  结构体。key 和 value 是一起封装在 pair 结构体中的，不能直接把 key 和 value 输出出来，除非重载了专门针对输出 pair 结构体中数据的流插入运算符，比如：ostream& operator << (ostream& out, const pair& kv);。

迭代器遍历map元素的两种方式：

// 迭代器遍历map
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{  
    /* 1、迭代器是像指针一样的类型
    * 对当前元素的迭代器it解引用(*it)可以得到当前节点中存储的数据：即pair对象(键值对)，然后用'.'再去访问pair对象中的kv值
    * 这里调用的是it.operator*() 解引用运算符重载函数，返回值为：pair对象的引用
    */
    cout << (*it).first << ", " << (*it).second << endl;
 
    /* 2、迭代器箭头->，返回当前迭代器指向j的地址(指针)：pair<string, int>*，实际上是调用的operator->()函数
    * 该指针再使用'->'就可以取到(pair对象)里面的kv值，即first和second
  * 代码为：it->->first，但可读性太差，编译器进行了特殊处理，省略掉了一个箭头，保持了程序的可读性
    */
    // 一般结构体的指针才会使用'->'来访问成员，所以当迭代器管理的节点中的数据是结构体的时候，就可以用'->'
    cout << it->first << ", " << it->second << endl; // 常用这种写法
    it++;
}

• 【举例】统计单词出现的次数

第一种解法，定义 map，遍历 str，向 map 中插入元素（键值对）：

string str[] = { "sort","sort", "tree","sort", "node", "tree","sort", "sort", };
 
// 定义map
map<string, int> Map;
 
// 遍历str
for (auto& e : str)  // 传引用，避免string深拷贝
{
    // 先查找判断当前单词是否已经在Map中了
    auto ret = Map.find(e);
    if (ret == Map.end()) // 如果不在Map中，返回Map中最后一个元素后面的迭代器
    {
        Map.insert(make_pair(e, 1)); // 插入pair对象(键值对)，即<单词，单词出现次数>
    }
    else // 如果在Map中，返回该元素的迭代器
    {
        ret->second++; // 单词出现的次数+1
    }
}
 
// 遍历map，这里的e是map的元素(即pair对象)，打印<单词，单词出现次数>
for (auto& e : Map)
{
    cout << e.first << ", " << e.second << endl;
}

上述解法，先查找当前单词是否在 map 中，如果不在，则插入，但是在插入函数内又会查找一次，找到插入的位置，有点冗余。

第二种解法，插入元素时，insert 本来就有查找功能：

void test_map()
{
  string str[] = { "sort", "sort", "tree", "sort", "node", "tree", "sort", "sort", };
  
  // 定义map
  map<string, int> count_map;
 
  // 遍历str
  for (auto& e : str)
  {
    // 插入元素
    auto ret = count_map.insert(make_pair(e, 1));
    // insert返回值类型是：pair<map<string, int>::iterator, bool>
 
    // 插入失败，说明该元素已存在于map中，函数返回一个pair对象
        // 即：pair<指向该元素的迭代器, false>
    if (ret.second == false)
    {
      (ret.first)->second++; // 对当前元素的value值加1
    }
  }
 
  // 遍历map，这里的e是map的元素(即pair对象)
  for (auto& e : count_map)
  {
    cout << e.first << ", " << e.second << endl;
  }
}

第三种解法：

使用 map::operator[] 函数根据当前元素的键值 key 查找，判断该元素是否在 map 中，如果在，返回其映射值 value 的引用，如果不在，当成新元素插入，并返回其映射值 value 的引用。

• 若元素 e 存在，返回其对应映射值 value，并加 1。
• 若元素 e 不存在，则插入，返回其对应映射值 value，并加 1。

string str[] = { "sort", "sort", "tree", "sort", "node", "tree", "sort", "sort", };
 
// 定义map
map<string, int> Map;
 
// 使用operator[]函数
for (auto& e : str)
{
    Map[e]++;
}
 
// 遍历map，打印< 单词，单词出现次数 >
for (auto& e : Map)
{
    cout << e.first << ", " << e.second << endl;
}

【总结】

1. map 中的的元素是键值对（pair 结构体）。
2. map 中的 key 是唯一的，并且不能修改，只能修改 key 对应的映射值 value。
3. 默认按照小于的方式对 key 进行比较。
4. map 中的元素如果用迭代器去遍历，可以得到一个有序的序列。
5. map 的底层为平衡搜索树（红黑树），查找效率比较高，时间复杂度为 O(logN)。
6. 支持 [] 操作符，operator[] 中实际进行插入查找，即在 [] 中放入 key，就可以找到与 key 对应的 value。

3、multiset

（1）multiset的介绍

multiset - C++ Reference (cplusplus.com)

【翻译】

1. multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的。
2. multiset 中，元素的 value 也会识别它（因为 multiset 中本身存储的就是  组成的键值对，因此 value 本身就是 key，key 就是 value，类型为 T），multiset 元素的值不能在容器中进行修改（因为元素总是 const 的），但可以从容器中插入或删除。
3. 在内部，multiset 中的元素总是按照其内部比较规则（类型比较）所指示的特定严格弱排序准则进行排序。
4. multiset 容器通过 key 访问单个元素的速度通常比 unordered_multiset 容器慢，但当使用迭代器遍历时会得到一个有序序列。
5. multiset 底层结构为二叉搜索树（红黑树）。

【注意】

1. multiset 中在底层中存储的是  的键值对。
2. mtltiset 的插入接口中只需要插入即可。
3. 与 set 的区别是，multiset 中的元素可以重复，set 中的 value 是唯一的。
4. 使用迭代器对 multiset 中的元素进行遍历，可以得到有序的序列。
5. multiset 中的元素不能修改。
   
6. 在 multiset 中找某个元素，时间复杂度为 O(logN)。
   
7. multiset 的作用：可以对元素进行排序。
   

（2）multiset的使用

这里只简单演示 set 与 multiset 的不同，其他接口接口与 set 相同，可以参考 set。

#include <set>
 
void TestSet()
{
    int array[] = { 4, 1, 3, 9, 6, 4, 5, 8, 4, 4 };
    // 注意：multiset在底层实际存储的是<int, int>的键值对
    multiset<int> s(array, array + sizeof(array)/sizeof(array[0]));
 
    for (auto& e : s)
        cout << e << " ";
    cout << endl;
    // 1 3 4 4 4 4 5 6 8 9
 
    cout << s.count(4) << endl; // 运行结果：3
    cout << s.count(3) << endl; // 运行结果：1
 
    return 0;
}

4、multimap

（1）multimap的介绍

multimap - C++ Reference (cplusplus.com)

【翻译】

1. Multimaps 是关联式容器，它按照特定的顺序，存储由 key 和 value 映射成的键值对value>，其中多个键值对之间的 key 是可以重复的。
2. 在 multimap 中，通常按照 key 排序和唯一地标识元素，而映射的 value 存储与 key 关联的内容。key 和 value 的类型可能不同，通过 multimap 内部的成员类型 value_type 组合在一起，value_type 是组合 key 和 value 的键值对：typedef pair value_type;
3. 在内部，multimap 中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对 key 进行排序的。
4. multimap 通过 key 访问单个元素的速度通常比 unordered_multimap 容器慢，但是使用迭代器直接遍历 multimap 中的元素可以得到关于 key 有序的序列。
5. multimap 在底层用二叉搜索树（红黑树）来实现。

【注意】

• multimap 和 map 的唯一不同就是：map 中的 key 是唯一的，而 multimap 中的 key 是可以重复的。

（2）multimap的使用

• multimap 中的接口可以参考 map，功能都是类似的。

注意 ：

1. multimap 中的 key 是可以重复的。
2. multimap 中的元素默认将 key 按照小于来比较。
3. multimap 中没有重载 operator[] 操作（为什么？因为 multimap 中的元素是按照键值有序存储的，而 operator[] 操作需要通过键值来访问元素，这样会破坏 multimap 中元素的有序性。因此，multimap 只提供了通过迭代器来访问元素的方式，如 find()、lower_bound()、upper_bound() 等函数）。
4. 使用时与 map 包含的头文件相同。