罗剑锋的 C++ 实战笔记
罗剑锋
前奇虎 360 技术专家,Nginx/OpenResty 开源项目贡献者
34779 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 32 讲
结束语 (1讲)
罗剑锋的 C++ 实战笔记
15
15
1.0x
00:00/00:00
登录|注册

12 | 三分天下的容器:恰当选择,事半功倍

你好,我是 Chrono。
今天我要讲的是标准库里的一块“重地”:容器,它也是 C++ 泛型编程范式的基础。
不过在正式开讲之前,我先问你个问题:什么是容器?
你也许会说:容器,就是能够“容纳”“存放”元素的一些数据结构
这个回答非常正确,而且说到了“点”上。
还记得计算机先驱的那句经典名言吗?“算法 + 数据结构 = 程序。”在 C++ 里,容器就是这个公式里面的“数据结构”。
所以,下面我就着重从数据结构的角度,来谈谈各种容器的区别、优缺点,还有如何选择最合适的容器。

认识容器

所谓的数据结构,就是数据在计算机里的存储和组织形式,比如堆、数组、链表、二叉树、B+ 树、哈希表,等等。
在计算机的发展历史上,众多“大牛”孜孜不倦地发明创造了这么多的数据结构,为什么呢?
因为没有一种数据结构是万能的、可以应用于任何场景。毕竟,不同的数据结构存储数据的形式不一样,效率也就不一样。有的是连续存放,有的是分散存放,有的存储效率高,有的查找效率高,我们必须要依据具体的应用场合来进行取舍。
我想,你肯定已经学过这些数据结构了,也知道它们的实现原理,自己写也不是什么太难的事情。
但是,对于最基本、最经典的那些数据结构,你完全没有必要去“自己造轮子”,因为 C++ 标准库里的容器就已经把它们给实现了。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《罗剑锋的 C++ 实战笔记》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(38)

  • 最新
  • 精选
  • EncodedStar
    这节课把容器简直讲活了,最后的小技巧很实用,nice

    作者回复: thanks。

    22
  • 泰伦卢
    关于vector扩容机制,建议加个平台前置条件,windows和linux系统的stl vector平台的扩容倍数是不一样的,而且移动端平台也有好多种stl,有gnustl和c++sharedstl等,不清楚具体实现,可能也会有所区别!

    作者回复: 感谢补充,在Linux下习惯了,不太关注其他平台。

    12
  • Eason Tai
    有一说一,配合c++ prime和自己手敲来看专栏,互相验证,真的挺舒服的。

    作者回复: 很好的学习方法,nice。

    11
  • 文中说key必须具备两个条件,其中第二个条件, "第二个则是因为 hash 值可能会冲突,所以当 hash 值相同时,就要比较真正的 key 值", 当hash值一样时,直接把新添加的元素添加到hash值相等的队列后边不就行了吗?为什么再比较key值呢? 这里,比较key值有什么用处吗?比较了之后可以用来做什么呢?没明白这里的意思,老师可以稍微解释一下吗?

    作者回复: 举个例子吧,比如说用string作为key,abc和cba,两者的hash值是相同的,都放进了一个开链表里,但这两个元素显然是不同的,真正要找cba就必须在这个链表里取比较查找。 关键在于hash值相等不代表key就一定相等,因为hash值只是一个映射,还必须去比较真正的实体。

    2
    6
  • Wei Zhou
    return std::hash()(p.x) 第一个括号是什么意思 ?

    作者回复: std::hash是一个类,所以std::hash()就是构造函数,创建了一个临时对象,而std::hash又重载了operator(),所以这个临时对象可以像函数一样调用。 这是c++里函数对象的常见用法,第一次见可能会有点理解困难。

    5
  • 逆风翻盘我可以
    多利用类型别名,而不要“写死”容器定义。老师,这句话能给个例子嘛?

    作者回复: 比如: using data_type = map<int,string>; 这样,在代码里用data_type,而不是直接的map类型,以后可以随时改变data_type的定义,比如换成: using data_type = unordered_map<int,string>;

    5
  • java2c++
    问题1:所有的容器都是为了用来存放元素,理论上直接用数组就可以了,但是增删改查的效率未必如你所愿了。所以标准库又搞了那么多容器是为了满足各个不同的使用场景。 增删改查效率最高的underd_set,时间复杂度是O(1) ,不过它是无序的,另外不能按下标查询。 其次是红黑树,跳表,时间复杂度是O(logN)。 相对于array它们共同的优点是不需要显性扩容,底层都处理好了

    作者回复: 说的很好。 注重查询效率通常就会选择无序容器,但还有其他很多时候容器注重的是存储,所以就可以选择array、vector,等全存完了之后再排序查找。

    5
  • 无为而立
    顺便复习了下,deltype哈哈,感觉把它当成函数更好理解

    作者回复: 说得对,也可以把它理解成是编译阶段的函数,计算表达式的类型。

    5
  • 木瓜777
    如果使用unorder_map,对自定义的结构,例如 struct Point {float x;float y},该如何实现hash?对多个float 有没有好的hash方法?

    作者回复: 可以使用标准库里的std::hash函数对类成员逐个hash。 但浮点数不建议用hash,它不精确。

    3
  • l c
    老师您好, 对于这里 auto comp = [](auto a, auto b) // 定义一个lambda,用来比较大小 { return a > b; // 定义大于关系 }; 之前一般我都是直接用一般函数写的,请问使用lambda的优势在哪里呢?

    作者回复: 简单方便,就地定义,不像普通函数,需要跑到源码文件前面去写,局部化更好理解和维护。

    2
收起评论
显示
设置
留言
38
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部