专栏首页算法时空STL里的容器区别

STL里的容器区别

小结 我们常用到的STL容器有vector、list、deque、map、multimap、set和multiset,它们究竟有何区别,各自的优缺点是什么,为了更好的扬长避短,提高程序性能,在使用之前需要我们了解清楚。


verctor vector类似于C语言中的数组,它维护一段连续的内存空间,具有固定的起始地址,因而能非常方便地进行随机存取,即 [] 操作符,但因为它的内存区域是连续的,所以在它中间插入或删除某个元素,需要复制并移动现有的元素。此外,当被插入的内存空间不够时,需要重新申请一块足够大的内存并进行内存拷贝。值得注意的是,vector每次扩容为原来的两倍,对小对象来说执行效率高,但如果遇到大对象,执行效率就低了。 list list类似于C语言中的双向链表,它通过指针来进行数据的访问,因此维护的内存空间可以不连续,这也非常有利于数据的随机存取,因而它没有提供 [] 操作符重载。 deque deque类似于C语言中的双向队列,即两端都可以插入或者删除的队列。queue支持 [] 操作符,也就是支持随机存取,而且跟vector的效率相差无几。它支持两端的操作:push_back,push_front,pop_back,pop_front等,并且在两端操作上与list的效率 也差不多。或者我们可以这么认为,deque是vector跟list的折中。 map map类似于数据库中的1:1关系,它是一种关联容器,提供一对一(C++ primer中文版中将第一个译为键,每个键只能在map中出现一次,第二个被译为该键对应的值)的数据处理能力,这种特性了使得map类似于数据结构里的红黑二叉树。 multimap multimap类似于数据库中的1:N关系,它是一种关联容器,提供一对多的数据处理能力。 set set类似于数学里面的集合,不过set的集合中不包含重复的元素,这是和vector的第一个区别,第二个区别是set内部用平衡二叉树实现,便于元素查找,而vector是使用连续内存存储,便于随机存取。 multiset multiset类似于数学里面的集合,集合中可以包含重复的元素。


小结 在实际使用过程中,到底选择这几种容器中的哪一个,应该根据遵循以下原则: 1、如果需要高效的随机存取,不在乎插入和删除的效率,使用vector; 2、如果需要大量的插入和删除元素,不关心随机存取的效率,使用list; 3、如果需要随机存取,并且关心两端数据的插入和删除效率,使用deque; 4、如果打算存储数据字典,并且要求方便地根据key找到value,一对一的情况使用map,一对多的情况使用multimap; 5、如果打算查找一个元素是否存在于某集合中,唯一存在的情况使用set,不唯一存在的情况使用multiset。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 入门编程,一定要从C语言开始吗?

    很多小伙伴在入门编程时,都是从咱们老九学堂的C语言课程开始的,但最近有的小伙伴问我,学编程一定要从C语言开始吗?直接学习JAVA可以吗?

    老九君
  • 最难学的十大编程语言 Java排第三 它竟是第一名!

    编程语言是开发者们代码工作的核心,也是许多开发者最爱讨论的话题。编程语言的选择对开发者和工具制造商都十分重要,前者需要保持最新和具备市场潜力的技能,后者则亟需确...

    老九君
  • 字节跳动EE部门前端面试经历及总结

    你好,我是星辉,幸会幸会。 今天下午我参加了字节跳动EE部门的前端视频第一次面试,把它记录总结下来,希望能够对大家带来帮助。

    星辉
  • 高端内存映射之kmap_atomic固定映射--Linux内存管理(二十一)

    linux高端内存中的临时内存区为固定内存区的一部分, 对于固定内存在linux内核中有下面描述

    233333
  • 编程语言中,c#、Python、JavaScript哪一个更接近c语言?

    不要尝试比较几种编程语言的优劣,任何一种编程语言都有其存在的价值,适合的就是最好的,现在编程领域Python,JAVA等等发展势头非常迅猛,但并不意味着所有的企...

    程序员互动联盟
  • 小甲鱼《零基础学习Python》课后笔记(二):用Python设计第一个游戏

    BIF(Built-in Functions)是Python的内置函数,为了方便程序员快速编写脚本程序。

    小火柴棒
  • 谈谈iOS获取调用链

    iOS开发过程中难免会遇到卡顿等性能问题或者死锁之类的问题,此时如果有调用堆栈将对解决问题很有帮助。

    fanspring
  • 为什么C语言诡异离奇、缺陷重重,却获得了巨大的成功?

    已经使用了C语言十几年了,今天还在写C语言代码,C语言算是很多编程语言祖师爷了,已经取得了巨大的成功但还是很多人对于C语言存在很大的偏见,觉得C语言里面很多语法...

    程序员互动联盟
  • 我与Android过往,从此更需努力,揭开新的篇章。

           早就写篇关于自己从接触Android到现在的文章,怕是更多的心灵鸡汤,或者自己的侃侃而谈,今天,在南京工作的倒数第二天,提笔写来,希望能够结识更多...

    黄林晴
  • Golang学习笔记之错误处理error、panic (抛出错误),recover(捕获错误)

    错误表示程序中出现了异常情况。Go 语言通过内置的错误接口提供了非常简单的错误处理机制。

    李海彬

扫码关注云+社区

领取腾讯云代金券