前言

今天在解决一个问题《5710. 积压订单中的订单总数》时用到了map的反向遍历，看到问题时首先想到了优先队列，但是需要维护一个大根堆和一个小根堆，感觉操作起来比较麻烦，突发奇想使用map就能够解决。map本身就是有序的，正向遍历可以得到从小到大的序列，而反向遍历就可以得到从大到小的序列，这个思路本身没有错，但是解题时卡在了反向遍历时如何删除元素的知识点上，特此记录一下。

map的正向遍历

map的正向遍历是一个基础知识点了，先简单复习一下，不管是用 for 还是 while，只要控制迭代器持续前进就可以了。

map<int, string> mp{{1, "A"}, {2, "E"}, {3, "I"}, {4, "O"}, {6, "U"}};

for (map<int, string>::iterator it = mp.begin(); it != mp.end(); ++it) {
    cout << it->first << " " << it->second << endl;
}

/* 输出内容
1 A
2 E
3 I
4 O
6 U
*/

引入 auto 关键字以后，定义表示式的时候会更加方便一点

map<int, string> mp{{1, "A"}, {2, "E"}, {3, "I"}, {4, "O"}, {6, "U"}};

for (auto it = mp.begin(); it != mp.end(); ++it) {
    cout << it->first << " " << it->second << endl;
}

引入冒号以后表达式更加简短，要注意的是这里的 it 已经不是指针了，而是 value_type 类型，所以需要是用 . 来访问

map<int, string> mp{{1, "A"}, {2, "E"}, {3, "I"}, {4, "O"}, {6, "U"}};

for (auto it : mp) {
    cout << it.first << " " << it.second << endl;
}

引入了结构化绑定声明之后，遍历方式还可以写成下面这样

map<int, string> mp{{1, "A"}, {2, "E"}, {3, "I"}, {4, "O"}, {6, "U"}};

for (auto& [a, b] : mp) {
    cout << a << " " << b << endl;
}

map 遍历时删除元素

map 遍历时删除需要注意迭代器失效问题，常用的有下面两种写法

1	it = mp.erase(it);

或者

1	mp.erase(it++);

遍历删除时的例子：

map<int, string> mp{{1, "A"}, {2, "E"}, {3, "I"}, {4, "O"}, {6, "U"}};

for (auto it = mp.begin(); it != mp.end();) {
    if (it->second == "I")
        mp.erase(it++);
    else
        it++;
}

for (auto it : mp) cout << it.first << " " << it.second << endl;

/* 输出内容
1 A
2 E
4 O
6 U
*/

map 的反向遍历

map 反向遍历时可以使用 reverse_iterator 迭代器，配合 rbegin() 和 rend() 方法就可以完成反向遍历

map<int, string> mp{{1, "A"}, {2, "E"}, {3, "I"}, {4, "O"}, {6, "U"}};

for (auto it = mp.rbegin(); it != mp.rend(); it++) {
    cout << it->first << " " << it->second << endl;
}
/* 输出内容
6 U
4 O
3 I
2 E
1 A
*/

map 反向遍历时删除元素

一开始也是用 erase 函数来删除元素，但是会报下面的编译错误

1
2
3

error: no matching function for call to ‘std::map<int, std::__cxx11::basic_string<char> >::erase(
    std::reverse_iterator<std::_Rb_tree_iterator<std::pair<const int, std::__cxx11::basic_string<char> > > >)’
    mp.erase(it++);

查询文档发现，erase 函数重载只有下面几种实现:

void erase( iterator pos );                                     (until C++11)
iterator erase( const_iterator pos );                           (since C++11)
iterator erase( iterator pos );                                 (since C++17)

void erase( iterator first, iterator last );                    (until C++11)
iterator erase( const_iterator first, const_iterator last );    (since C++11)

size_type erase( const key_type& key );

参数是迭代器的函数并不支持 reverse_iterator，需要将 reverse_iterator 转化成 iterator 才可以，这时就需要用到 base 函数，对 reverse_iterator 类型的迭代器使用 base 函数得到的是上一个元素“原始指针”，这一点比较有意思，具体的解释可以参考《std::reverse_iterator::base》，这种操作决定了我们遍历删除的写法，应该是先自增再调用 base 函数，代码如下；

map<int, string> mp{{1, "A"}, {2, "E"}, {3, "I"}, {4, "O"}, {6, "U"}};

for (auto it = mp.rbegin(); it != mp.rend();) {
    if (it->second == "I") mp.erase((++it).base());
    else it++;
}

for (auto it = mp.rbegin(); it != mp.rend(); it++)
    cout << it->first << " " << it->second << endl;

/* 输出内容
6 U
4 O
2 E
1 A
*/

总结

map 默认会按照 key 排序，是一个常用的有序容器
配合使用 rbegin() 和 rend() 函数可以完成 map 的反向遍历
对 reverse_iterator 类型迭代器使用 base() 函数，可以转化成 iterator 相关类型，然后进行删除操作

==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<==

搬起砖，我抱不了你，放下砖 … 我尽力！

2021-3-21 19:44:27