前言

今天在解决一个问题《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 遍历时删除需要注意迭代器失效问题，常用的有下面两种写法

it = mp.erase(it);

或者

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 函数来删除元素，但是会报下面的编译错误

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::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 */