C++中的deque容器

1.

deque容器属于双端数组，可以队它的头部和尾部进行插入数据的操作，在我们是使用vector的时候，对于头部的插入删除效率很低，当数据量很大的时候，这一点就表现得越发的明显，而相对而言deque对头部的插入删除速度就比vector快很多，但是vector访问元素的速度会比deque访问元素的速度快很多，这和他们的内部实现有关系.下图就很好展现了deque的特性

• deque内部工作原理：
  deque内部有个中控器，维护每段缓冲区的内容，缓冲区中存放真实数据。中控器维护每个缓冲区的地址，使得使用deque时像一片连续的内存空间：
  
• deque容器的迭代器支持随机访问
  deque构造函数

deque<int> dq; // 定义一个int类型的双端队列dq
deque<int> dq(10); // 定义一个int类型的双端队列dq，并设置初始大小为10
deque<int> dq(10, 20); // 定义一个int类型的双端队列dq，并设置初始大小为10且初始值都为20
deque<int> dq1(dq); // 定义并用双端队列dq初始化双端队列dq1
deque<int> dq1(dq.begin(), a.begin()+3); // 将双端队列dq中从第0个到第2个(共3个)作为双端队列dq1的初始值
1
2
3
4
5

• deque赋值：
  函数原型：
  deque& operator=(const deque &deq); //重载等号操作符

deque<int> dq; // 定义一个int类型的双端队列dq
deque <int> dq1 = dq;

1
2
3

• deque访问元素
  下标访问：dq[1]; // 并不会检查是否越界
  at 方法访问：dq.at(1); // 以上两者的区别就是 at 会检查是否越界，是则抛出 out of range 异常
  访问第一个元素：dq.front();
  访问最后一个元素：dq.back();

-deque插入元素
头部添加元素：dq.push_front(const T& x);
末尾添加元素：dq.push_back(const T& x);
任意位置插入一个元素：dq.insert(iterator it, const T& x);
任意位置插入 n 个相同元素：dq.insert(iterator it, int n, const T& x);
插入另一个向量的 [first,last] 间的数据：deq.insert(iterator it, iterator first, iterator last);

• deque 删除元素
  头部删除元素：dq.pop_front();
  末尾删除元素：dq.pop_back();
  任意位置删除一个元素：dq.erase(iterator it);
  删除 [first,last] 之间的元素：dq.erase(iterator first, iterator last);
  清空所有元素：dq.clear();

• deque交换两个同类型容器的元素：
  swap(deque&);

常用到的方法

assign()	它分配新内容并替换旧内容。
emplace()	它将在指定位置添加一个新元素。
emplace_back()	它在末尾添加一个新元素。
emplace_front()	它在双端队列的开头添加一个新元素。
insert()	它在指定位置之前添加一个新元素。
push_back()	它在容器的末尾添加一个新元素。
push_front()	它在容器的开头添加一个新元素。
pop_back()	它从双端队列中删除最后一个元素。
pop_front()	它从双端队列中删除第一个元素。
swap()	它交换两个双端队列的内容。
clear()	它将删除双端队列的所有内容。
empty()	它检查容器是否为空。
erase()	它删除元素。
max_size()	它确定双端队列的最大大小。
resize()	它改变了双端队列的大小。
shrink_to_fit()	它减少了内存以适合双端队列的大小。
size()	它返回元素数。
at()	它访问位置pos处的元素。
operator[]()	它访问位置pos处的元素。
operator=()	它将新的内容分配给容器。
back()	它访问最后一个元素。
begin()	它将迭代器返回到双端队列的开头。
cbegin()	它向双端队列的开头返回一个常量迭代器。
end()	它将迭代器返回到末尾。
cend()	它将常量迭代器返回到末尾。
rbegin()	它将反向迭代器返回到开头。
crbegin()	它将常量反向迭代器返回到开头。
rend()	它将反向迭代器返回到末尾。
crend()	它将常量反向迭代器返回到末尾。
front()	它访问最后一个元素。
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

验证代码

#include 
#include 
#include 
#include 

using namespace std;

class Person{
public:
	Person(string nam,int ag)
	{
		this->name = nam;
		this->age = ag;
	}
	
	string name;
	int age;
};

void print(deque <Person> &p)
{
	for(deque<Person>::iterator it = p.begin();it != p.end();it++)
	{
		cout << "name: "<< it->name <<"  age:  " << it->age<< endl;
	}
}

void test01(void)
{
	Person p1("张三",25);
	Person p2("李四",21);
	Person p3("王五",29);
	Person p4("刘二",22);
	Person p5("周八",23);
	Person p6("孙六",28);

	deque<Person> dq;
	dq.push_back(p1);
	dq.push_back(p2);
	dq.push_back(p3);
	dq.push_back(p4);
	dq.push_back(p5);
	dq.push_back(p6);

	cout << "dq: " << endl;
	print(dq);
	cout << "dq size: " << dq.size() <<endl; 
	cout << "dq max size" << dq.max_size() << endl;

	cout << "[] 访问：" << dq[0].name << dq[0].age << endl;
	cout << "insert后：" << endl;
	deque<Person>::iterator it = dq.begin();
	dq.insert(it+3,p1);
	print(dq);

	cout << "insert 4个p1后：" << endl;
	dq.insert(it+3,4,p1);
	print(dq);

	cout << " push front p4 后：  "<< endl;
	dq.push_front(p4); 
	print(dq);


	deque<Person> dq1 = dq;
	cout << "dq1:  "<<endl;
	print(dq1);
	cout << "dq1 size: " << dq1.size() <<endl; 

	deque <Person> dq2(6,p1);
	cout << "dq2:  "<<endl;
	print(dq2);
	cout << "dq2 size: " << dq2.size() <<endl; 
	
	cout << "/n assign dq3:" << endl;
	deque <Person> dq3(dq.begin(),dq.end());
	print(dq3);

	cout << "/n assign(n,elm) dq4:" << endl;
	deque <Person> dq4;
	dq4.assign(3,p3);
	print(dq4);

	cout << "pop front 操作"<<endl;
	dq.pop_front();
	print(dq);
	

	cout << "pop back 操作"<<endl;
	dq.pop_back();
	print(dq);
}

void print02(deque<int> &p)
{
	for(deque<int>::iterator it = p.begin();it != p.end();it++)
	{
		cout << *it <<  "  "; 
	}
	cout << endl;
}
void test02(void)
{
	deque<int> dq;
	
	for(int i = 0;i < 5; i++)
	{
		dq.push_front(i);
	}
	print02(dq);

	deque<int> dq1;
	for(int i = 0;i < 5; i++)
	{
		dq1.push_back(i);
	}
	cout << "dq1: "<<endl;
	print02(dq1);
	
	cout << "dq1 swap dq 后："<<endl;
	dq1.swap(dq);
	print02(dq1);
}

int main(void)
{
	test01();
	test02();

	return 0;
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131