C++ STL 之顺序存储结构 vector，list，deque异同

   C++中的容器类包括“顺序存储结构”和“关联存储结构”，前者包括vector，list，deque等；后者包括set，map，multiset，multimap等。若需要存储的元素数在编译器间就可以确定，可以使用数组来存储，否则，就需要用到容器类了。

1、vector介绍

   vector是一种连续存储结构，每个元素在内存上是连续的。它支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率比较低下；
   vector相当于一个数组，但是与数组的区别为：内存空间的扩展。vector支持不指定vector大小的存储，但是数组的扩展需要程序员自己写。

vector的内存分配实现原理：
   STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacity()函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储（VC++6.0是两倍，VS2005是1.5倍），所以这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
扩充空间（不论多大）都应该这样做：
（1）配置一块新空间
（2）将旧元素一一搬往新址
（3）把原来的空间释放还给系统
注：vector 的数据安排以及操作方式，与array 非常相似。两者的唯一差别在于空间的利用的灵活性。Array 的扩充空间要程序员自己来写。
vector类定义了好几种构造函数，用来定义和初始化vector对象:

 vector<T>  v1;       //vector保存类型为T的对象。默认构造函数v1为空。
 vector<T> v2(v1);    //v2是v1的一个副本。
 vector<T> v3(n, i);  //v3包含n个值为i的元素。
 vector<T> v4(n);     //v4含有值初始化的元素的n个副本。
1
2
3
4

2、deque

   deque也是连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于，deque提供了两级数组结构， 第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。因deque除了具有vector的所有功能外，还支持高效的首/尾端插入/删除操作。deque在功能上相当于合并vector和list。
deque 双端队列 double-end queue

优点：

• 随机访问方便，即支持[ ]操作符和vector.at()
• 在内部方便的进行插入和删除操作
• 可在两端进行push、pop

缺点：占用内存多

使用区别：
（1）如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
（2）如果你需要大量的插入和删除，而不关心随机存取，则应使用list
（3）如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque

#include 
#include 
#include 
#include 
 
using namespace std;
 
int main()
{
	deque<string> strDeq;
 
	strDeq.assign(4,string("CHINA"));
	strDeq.push_back("first_string");
	strDeq.push_front("last_string");
 
	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator<string>(cout," "));
	cout << endl;
	cout << endl;
 
	for(int i = 0;i < strDeq.size();++i)
		cout << "strDeq[" << i << "] : " << strDeq[i] << endl;
	cout << endl;
	
	for(int i = 0;i < strDeq.size();++i)
		cout << "strDeq.at(" << i << ") : " << strDeq.at(i) << endl;
	cout << endl;
 
	strDeq.pop_front();
	strDeq.pop_back();
 
	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator<string>(cout," "));
	cout << endl;
	cout << endl;
 
	for(int i = 1;i < strDeq.size();++i)
		strDeq[i] = "pre" + strDeq[i];
	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator<string>(cout," "));
	cout << endl;
	cout << endl;
 
	strDeq.resize(4,"resized string");
 
	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator<string>(cout," "));
	cout << endl;
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

3、list

   list是非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
优点：

• list 容器具有一些其它容器（array、vector 和deque）所不具备的优势，即它可以在序列已知的任何位置快速插入或删除元素（操作的时间复杂度为O(1)）。并且在 list容器中移动元素，也比其它容器的效率高
• 不使用连续内存完成动态操作
• 在内部方便的进行插入和删除操作
• 可在两端进行push、pop

缺点：

• 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
• 相对于verctor占用内存多

#include 
#include 
using namespace std;

int main() {
    // 创建一个没有任何元素的空 list 容器
    list<int> values1;

    // 创建一个包含 n 个元素的 list 容器，每个元素的值都为相应类型的默认值
    list<int> values2(5);

    // 创建一个包含 n 个元素的 list 容器，并为每个元素指定初始值
    list<int> values3(5, 1);

    // 通过拷贝创建
    list<int> values4(values3);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19