发音

deque 
/dek/ O /dEk/ O

和vector相似,但是可以在两端进行插入删除,支持随机访问。

为了实现两端的插入和删除,deque的内存实现为一组独立区块,第一区块朝一个方向扩展,最末区块朝另一个方向扩展。

需要头文件<deque>

位于命名空间std,定义如下:

template <class Type, class Allocator =allocator<Type>>
class deque

参数:

第一个参数是要存储在 deque 中的元素数据类型

第二个参数为所存储分配器对象的类型,该分配器对象封装有关 deque 的内存分配和解除分配的详细信息。 此参数是可选的, 默认值为 <分配器类型 > 。

deque与vector功能的差异

  • deque元素访问和迭代器动作稍慢,因为有一个间接过程
  • deque的迭代器一定是智能指针
  • 在内存有限制的系统内deque可以用多个区块所以能有更多元素
  • deque的插入和删除操作,除了在头尾两端,都会让其中元素的任何已存在的引用,迭代器和指针失效。
  • deque的内存重分配优于vector,不用复制全部元素。
  • deque会释放不再使用的内存块。

可以优先选用deque的场景

  1. 需要在两端插入删除
  2. 不需要指向容器内元素
  3. 有需求要求不再使用的元素释放(c++标准不保证此项)

操作函数

操作 效果
deque<Elem> c 默认构造,空的queue
deque<Elem> c(c2) 复制构造
deque<Elem> c = c2 同上
deque<Elem> c(rvalue) move构造,c11
deque<<Elem> c = rvalue 同上,c11
deque<Elem> c(n) 默认构造生成一个大小为n的queue
deque<Elem c(n,elem) 初始化一个大小为n,每个元素都是elem的queue
deque<Elem> c(begin,end) 初始化一个queue,元素是begin和end的范围
deque<Elem> c(initlist) 以初始化列进行初始化,c11
deque<Elem> c = initlist 同上
c.~deque() 销毁所有元素,释放内存

与vector不同的两点操作:

  1. 不提供容量操作,如capacity(),sreserve()
  2. deque直接提供函数完成头部的插入删除,push_front(),pop_front()

c++11添加了函数shrink_to_fit(),缩小内存以匹配元素个数,但没有强制力。会释放掉deque本身不会释放的用于存储指针的空间。

非变动性操作

操作 效果
c.empty() 返回是否为空
c.size() 返回当前容器内元素数量
c.max_size() 返回容器最大的可能元素数量
c.shrink_to_fit() 减少容器内存来符合元素数量,c11
c1 == c2  
!=  
>  
<  
>=  
<=  
c[index] 返回索引所指的元素
c.at(index) 会检查范围,返回索引指向的元素,超过范围会抛出异常
c.front() 返回第一个元素,不检查是否存在第一个元素
c.back() 返回最后一个元素,也不检查
c.begin() 返回指向第一个元素的迭代器
c.end() 返回指向最后一个元素的迭代器
c.cbegin() 返回一个const的指向第一的迭代器,c11
c.cend() const,最后,c11
c.rbegin() 看例子,返回该deque的反向的deque的第一个元素的迭代器
c.rend() 和上面那个类比一下
c.crbegin() 上上面那个再加个const
c.crend()  

c.rbegin()

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
// deque_rbegin.cpp
// compile with: /EHsc
#include <deque>
#include <iostream>
 
int main()
{
	using namespace std;
	deque <int> c1;
	deque <int>::iterator c1_Iter;
	deque <int>::reverse_iterator c1_rIter;
 
	// If the following line had replaced the line above, an error
	// would have resulted in the line modifying an element
	// (commented below) because the iterator would have been const
	// deque <int>::const_reverse_iterator c1_rIter;
 
	c1.push_back(10);
	c1.push_back(20);
	c1.push_back(30);
 
	c1_rIter = c1.rbegin();
	cout << "deque中的最后一个元素是" << *c1_rIter << "." << endl;
 
	cout << "deque中都有这些元素: ";
	for (c1_Iter = c1.begin(); c1_Iter != c1.end(); c1_Iter++)
		cout << *c1_Iter << " ";
	cout << endl;
 
	// 可以使用rbegin以相反的顺序遍历deque
	cout << "反序的deque是: ";
	for (c1_rIter = c1.rbegin(); c1_rIter != c1.rend(); c1_rIter++)
		cout << *c1_rIter << " ";
	cout << endl;
 
	c1_rIter = c1.rbegin();
	*c1_rIter = 40;  // 如果如上所述声明了const_reverse迭代器,则会导致错误
	cout << "现在deque的最后一个元素是 " << *c1_rIter << "." << endl;
}
deque 的 后 一 《 元 素 是 30 . 
de “ 都 者 这 些 元 素 : 10 20 30 
30 20 10 
在 qu 的 后 一 个 元 素 是


是很好理解的

注意:

除了at(),没有任何成员函数检查索引或者迭代器是否有效

元素的插入和删除可能导致内存重新分配,会使所有的指向deque元素的指针,索引和迭代器失效,除非是在头尾进行该操作,在前面已经强调过了。

另外,即使是在头尾进行插入删除也会使原本指向首尾的迭代器失效。

变动性操作

操作 效果
c = c2 赋值
c = rv 将右值rv的所有元素move assign的方式给c,c11   
c = initlist 将初值列的值赋给c
c.assign(n,elem) 将n个elem的值赋给c的对应n个元素
c.assign(begin,end) 将[begin,end)的元素给c
c.assign(initlist) 将初值列的所有元素给c
c1.swap(c2) c1,c2置换
swap(c1,c2) 同上,全局函数
c.push_back(elem) 在尾部插入elem
c.pop_back() 移除尾部的元素,不返回
c.push_front(elem) 在头部插入一个elem
c.pop_front() 移除头部的元素,不返回
c.insert(pos,elem) 在pos的位置前插入elem,并返回新元素的位置
c.insert(pos,n,elem) 在pos前插入n个elem,并返回第一个新元素的位置
c.insert(pos,begin,end) 在pos前插入范围并返回第一个元素的位置
c.insert(pos,initlist) 在pos前插入initlist内的元素并返回第一个新元素的位置,c11
c.emplace(pos,args…) 在pos前插入一个以args为初值的元素,并返回新元素的位置,C11
c.emplace_back(args…) 在末尾附加一个以args为初值的元素,不返回,C11
c.emplace_front(args…) 在起点前插入一个以args为初值的元素,不返回,C11
c.erase(pos) 移除pos位置的元素,并返回下一个元素的位置
c.erase(begin,end) 移除begin和end范围内的元素,返回下一个元素位置
c.resize(num) 将元素数量改为num,如果size变大,多出的位置进行默认构造
c.resize(num,elem) 和上面的类似,但是多出来的元素是elem
c.clear() 清空容器

运行实例:

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
#include <iostream>
#include <deque>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;
 
int main()
{
	//初始化一个空的deque,元素类型为string
	deque<string> coll;
 
	//插入几个元素
	coll.assign(3, string("string"));
	coll.push_back("last string");
	coll.push_front("first string");
 
	//打印
	copy(coll.cbegin(), coll.cend(), ostream_iterator<string>(cout, "\n"));
	cout << endl;
 
	//移除第一个和最后一个元素
	coll.pop_front();
	coll.pop_back();
 
	//在除了第一个元素前的每一个位置插入“another”
	for (unsigned i = 1; i < coll.size(); ++i)
	{
		coll[i] = "another" + coll[i];
	}
 
	//将容器数量变为4个
	coll.resize(4, "resized string");
 
	//打印元素
	copy(coll.cbegin(), coll.cend(), ostream_iterator<string>(cout, "\n"));
 
	return 0;
}