现代C++实战30讲
吴咏炜
前 Intel 资深软件架构师
立即订阅
3680 人已学习
课程目录
已更新 14 讲 / 共 30 讲
0/4登录后,你可以任选4讲全文学习。
课前必读 (2讲)
开篇词 | C++这么难,为什么我们还要用C++?
免费
课前必读 | 有关术语发音及环境要求
基础篇 (9讲)
01 | 堆、栈、RAII:C++里该如何管理资源?
02 | 自己动手,实现C++的智能指针
03 | 右值和移动究竟解决了什么问题?
04 | 容器汇编 I:比较简单的若干容器
05 | 容器汇编 II:需要函数对象的容器
06 | 异常:用还是不用,这是个问题
07 | 迭代器和好用的新for循环
08 | 易用性改进 I:自动类型推断和初始化
09 | 易用性改进 II:字面量、静态断言和成员函数说明符
提高篇 (3讲)
10 | 到底应不应该返回对象?
11 | Unicode:进入多文字支持的世界
12 | 编译期多态:泛型编程和模板入门
现代C++实战30讲
登录|注册

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

吴咏炜 2019-12-04
你好,我是吴咏炜。
上几讲我们学习了 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/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《现代C++实战30讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(33)

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

    作者回复: 3的正解终于出现,有人说到“异常安全”了。👍

    再说两句,这是C++98时设计的接口,没有移动就只能那样。有了移动,在多线程的环境里,移动返回加弹出实际上就变得有用了。我对复杂和可读性部分不那么同意。

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

    作者回复: 很棒👌。

    异常安全是关键。

    2019-12-04
    13
  • 禾桃
    请教一个问题,
    #1
    为什么一定强制移动构造函数不要抛出异常?
    移动构造函数抛出异常后,catch处理不可以吗?

    #2
    为什么拷贝构造函数被允许抛出异常?

    能麻烦给些代码说明一下吗?

    非常感谢!

    作者回复: catch住也没有用了。仔细想一下,我现在要把vector里的两个对象移到一个新的vector,移第一个成功,第二个时有异常,然后vector该怎么办?现在两个vector都废掉了。

    拷贝不影响旧的容器。即使发生异常,至少老的那个还是好的。这就是异常安全。

    2019-12-05
    8
  • 徐凯
    第一个问题 今天讲的大多是线性结构的容器,也可以说大多是非关联容器

    第二个问题 应该不只是c++ 所有语言都提供了,之所以对其封装是便于使用,不需要用户自己去造轮子。同时有些容器内部有迭代器 与stl算法相结合可以便于实现泛型编程。c++委员会想让c++成为一个多元化的语言支持 面向对象 面向过程 泛型编程

    第三个问题 将对容器的操作与获取值的操作分离开,用途会更明确。同时pop由于已经从容器中剔除了那个元素,那么返回的只能是个拷贝不允许返回已销毁元素的引用。这意味着需要一次拷贝构造操作。而top只需要返回指定元素的引用,高效简洁。将两次操作分开使得操作更明确同时没有额外开销。

    个人见解 请老师赐教😃

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

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

    作者回复: 关于几次拷贝/移动的问题?参考 hello world 的评论下的廖熊猫的回答:

    在插入的时候,你会发现空间不够了,然后开辟新的空间,在新空间先把最后插入的元素放好,然后再依次把以前的元素一个一个挪过来。空间不够的话最后一个元素是没法插入进去的啊,所以没办法移动三次的。

    还有我自己的回答:

    两者都是要构造第 3 个对象时空间不足,需要这样:

    1. 分配一个足够大的新内存区域。
    2. 在上面构造第 3 个对象。
    3. 如果成功(没有异常),再移动/拷贝旧的对象。
    4. 全部成功,则析构旧对象,释放旧对象的内存。
    5. 如果 1 出现异常,直接抛出即可;如果 2–3 出现异常,则析构已成功构造的对象,释放新内存空间,继续抛出异常。

    如果不是这个问题。请把问题阐释得更详细些。可以重新开一个新的评论。

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

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

    2019-12-11
    1
  • 花晨少年
    如果不修改字符串的内容,使用 const string& 或 C++17 的 string_view 作为参数类型。后者是最理想的情况,因为即使在只有 C 字符串的情况,也不会引发不必要的内存复制
    -----------------
    没有理解,“只有 C 字符串的情况,也不会引发不必要的内存复制”,对于string_view相对于const string&,能否简单举个例子

    作者回复: 只有const char*,目标是const string&,会引发一个临时string的构造,会导致内存复制。

    用string_view当然也会产生临时对象,但string_view不会复制字符串的内容。

    2019-12-07
    1
  • robonix
    老师,文中提到使用v1.push_back会额外生成临时对象,多一次拷贝构造和一次析构。是不是应该改为多一次移动构造和析构呢?

    作者回复: 这个疑问提得好👍。在目前这个例子里,确实是移动构造而不是拷贝构造。

    2019-12-16
  • 凌云
    int main()
    {
    vector<Obj1> v1;
    //v1.reserve(2);
    v1.emplace_back();
    v1.emplace_back();
    v1.emplace_back();
    }
    输出:
    Obj1()
    Obj1()
    Obj1(const Obj1&)
    Obj1()
    Obj1(const Obj1&)
    Obj1(const Obj1&)
    "vector 适合在尾部操作,这是它的内存布局决定的。只有在尾部插入和删除时,其他元素才会不需要移动,除非内存空间不足导致需要重新分配内存空间",讲义中的例子,如果未调用reserve,那么是构造,构造,拷贝构造,构造,然后是2次拷贝构造,那么重新分配内存空间的意思是,当指定的空间不足以放下所有元素时,会将前面的元素拷贝一遍?

    作者回复: 会将前面的元素拷贝或移动一遍。

    移动的条件文中提到了,元素类型需要“提供一个保证不抛异常的移动构造函数”。

    2019-12-15
  • 神秘的火柴人
    老师,文中:

    stack
    类似地,栈 stack 是后进先出(LIFO)的数据结构。
    queue 缺省也是用 deque 来实现,但它的概念和 vector 更相似。它的接口跟 vector 比,有如下改变:

    这里queue缺省是不是笔误了,应该是stack吧

    作者回复: 多谢多谢。已经修复。

    2019-12-13
  • Alice
    谢谢老师的回复,老师您说“扩充空间是一个编译器自发进行的操作,没有用户控制。一般会类似于reserve(size() * 2)”,我之前没有遇到过这个知识点,那老师我应该看点什么稍微补充一下这块知识?

    作者回复: https://www.cnblogs.com/skyfsm/p/7488053.html

    这篇中文文章说得还比较清楚,可以看一下。

    2019-12-12
  • Alice
    老师 vector obj1演示代码里,在构造第三个元素发现空间不够之后,v1会按我们之前设定好的自动调用v1.reserve(2)来扩充空间,是这个意思嘛?

    作者回复: 不是。执行 v1.reserve(2) 之后,空间大小就是 2 了。扩充空间是一个编译器自发进行的操作,没有用户控制。一般会类似于 reserve(size() * 2)。

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

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

    2019-12-11
  • hdongdong123
    老师给的工具xeus-cling为啥第二次运行的时候就报错error: redefinition of 'str'

    作者回复: 就像你在代码里对 str 定义两次一样啊。这仍然是 C++,不是 Python。

    Restart kernel 可以重新来。

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

    作者回复: Java是引用语义,返回对象就是返回个指针,没有任何问题。

    C++是值语义,以前返回对象只能是拷贝,可能发生异常。一旦发生异常,对象已经被弹出,那它就彻底“丢失”了。

    2019-12-09
    1
  • 花晨少年
    老师请问 "在元素大小较小的情况下,forward_list 能节约的内存是非常可观的"
    这句话怎么理解呢,元素大小较小的情况下,是指的元素数量小,还是元素本身的值偏小呢。

    作者回复: 指单个元素的大小,sizeof。

    2019-12-08
  • 总统老唐
    吴老师,关于 vector 的 emplace_back 有2点疑问:
    1,我的理解,v1 的内存空间是在栈上分配的,当 v1 的capacity达到最大值时,需要给 v1 重新分配空间才能存放新的对象,因为栈帧是连续内存空间,那么不管是从高到低还是从低到高,已经分配的地址,比如v1[0],应该不变,但是查看v1[0]的地址,发现有变化,看起来第三次 emplace_back 导致 v1 的地址变化了,这样一来,原来存放v1[0] 和 v1[1] 的栈空间不就空了吗,那是不是导致了栈的内存空间不连续了?
    2,第三次 emplace_back 的打印信息显示,先调用了构造函数,再调用拷贝函数,是不是表示,当 v1 获得新地址后,是先在新的 v1[2] 上构造新对象,再把原来 v1[0] 和 v1[1] 中的对象拷贝过来?

    作者回复: 上来就错了。大部分容器都是在堆上分配空间的……

    2 正确。内存分配成功,新对象构造成功,才移动/拷贝旧对象。

    2019-12-06
  • 虫 二
    1.本章节大部分都是非关联容器
    2.各容器效率不同,为了方便使用应用在不同的场景之中
    3.在某些特定情况下会引发异常问题

    作者回复: 可以。够言简意赅的。

    2019-12-04
  • 1.线性容器
    2.由于不同场景下需要有合适的数据结构与之对应,比如既然有了deque为何会有queue和stack呢,queue和stack的功能deque也能实现,而且甚至比queue和stack具有更大的自由,这是由于在很多情况下接口的自由使得犯错误的几率也就变大,因此将大多数接口都封装起来来减小出错的可能性。以及链表、数组都存在也是因为他们都具有不可代替的一面。
    3.JAVA中确实是当pop时返回被pop的值,而C++中并没有返回该值,我认为很大程度上是由于C++更注重效率,毕竟这样做可以减小一次拷贝或者移动,当容器中存储的对象拷贝或移动很费劲或者多次pop时,这将大大降低C++的pop速度。另外我认为可能和异常的避免有关,由于如果需要返回被pop的值,需要提前将其拷贝到其他地方或者是移动到其他地方,这两者都可能需要内存的分配,所以可能会出现异常。第二点纯属脑洞,不清楚自己考虑的对不对,希望老师指正。。。

    作者回复: 还是重点谈3。对于C++的情况,基本没问题。对于Java,则错了。Java的情况最接近于你返回一个智能指针——这个操作本身性能是没问题的。主要约束是必须在堆上放置对象。

    2 你对防犯错的考虑非常好。其他人似乎没提到。👍

    2019-12-04
收起评论
33
返回
顶部