C++中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的数据结构模型是二叉树(红黑树)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/f140e47a650033820af26c69c0ddf5f8.html