设为首页 加入收藏

TOP

C++中STL容器的比较
2019-06-05 02:08:09 】 浏览:25
Tags:STL 容器 比较

容器特性:


vector:典型的序列容器,C++标准严格要求次容器的实现内存必须是连续的,唯一可以和标准C兼容的stl容器,任意元素的读取、修改具有常数时间复杂度,在序列尾部进行插入、删除是常数时间复杂度,但在序列的头部插入、删除的时间复杂度是O(n),可以在任何位置插入新元素,有随机访问功能,插入删除操作需要考虑。


deque(双端队列):序列容器,内存也是连续的,和vector相似,区别在于在序列的头部插入和删除操作也是常数时间复杂度,可以在任何位置插入新元素,有随机访问功能。


list :序列容器,内存是不连续的,任意元素的访问、修改时间复杂度是O(n),插入、删除操作是常数时间复杂度,可以在任何位置插入新元素。


set  :关联容器,元素不允许有重复,数据被组织成一棵红黑树,查找的速度非常快,时间复杂度是O(logN)


multiset:关联容器,和set一样,却别是允许有重复的元素,具备时间复杂度O(logN)查找功能


map :关联容器,按照{键,值}方式组成集合,按照键组织成一棵红黑树,查找的时间复杂度O(logN),其中键不允许重复。


multimap:和map一样,区别是键可以重复


分类:


连续内存容器:vector、deque


所以有数据插入和删除的时候,如果不是在序列的或者两端那么花费的代价是非常大的,因为需要保证连续内存,同时给新元素腾出空间或者填充删除元素的空间,如果存储的是复杂结构的话就要花费大量的时间进行拷贝操作(可以存储复杂结构的指针来弥补这个缺陷,这个讨论在另个总结中进行)


基于节点的容器:list、set、multiset、map、multimap


这样的容器在插入删除元素的时候修改的只是节点的指针,这样的消耗是非常小的。


考虑因素:
(1)需要大量添加元素:vector在大量添加元素的时候问题最大,list对这种情况的适应能力就非常好,deque(由多个内存块组成)前面说过了,他是vector和list的折衷形式,内存不够了就申请一块新的内存,但并不拷贝老的元素。


(2)查找速度:序列容器区分容器是否已排序,排序好的就是logn,没有的是最好是n,关联容器的话,存储的时候存储的是一棵红黑树(一种更为严格的平衡二叉树,文档最后有介绍

),总是能达到对数时间复杂度(O(logN))的效率,因为关联容器是按照键值排好序的。


(3)连续内存:如果想任意位置插入元素的话,还是不考虑vector、deque


(4)元素的排序:关联容易会按照某种等价关系排序


(5)内存是否和C兼容:vector兼容


所以优缺点是:


1.      Vector的数据模型就是数组。


优点:内存和C完全兼容、高效随机访问、节省空间


缺点:内部插入删除元素代价巨大、动态大小查过自身容量需要申请大量内存做大量拷贝。


2.      List的数据结构模型是链表


优点:任意位置插入删除元素常量时间复杂度、两个容器融合是常量时间复杂度


缺点:不支持随机访问、比vector占用更多的存储空间


3.      Deque的数据模型是数组和链表的折衷:


优点:高效随机访问、内部插入删除元素效率方便、两端push pop


缺点:内存占用比较高


4.      Map、set、multimap、multiset的数据结构模型是二叉树(红黑树)


优点:元素会按照键值排序、查找是对数时间复杂度、通过键值查元素、map提供了下标访问



编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++动态规划dp算法题 下一篇剑指offer中数据结构与算法部分笔..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }