C++中反向遍历map时怎样删除元素
文章目录
- 前言
- map的正向遍历
- map 遍历时删除元素
- map 的反向遍历
- map 反向遍历时删除元素
- 总结
前言
今天在解决一个问题 《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::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
相关类型,然后进行删除操作
搬起砖,我抱不了你,放下砖 … 我尽力!