【C++】STL03-deque

概念

1. 在有一个中央控制区map，它是一个存储指针的指针。它存储的是分段的一些数据的地址。将它们连接起来，形成了表象上的连续，实际上是分段。
2. 可以从两端插入删除，也可以通过索引访问元素
3. 对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector当中，对vector进行排序，再复制回deque。
4. deque是在功能上合并了vector和list。
5. 迭代器包含四部分。分别是该段地址的前后边界、当前数据的地址、一个是map。嗯嗯嗯。

与vector区别

1.deque可以在头部对元素进行插入和删除。push_front、pop_front。
2.deque没有容量的概念，因为它是动态的，以分段连续空间组合而成，随时可以增加一段新的空间并连接起来。没有capacity()和reverse()功能。
3.在访问元素时deque容器速度比vector容器速度慢

优点

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

① 与vector比较：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
② 与list比较：其底层是连续空间，空间利用率比较高，不需要存储额外字段。

缺点

(1) 占用内存多
(2)不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，不适合大量的头部和中间插入删除，也不适合大量的随机访问。而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

操作

大部分函数与vector一样，多了push_front、pop_front。

void test01() {
	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_back(30);
	d.push_back(40);

	printDeque(d);
//=======赋值========
	deque<int> d1;
	d1 = d;
	d1.assign(d.begin(), d.end());

	cout << d1.empty() << endl;
	cout << d1.size() << endl;

	d1.push_front(20);
	d1.push_front(10);

	d1.pop_back();	// 尾删
	d1.pop_front();	// 头删

	d1.insert(d.begin(), 1000);

	d1.erase(d.begin());

	d1.clear();

	printDeque(d1);
}
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