现代 C++ 编程实战
吴咏炜
前 Intel 资深软件架构师
34196 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 51 讲
加餐 (1讲)
现代 C++ 编程实战
15
15
1.0x
00:00/00:00
登录|注册

04 | 容器汇编 I:比较简单的若干容器

pop
push
emplace
pop
push
emplace
高效插入和删除
pop_front
emplace_front
push_front
emplace_back
emplace
erase
insert
push_back
pop_back
resize
reserve
capacity
data
中括号下标访问
swap
size
empty
end
begin
stack(或 queue)的 pop 函数返回类型为 void 的原因
不同序列容器类型的原因
容器的共同特点
LIFO数据结构
成员函数
依赖于底层容器
后进先出
FIFO数据结构
成员函数
依赖于底层容器
先进先出
内存利用率优先
节约内存
单向链表
中间频繁插入或删除
单独分配
成员函数
双向链表
频繁头尾操作
部分连续存储
成员函数
双端队列
预留内存
尾部操作
emplace系列函数
移动构造函数
连续存放
成员函数
动态数组
对外暴露接口
在代码中使用
支持字符串操作
字符串管理
成员函数
存放字符类型数据
支持交换
大小
记录状态是否为空
开始和结束点
吴咏炜, output_container
QuantStack, xeus-cling
cppreference.com
问题
容器的理解和认识
适用场景
特点
适用场景
特点
适用场景
特点
替代标准算法
适用场景
内存布局
特点
适用场景
内存布局
特点
适用场景
性能优化
内存布局
特点
推荐用法
用途
特点
容器的共同特点
参考资料
课后思考
总结
stack
queue
forward_list
list
deque
vector
string
容器概述
C++ 容器

该思维导图由 AI 生成,仅供参考

你好,我是吴咏炜。
上几讲我们学习了 C++ 的资源管理和值类别。今天我们换一个话题,来看一下 C++ 里的容器。
关于容器,已经存在不少的学习资料了。在 cppreference 上有很完备的参考资料([1])。今天我们采取一种非正规的讲解方式,尽量不重复已有的参考资料,而是让你加深对于重要容器的理解。
对于容器,学习上的一个麻烦点是你无法直接输出容器的内容——如果你定义了一个 vector<int> v,你是没法简单输出 v 的内容的。有人也许会说用 copy(v.begin(), v.end(), ostream_iterator(…)),可那既啰嗦,又对像 mapvector<vector<…>> 这样的复杂类型无效。因此,我们需要一个更好用的工具。在此,我向你大力推荐 xeus-cling [2]。它的便利性无与伦比——你可以直接在浏览器里以交互的方式运行代码,不需要本机安装任何编译器(点击“Trying it online”下面的 binder 链接)。下面是在线运行的一个截图:
xeus-cling 也可以在本地安装。对于使用 Linux 的同学,安装应当是相当便捷的。有兴趣的话,使用其他平台的同学也可以尝试一下。
如果你既没有本地运行的条件,也不方便远程使用互联网来运行代码,我个人还为本专栏写了一个小小的工具 [3]。在你的代码中包含这个头文件,也可以方便地得到类似于上面的输出。示例代码如下所示:
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文介绍了C++中常用的容器,包括vector、deque、list、forward_list、queue和stack。其中,作者详细介绍了每种容器的特点、内存布局和使用方法。对于每种容器,都强调了其适用场景和优势,以及与其他容器的比较。此外,还介绍了容器适配器queue和stack,以及它们与底层容器的关系和接口特点。通过代码示例展示了容器的使用方法和注意事项。整体来说,本文通过介绍这些容器,为读者提供了对C++容器的基本了解,并给出了一些使用建议。文章内容详实,适合C++初学者快速了解和掌握这些常用容器的特点和使用方法。文章还提供了一些课后思考问题,引发读者对容器的进一步思考和交流。 文章中介绍了C++中的序列容器和容器适配器,通过对每种容器的特点和使用方法的介绍,读者可以对C++中的容器有了一定的理解和认识。下一讲将继续介绍剩余的标准容器。欢迎读者留言和作者交流对容器的看法和思考。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《现代 C++ 编程实战》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(62)

  • 最新
  • 精选
  • 中年男子
    我发现老师的问题基本都可以在文章中找到答案, 1、2就不说了,3说一下我的理解:引用老师在vector那段的话 stack(queue)为保证强异常安全性,如果元素类型没有提供一个保证不抛异常的移动构造函数, 通常会使用拷贝构造函数,而pop作用是释放元素,c++98还没有移动构造的概念,所以如果返回成员,必须要调用拷贝构造函数,这时分配空间可能出错,导致构造失败,要抛出异常,所以没必要返回成员。

    作者回复: 很棒👌。 异常安全是关键。

    2019-12-04
    2
    86
  • 禾桃
    请教一个问题, #1 为什么一定强制移动构造函数不要抛出异常? 移动构造函数抛出异常后,catch处理不可以吗? #2 为什么拷贝构造函数被允许抛出异常? 能麻烦给些代码说明一下吗? 非常感谢!

    作者回复: catch住也没有用了。仔细想一下,我现在要把vector里的两个对象移到一个新的vector,移第一个成功,第二个时有异常,然后vector该怎么办?现在两个vector都废掉了。 拷贝不影响旧的容器。即使发生异常,至少老的那个还是好的。这就是异常安全。

    2019-12-05
    2
    56
  • YouCompleteMe
    1.都是线性容器 2.不同容器功能,效率不一样 3.实现pop时返回元素时,满足强异常安全,代码实现复杂,可读性差。

    作者回复: 3的正解终于出现,有人说到“异常安全”了。👍 再说两句,这是C++98时设计的接口,没有移动就只能那样。有了移动,在多线程的环境里,移动返回加弹出实际上就变得有用了。我对复杂和可读性部分不那么同意。

    2019-12-04
    31
  • Alice
    吴老师您好,我是那个那天问您vector演示代码的学生,还需要接着请教这段代码的一些问题。因为我刚接触c++不久,可能有些基本语法理解的不是很到位还没有那么深,就需要再问几个基础的问题了。就先请教obj1部分的函数吧,先用reserve(2)预留了两个存储空间,然后接着用emplace_back()在最后面构造新元素,所以说因为有两个新开的空间那么前两次用emplace_back()构造元素成功就调用构造函数抛出两个obj1( )不知道理解的对不对?那第三个obj1( )是怎么来的呢?后面两个obj1( const obj1&)怎么来的也不是很理解?这里的obj1&为什么要定义成const类型呢? 还有就是我现阶段对构造函数的理解还停留在初始化的意思上理解地还是太浅吧,不知道该怎么再往深理解一下? 麻烦老师再帮我解答一下问题,辛苦老师了💦

    作者回复: 头两个在已有空间上成功构造。第三个时发现空间不足,系统会请求更大的空间,大小由实现决定(比如两倍)。有了足够的空间后,就会在新空间的第三个的位置构造(第三个obj1),成功之后再把头两个拷贝或移动过来。

    2019-12-11
    2
    13
  • EncodedStar
    《现代C++实战31讲》第一天 容器汇编1:比较简单的若干容器 一、容器的输出: 1.简单容器(如:vector)输出就是遍历(v.begin,v.end) 2.复杂容器(如:vector<vector>)就需要工具 xeus-cling 二、string 1.接口中不建议使用const string& ,除非确实知道调用者使用的是string,如果函数不对字符串做特殊处理的话用const char* 可以避免在调用字符串的时候构造string 三、vector 1.vector主要缺陷是大小的增长导致的元素移动,如果可能,尽早使用reserve函数为vector保留所需要的内存,在vector预期会增长很大时带来很大的性能提升 四、deque 1.如果需要经常在头尾增删元素内容,deque会合适 五、list 1.list 是双向链表 2.forward_list是单向链表 六、stack 1.后进先出,底层由deque实现 课后思考: 1.容器有哪些共同点 答:都是线性容器,非关联容器 2.为什么C++有那么多不同的序列容器类型 答:不同容器对应实现不同需求,效率不同 3.为什么stack(或者queue) pop函数返回的是void而不是直接返回内容 答:为了保证异常安全,如果返回的成员构造失败就会抛出异常。

    作者回复: 学习很认真,回答也基本抓住要点了,尤其问题 2 和 3。👍

    2019-12-19
    8
  • Alice
    老师 您好 我是一个c++的初学者😳,这一讲的容器的概念原理都理解了,就是vector那一段的演示代码推不出老师的结果来,能不能麻烦老师再解释一下那段代码,辛苦老师了👨‍🏫!

    作者回复: 关于几次拷贝/移动的问题?参考 hello world 的评论下的廖熊猫的回答: 在插入的时候,你会发现空间不够了,然后开辟新的空间,在新空间先把最后插入的元素放好,然后再依次把以前的元素一个一个挪过来。空间不够的话最后一个元素是没法插入进去的啊,所以没办法移动三次的。 还有我自己的回答: 两者都是要构造第 3 个对象时空间不足,需要这样: 1. 分配一个足够大的新内存区域。 2. 在上面构造第 3 个对象。 3. 如果成功(没有异常),再移动/拷贝旧的对象。 4. 全部成功,则析构旧对象,释放旧对象的内存。 5. 如果 1 出现异常,直接抛出即可;如果 2–3 出现异常,则析构已成功构造的对象,释放新内存空间,继续抛出异常。 如果不是这个问题。请把问题阐释得更详细些。可以重新开一个新的评论。

    2019-12-06
    6
    7
  • 徐凯
    第一个问题 今天讲的大多是线性结构的容器,也可以说大多是非关联容器 第二个问题 应该不只是c++ 所有语言都提供了,之所以对其封装是便于使用,不需要用户自己去造轮子。同时有些容器内部有迭代器 与stl算法相结合可以便于实现泛型编程。c++委员会想让c++成为一个多元化的语言支持 面向对象 面向过程 泛型编程 第三个问题 将对容器的操作与获取值的操作分离开,用途会更明确。同时pop由于已经从容器中剔除了那个元素,那么返回的只能是个拷贝不允许返回已销毁元素的引用。这意味着需要一次拷贝构造操作。而top只需要返回指定元素的引用,高效简洁。将两次操作分开使得操作更明确同时没有额外开销。 个人见解 请老师赐教😃

    作者回复: 挺好。三比其他回答已经进一步了,但还是没有触及到某个关键字。

    2019-12-04
    2
    5
  • 农民园丁
    第三遍学习,产生一个困惑,请教吴老师: 采用不抛出异常的移动构造函数,会不会导致vector的内存不连续呢? 在上面的例子中,构造第3个Obj2对象时空间不足自动扩充,此时的空间为新分配的内存空间。 之后在新的空间第3个位置构造Obj2,然后将原空间第1、2个对象移动到新空间的第1、2个位置。 这个移动的过程是否只是将原空间第1、2个对象的指针移动到了新的空间?这样是不是新的vector空间内存布局就不连续了?

    作者回复: 首先,vector 的内存空间必然是连续的。 移动是移动对象,而不是指针。对象内部有什么,什么是合理的移动,由这个对象来定义。就我给出的例子,Obj2 大小为 1,所以移动就是把这个 1 字节的对象移动过去,执行的是 Obj2(Obj2&&)——真实的类就靠这个干活了,而我这里实际什么都没有做。

    2021-01-26
    2
    3
  • robonix
    老师,假如移动构造函数被声明为noexcept了,诱导编译器调用移动构造,而此时却又抛异常了,程序也会直接停止吗?

    作者回复: 对,缺省情况下,std::terminate 会被调用。

    2019-12-11
    3
  • 皓首不倦
    老师您好 第三个问题能不能这样理解 pop作用是弹出最后一个对象 弹出后该对象内存已经脱离容器当前所管理的有效的范围 虽然该片内存在后续有push操作时候还会被重复使用到 但是pop执行完后 该片内存逻辑层面看是暂时脱离了容器的管理范围的 显然pop不能将该片内存以引用方式传给外面 否则外部会持有一片目前脱离管理的无效内存 外部再对这片内存不论读还是写都是不合适的 所以pop如果要反返回对象 只能选择拷贝方式返回 会触发拷贝构造 对于内存占用大或者是需要进行深拷贝的对象而言 这个操作开销太大了 所以选择用top 返回可以安全访问的对象引用 而pop就单纯作为退栈操作不返回对象 我个人理解这样设计api 接口是为了避免不安全地访问内存 对比Java的 stack的 pop接口 Java的pop接口就返回了栈顶对象 因为这个对象内存托管给了jvm管理 调用端拿到了这个出栈的对象的引用也不会有访问内存的问题 但是c++如果把对象内存通过引用带给调用端 那调用端就可能直接读写容器内部的私有内存了 这片内存地址随时可能因为容器的扩容行为而变成野地址 对其访问其实并不安全 不知道我这样理解是否正确

    作者回复: Java是引用语义,返回对象就是返回个指针,没有任何问题。 C++是值语义,以前返回对象只能是拷贝,可能发生异常。一旦发生异常,对象已经被弹出,那它就彻底“丢失”了。

    2019-12-09
    2
    3
收起评论
显示
设置
留言
62
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部