首页 > 代码库 > Array,Vector,List,Deque的区别与联系【转+改】
Array,Vector,List,Deque的区别与联系【转+改】
数组
内存连续分配，长度大小固定，内置的最基础的数据结构之一。支持随机访问和随机存储。
该类型数据所占内存空间最小。
Vector
是C++ STL中的一个容器。和数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随机存取（即使用[]操作符访问其中的元素），但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝（复杂度是O(n)），另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。
Vector的原型定义如下。可以看到，作为一个容器，相比array附加了很多数据成员，因而从整体上而言，其内存空间占用较数组更多。但是仅仅就分配的连续的数组空间而言，和内置型数组占用空间大小基本一致。
// vector 基类 _Vector_base 定义template <class _Tp, class _Alloc> class _Vector_base {public: typedef _Alloc allocator_type; // 获取一个空间配置器对象 allocator_type get_allocator() const { return allocator_type(); } // 默认构造：没有指定初始节点个数 _Vector_base(const _Alloc&) : _M_start(0), _M_finish(0), _M_end_of_storage(0) {} // 构造函数：指定节点个数n _Vector_base(size_t __n, const _Alloc&) : _M_start(0), _M_finish(0), _M_end_of_storage(0) { // 分配 n 个节点所需空间 _M_start = _M_allocate(__n); // _M_start 指向起始位置 _M_finish = _M_start; // _M_finish 指向其实位置 _M_end_of_storage = _M_start + __n; // _M_end_of_storage指向内存末尾节点 } // 析构函数：释放内存空间 ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); } protected: _Tp* _M_start; // 指向第一个元素所在的节点 _Tp* _M_finish; // 指向最后一个元素所在节点的下一个节点 _Tp* _M_end_of_storage; // 可用内存空间的末尾节点 // 空间配置器 typedef simple_alloc<_Tp, _Alloc> _M_data_allocator; // 分配 n 个节点所需要的空间 _Tp* _M_allocate(size_t __n) { return _M_data_allocator::allocate(__n); } // 释放 n 个节点所对应的空间 void _M_deallocate(_Tp* __p, size_t __n) { _M_data_allocator::deallocate(__p, __n); }};
List
list是由数据结构中的双向链表实现的，因此它的内存空间可以是不连续的。因此只能通过指针来进行数据的访问，这个特点使得它的随机存取变的非常没有效率，需要遍历中间的元素，搜索复杂度O(n)，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。
其定义如下所示，很明显，除了数据域以外，还包含前向指针后后序指针，因而其耗费的空间比vector要大。
// ListNodeBase定义struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev;}; // ListNode定义template <class _Tp>struct _List_node : public _List_node_base { _Tp _M_data; // 数据域};
Deque
deque是双端队列，在队列头部和尾部可以快速的进行元素的插入和删除操作，相比vector而言有一定的优势，同时由于内部构造的设计，不存在vector那样扩充时带来的“配置新空间 / 移动旧数据 / 释放旧空间”问题。deque还提供Random Access Iterator，可以随机访问容器内的元素。deque同时还是STL中queue和stack的底层依赖组件。
下面的图片展示deque的内部结构设计。可以看到，deque拥有一个bitmap结构（称之为map），map中每一个元素指向一块连续的内存块，后者才是真正存储deque元素的地方，因为每个块都是固定大小的，但是每个块之间不要求是连续的，所以扩充空间的时候，就没有vector那样的副作用了。
deque的数据结构更为复杂，还包含了map节点，但是相比list每个节点均需要额外指针而言，其内存占用量还是较少。所以deque数据部分消耗的内存空间大小应该在vector和list之间。
需要说明的是，stack和queue的内部实现均基于deque实现，queue只能头删尾进，stack只能尾删尾进，这都是deque所支持的操作的特殊情况，或者说一个子集。
Array,Vector,List,Deque的区别与联系【转+改】