当前位置: 首页 > news >正文

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 相关类型,然后进行删除操作

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

搬起砖,我抱不了你,放下砖 … 我尽力!

相关文章:

  • C++中常见的字符判断与处理方法
  • 写给自己的KMP——C++版本
  • C++中一些可以在偷懒时直接使用的函数
  • protobuf中SerializeToString和SerializePartialToString的区别
  • linux文件权限简单备忘知识点
  • 使用AddressSanitizer搭配addr2line查找C/C++内存泄漏问题
  • C++对我来说简直就是星辰大海,为了避免翻船,我选择从小河沟出发
  • cpplint中filter参数的每个可选项的含义
  • 手把手搭建一个redis集群
  • 换个角度来看看C++中的左值、右值、左值引用、右值引用
  • C/C++中的数据类型转换()/static_cast/dynamic_cast/const_cast/reinterpret_cast
  • C++11中std::move和std::forward到底干了啥
  • 使用box2dweb做一个下落的小球,宝宝玩的不亦乐乎
  • C++中使用std::sort自定义排序规则时要注意的崩溃问题
  • 从一个小题中的应用来体会下std::tie的便利之处
  • IE9 : DOM Exception: INVALID_CHARACTER_ERR (5)
  • 【前端学习】-粗谈选择器
  • 【刷算法】求1+2+3+...+n
  • AngularJS指令开发(1)——参数详解
  • export和import的用法总结
  • JS专题之继承
  • PAT A1120
  • React-Native - 收藏集 - 掘金
  • React的组件模式
  • underscore源码剖析之整体架构
  • vue中实现单选
  • 编写符合Python风格的对象
  • 道格拉斯-普克 抽稀算法 附javascript实现
  • 关于Flux,Vuex,Redux的思考
  • 基于Javascript, Springboot的管理系统报表查询页面代码设计
  • 模仿 Go Sort 排序接口实现的自定义排序
  • 什么是Javascript函数节流?
  • 使用API自动生成工具优化前端工作流
  • 使用putty远程连接linux
  • 手机端车牌号码键盘的vue组件
  • 无服务器化是企业 IT 架构的未来吗?
  • 小程序测试方案初探
  • 一个6年java程序员的工作感悟,写给还在迷茫的你
  • Prometheus VS InfluxDB
  • Salesforce和SAP Netweaver里数据库表的元数据设计
  • 整理一些计算机基础知识!
  • #includecmath
  • $Django python中使用redis, django中使用(封装了),redis开启事务(管道)
  • (1/2) 为了理解 UWP 的启动流程,我从零开始创建了一个 UWP 程序
  • (day 12)JavaScript学习笔记(数组3)
  • (ros//EnvironmentVariables)ros环境变量
  • (保姆级教程)Mysql中索引、触发器、存储过程、存储函数的概念、作用,以及如何使用索引、存储过程,代码操作演示
  • (第8天)保姆级 PL/SQL Developer 安装与配置
  • (仿QQ聊天消息列表加载)wp7 listbox 列表项逐一加载的一种实现方式,以及加入渐显动画...
  • (四)Android布局类型(线性布局LinearLayout)
  • . Flume面试题
  • .“空心村”成因分析及解决对策122344
  • .NET MVC、 WebAPI、 WebService【ws】、NVVM、WCF、Remoting
  • .net oracle 连接超时_Mysql连接数据库异常汇总【必收藏】
  • .NET学习全景图