1. vector与deque
vector与动态数组相同,能够在插入或删除元素时自动调整自身大小,其存储由容器自动处理,vector
通常占用多于静态数组的空间,因为要分配更多的内存以管理将来的增长,在每次插入元素的时,仅当额外内存耗尽时触发重新分配。
如上图所示,vector
元素放置在连续存储中,以便可以使用迭代器访问和遍历他们。在vector
中,末尾插入需要不同的时间,因为有时候需要扩展存储空间。对于删除最后一个元素,因为不涉及存储空间大小的调整,则执行时间是恒定的。对于开头或者中间插入和擦除在时间上是线性的,因为可能要涉及到元素的移动。
deque是具有两端扩缩功能的序列容器。其存储方式与vector
相反,deque
的元素不是相接存储的,是由一段一段等长的连续空间构成的,各段之间并不一定是连续的。它的典型实现如下图所示,通过单独分配固定尺寸的序列(对应图中的数据区),外加额外的登记(对应图中map
映射区),map
数组中存储的是每段连续空间的地址,通过映射区来管理这些一段一段等长的连续空间,进而实现“整体连续”的效果。
当deque
容器需要在头部或者尾部增加空间的时候,它会申请一段新的连续空间,同时在map
数组的开头或者结尾添加指向该空间的指针,由此将deque
元素串接起来。在遇到空间不足的时候由于deque
可以申请新的连续空间,原数据空间可以保持不变,更新map
即可,所以deque
在涉及到空间扩展的时候,效率远高于vector
。
2. 性能比较
2.1 随机访问
由于vector
是连续存储的,deque
是分段连续存储,其随机访问需对map
数组进行二次指针解引用(可以理解为:deque
随机访问需要先去找到待访问元素在哪段连续存储空间,然后再对该空间进行下标访问),而vector
只有下标访问一次即可。因此在随机访问性能上,vector
略高于deque
,但两者复杂度均为常数
O
(
1
)
O(1)
O(1)。
2.2 末尾插入/删除
前面我们说过,vector
的存储是自动管理的,按需扩张收缩,vector
通常占用多于静态数组的空间,因为要分配更多的内存以管理将来的增长,通常情况下vector
在尾部插入元素的复杂度为
O
(
1
)
O(1)
O(1),但当额外内存耗尽的时候,需要重新分配,此时重新分配,是需要单独再申请一份更大空间,把vector
原有的元素重新放到新申请的空间上,再完成尾部插入,此时涉及到了新空间的申请、所有元素的移动和旧空间的释放,这种情况下的插入在性能上是灾难级别的,因此,总的来说对于vector
尾部插入的时间复杂度为均摊常数
O
(
1
)
O(1)
O(1)。
对于deque
由于存储空间是分段连续的,当空间不够的时候重新申请新的一段空间即可,不会涉及到旧元素的移动,其复杂度度为常数
O
(
1
)
O(1)
O(1)。对于尾部删除,因为不涉及到分配空间申请,因此两者的复杂度均在
O
(
1
)
O(1)
O(1)。
注:
vector
在尾部插入元素的时,新的size()
如果大于capacity()
,那么所有的迭代器和引用(包括end()
迭代器)都会失效,否则只有end()
迭代器会失效。而deque
除了迭代器会失效,而不会使指向其余元素的指针或引用失效。
2.3 随机插入/删除
vector
在进行随机插入的时候,涉及到插入位置到序列尾部这段元素的移动(可以理解为这段元素需要整体往后移动一位,给新插入元素把位置留出来),随机删除元素同理,因此其随机插入/删除的时间复杂度为插入位置与到vector尾部距离成线性
O
(
n
)
O(n)
O(n)。deque
的扩展方式是双向的,因此其可以**根据插入位置距离头部或者尾部较近的距离成线性
O
(
n
)
O(n)
O(n),**因此,其性能略胜vector
一丢丢。
注:对于
vector
随机插入,如果新size()
大于旧的capacity()
就会导致重分配,所有的迭代器和引用都会失效,否则,只有在插入点前的迭代器和引用会保持有效。对于deque
而言,所有迭代器和引用也会失效,除非插入位置为容器尾部或者头部,引用不会失效。
3. 总结
vector
和deque
的对比如下表所示:
vector | deque | |
---|---|---|
头文件 | 使用需要包含头文件<vector>
|
使用需要包含头文件<deque>
|
存储方式 | 连续存储元素 | 包含元素连续存储的内存快列表 |
随机访问 | 支持,复杂度为常数 O ( 1 ) O(1) O(1) | 支持,复杂度为常数 O ( 1 ) O(1) O(1) |
末尾插入/末尾删除元素 | 均摊常数 O ( 1 ) O(1) O(1) | 常数 O ( 1 ) O(1) O(1) |
随机插入/随机删除元素 | 与到vector 结尾的距离成线性
O
(
n
)
O(n)
O(n)
|
线性 O ( n ) O(n) O(n) |
vector
重分配在性能上是有开销的,如果在使用之前元素的数量已知,那么可以使用rederve()函数来消除重分配。
deque
的存储按需自动扩展及收缩,扩展deque
比扩张vector
更优,因为它不涉及到复制既存元素到新内存位置。但另外一方面,deque
典型地拥有较大的最小内存开销,所以当即使保有一个元素的时候,deque
也需要为它分配它的整个内部数组。文章来源:https://www.toymoban.com/news/detail-676028.html
文章首发公众号:iDoitnow如果喜欢话,可以关注一下文章来源地址https://www.toymoban.com/news/detail-676028.html
到了这里,关于vector VS deque的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!