一.deque

• 适用于既要频繁随机访问，又要关心两端数据的插入与删除的场景。

一.deque简介

deque是双向开口的连续性存储空间。虽说是连续性存储空间，但这种连续性只是表面上的，实际上它的内存是动态分配的，它在堆上分配了一块一块的动态储存区，每一块动态存储去本身是连续的，deque自身的机制把这一块一块的存储区虚拟地连在一起。
它首次插入一个元素，默认会动态分配512字节空间，当这512字节空间用完后，它会再动态分配自己另外的512字节空间，然后虚拟地连在一起。deque的这种设计使得它具有比vector复杂得多的架构、算法和迭代器设计。它的性能损失比之vector，是几个数量级的差别。所以说，deque要慎用。

二.deque特性

deque是连续线性空间。但这种连续不同于数组和vector的连续，deque只是逻辑上的连续空间，它把一块一块独立的空间逻辑地连在一起，仿佛整个deque空间是一块完整的连续空间
deque容器是C++标准模版库(STL,Standard Template Library)中的部分内容。deque容器类与vector类似，支持随机访问和快速插入删除，它在容器中某一位置上的操作所花费的是线性时间。与vector不同的是，deque还支持从开始端插入数据
支持随机访问，即支持[]以及at()，但是性能没有vector好。
可以在内部进行插入和删除操作，但性能不及list。

(1).deque与vector的不同

1、两端都能够快速插入和删除元素。vector只能在尾端进行。

2、deque的元素存取和迭代器操作会稍微慢一些。因为deque的内部结构会多一个间接过程。

3、迭代器是特殊的智能指针，而不是一般指针。它需要在不同的区块之间跳转。

4、deque可以包含更多的元素，其max_size可能更大。因为不止使用一块内存。

5、不支持对容量和内存分配时机的控制。

6、deque的内存区块不再被使用时，会被释放。deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实作版本定义。

(2)deque和vector相似的特性：

1、在中间部分插入和删除元素相对较慢，因为所有元素都要被移动。

2、迭代器属于随即存取迭代器。

最好采用deque的情形：

1、需要在两端插入和删除元素。

2、无需引用容器内的元素。

3、要求容器释放不再使用的元素。

三.基本函数实现

使用前添加函数头#include<deque>

1.构造函数

• deque<Elem> c 创建一个空的deque

deque<int > q;创建int型数据，队列名为q

• deque<Elem> c1(c2) 复制一个deque。

deque<int >q1;
deque<int >q2(q1);

• deque<Elem> c(n) 创建一个deque，含有n个数据，数据均已缺省构造产生。

deque<int >q(5);

• deque<Elem> c(n, elem) 创建一个含有n个elem拷贝的deque。

deque<int >q(2,2);
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:2 2

• deque<Elem> c(beg,end) 创建一个以[beg;end)区间的deque。

	deque<int >q;
deque<int >q2(q.begin(),q.end());

• ~deque<Elem>() 销毁所有数据，释放内存

2.添加函数

• deque.push_back(elem); //在容器尾部添加一个数据

deque<int >q(2,2);
q.push_back(1);
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:2 2 1

• deque.push_front(elem); //在容器头部插入一个数据

deque<int >q(2,2);
q.push_front(1);
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:1 2 2

• emplace(); //在队列指定的元素位置前插入新的元素
• emplace_back(); //在队列尾部增加新的元素

deque<int >q(2,2);
q.emplace_back(1);
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:2 2 1

• emplace_front();// 在队列头部增加新的元素

deque<int >q(2,2);
q.emplace_front(1);
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:1 2 2

• deque.insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。

deque<int >q(2,2);
q.insert(q.begin()+1,1);
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:2 1 2

• deque.insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。

deque<int >q(2,2);
q.insert(q.begin()+1,2,1);
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:2 1 1 2

• deque.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。

deque<int >q(4,2),p(2,5);
q.insert(q.begin()+1,p.begin(),p.end());
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:2 5 5 2 2 2

 1
deque<int> d {1,2,3,4,5};
2
deque<int>::iterator it;
3
cout << "insert before:" ;
4
for(it=d.begin();it!=d.end();it++){
5
cout << *it << " ";
6
}
7
cout << endl;
8
d.insert(d.end(),22);
9
d.insert(d.end(), 3,88);
10
int a[5] = {1,2,3,4,5};
11
d.insert(d.begin(),a,a+3);
12
cout << "insert after:" ;
13
for(it=d.begin();it!=d.end();it++){
14
cout << *it << " ";
15
}
16
cout << endl;

3.删除函数

• deque.pop_back(); //删除容器最后一个数据

deque<int >q(4,2);
//q.pop_back();
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:2 2 2 2
deque<int >q(4,2);
q.pop_back();
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:2 2 2

• deque.pop_front(); //删除容器第一个数据

deque<int >q(4,2),p(2,5);
q.insert(q.begin()+1,p.begin(),p.end());
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:2 5 5 2 2 2
deque<int >q(4,2),p(2,5);
q.insert(q.begin()+1,p.begin(),p.end());
q.pop_front();
while(q.size())
{
cout<<q.front()<<' ';
q.pop_front();
}
输出:5 5 2 2 2

• deque.clear(); //移除容器的所有数据

1
deque<int> d {1,2,3,4,5};
2
deque<int>::iterator it;
3
cout << "clear before:" ;
4
for(it=d.begin();it!=d.end();it++){
5
cout << *it << " ";
6
}
7
cout << endl;
8
d.clear();
9
cout << "clear after:" ;
10
for(it=d.begin();it!=d.end();it++){
11
cout << *it << " ";
12
}
13
cout << endl;

• deque.erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。
• deque.erase(pos); //删除pos位置的数据，返回下一个数据的位置。

1
deque<int> d {1,2,3,4,5};
2
d.erase(d.begin());
3
deque<int>::iterator it;
4
cout << "erase(pos) after:" ;
5
for(it=d.begin();it!=d.end();it++){
6
cout << *it << " ";
7
}
8
cout << endl;
9
d.erase(d.begin(), d.begin()+3);
10
cout << "erase(beg,end) after:" ;
11
for(it=d.begin();it!=d.end();it++){
12
cout << *it << " ";
13
}
14
cout << endl;

4.遍历函数

• deque.at(idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range。

1
deque<int> d {1,2,3,4,5};
2
cout << "d.at(pos):" << d.at(2);
3
return 0;

• deque[idx]`; //返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。

deque<int >q(2,2),p(2,5);
q.insert(q.begin()+2,p.begin(),p.end());
int c=q[2];
cout<<c;
输出:5

• deque.front(); //返回第一个数据。

deque<int >q(4,2),p(2,5);
q.insert(q.begin()+1,p.begin(),p.end());
int c=q.front();
cout<<c;
输出:2

• deque.back(); //返回最后一个数据

deque<int >q(2,2),p(2,5);
q.insert(q.begin()+2,p.begin(),p.end());
int c=q.back();
cout<<c;
输出:5

5.判断函数

• deque.empty(); //判断容器是否为空

1
deque<int> d {1,2,3,4,5};
2
if(!d.empty()){
3
cout << "d is not empty!" << endl;
4
}else{
5
cout << "d is empty!" << endl;
6
}
7
return 0;

6.大小函数

• deque.size(); //返回容器中元素的个数

1
deque<int> d {1,2,3,4,5};
2
cout << "d.size():" << d.size() << endl;
3
return 0;

• deque.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

 1
deque<int> d {1,2,3,4,5};
2
cout << "d.size():" << d.size() << endl;
3
d.resize(d.size()+5);
4
cout << "d.resize() after:" << d.size() <<endl;
5
deque<int>::iterator it;
6
cout << "resize() after:" ;
7
for(it=d.begin();it!=d.end();it++){
8
cout << *it << " ";
9
}
10
cout << endl;

• deque.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

1
deque<int> d {1,2,3,4,5};
2
cout << "d.size():" << d.size() << endl;
3
d.resize(d.size()+5);
4
cout << "d.resize() after:" << d.size() <<endl;
5
deque<int>::iterator it;
6
cout << "resize() after:" ;
7
for(it=d.begin();it!=d.end();it++){
8
cout << *it << " ";
9
}
10
cout << endl;

• max_size()返回c容器可能存放元素的最大数量

1
deque<int> d {1,2,3,4,5};
2
cout << "d.max_size():" << d.max_size() << endl;
3
return 0;

7.其他函数

• get_allocator() 返回双向队列的配置器
• deque.begin(); //返回容器中第一个元素的迭代器。
• deque.end(); //返回容器中最后一个元素之后的迭代器。一般与别的函数结合使用

deque<int> d {1,2,3,4,5};
deque<int>::iterator it;
for(it=d.begin();it!=d.end();it++){
cout << *it << " ";
}
cout << endl;

• deque.rbegin(); //返回容器中倒数第一个元素的迭代器。返回指向反向队列的第一个元素的迭代器(即原队列的最后一个元素)
• deque.rend(); //返回容器中倒数最后一个元素之后的迭代器。返回指向反向队列的最后一个元素的下一个位置(即原队列的第一个元素的前一个位置).一般与别的函数结合使用

1
deque<int> d {1,2,3,4,5};
2
deque<int>::reverse_iterator it;
3
for(it=d.rbegin();it!=d.rend();it++){
4
cout << *it << " ";
5
}
6
cout << endl;

• operator=赋值运算符重载

deque<int> d1 {1,2,3,4,5},d2;
d2 = d1;
deque<int>::iterator it;
for(it=d2.begin();it!=d2.end();it++){
cout << *it << " ";
}
cout << endl;

• deque.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。
• deque.assign(n,elem); //将n个elem拷贝赋值给本身。

1
deque<int> d1 {1,2,3,4,5},d2;
2
d2.assign(2, 8);
3
deque<int>::iterator it;
4
cout << "d2.assign(n,num):";
5
for(it=d2.begin();it!=d2.end();it++){
6
cout << *it << " ";
7
}
8
d2.assign(d1.begin(), d1.begin()+3);
9
cout << "d2.assign(beg,end):";
10
for(it=d2.begin();it!=d2.end();it++){
11
cout << *it << " ";
12
}
13
cout << endl;

• deque.swap(deq); // 将vec与本身的元素互换c1.swap(c2)交换容器c1,c2;
  swap(c1,c2)同上。

1
deque<int> d1 {1,2,3,4,5},d2,d3;
2
d1.swap(d2);
3
deque<int>::iterator it;
4
cout << "d1 swap after:" ;
5
for(it=d1.begin();it!=d1.end();it++){
6
cout << *it << " ";
7
}
8
cout << endl;
9
cout << "d2 swap after:" ;
10
for(it=d2.begin();it!=d2.end();it++){
11
cout << *it << " ";
12
}
13
cout << endl;
14
15
swap(d3,d2);
16
cout << "d3 swap after:" ;
17
for(it=d3.begin();it!=d3.end();it++){
18
cout << *it << " ";
19
}
20
cout << endl;

• c.operator[]下标运算符重载

1
deque<int> d {1,2,3,4,5};
2
cout << "d[2]:" << d[2];
3
return 0;

8.总结

1.c.begin()返回指向第一个元素的迭代器
2.end()返回指向最后一个元素下一个位置的迭代器
3.c.rbegin()返回指向反向队列的第一个元素的迭代器(即原队列的最后一个元素)
4.c.rend()返回指向反向队列的最后一个元素的下一个位置(即原队列的第一个元素的前一个位置)
5.operator=赋值运算符重载
6.c.assign(n,num)将n个num拷贝复制到容器
7 c.assign(beg,end)将[beg,end)区间的数据拷贝复制到容器c
8.c.at(pos)返回索引为pos的位置的元素,会执行边界检查,如果越界抛出out_of_range异常
9.c.operator[]下标运算符重载 c.empty()判断c容器是否为空
10.c.front()返回c容器的第一个元素
11.c.size()返回c容器中实际拥有的元素个数
12.c.back()返回c容器的最后一个元素
13.c.size()返回c容器中实际拥有的元素个数
14.c.clear()清除c容器中拥有的所有元素
15.c.insert(pos,num)在pos位置插入元素num
16.c.insert(pos,n,num)在pos位置插入n个元素num
17.c.insert(pos,beg,end)在pos位置插入区间为[beg,end)的元素
18.c.erase(pos)删除pos位置的元素
19.erase(beg,end)删除区间为[beg,end)的元素
20.c.erase(beg,end)删除区间为[beg,end)之间的元素
21.c.push_back(num)在末尾位置插入元素
22.c.pop_back()删除末尾位置的元素 c.push_front(num)在开头位置插入元素
23.c.pop_front()删除开头位置的元素
24.c.resize(num)从新定义容器的大小
24.c1.swap(c2)交换容器c1,c2;
swap(c1,c2)同上。
25.重载运算符
.operator== .
operator!=
operator<
operator<=
operator>
operator>=

除了这些用法之外，deque比queue更优秀的一个性质是它支持随机访问，即可以像数组下标一样取出其中的一个元素。
即：q[i]。

1
deque<int> d {1,2,3,4,5};
2
d.push_back(10);
3
deque<int>::iterator it;
4
cout << "push_back(num):" ;
5
for(it=d.begin();it!=d.end();it++){
6
cout << *it << " ";
7
}
8
cout << endl;
9
10
d.pop_back();
11
cout << "pop_back(num):" ;
12
for(it=d.begin();it!=d.end();it++){
13
cout << *it << " ";
14
}
15
cout << endl;
16
17
d.push_front(10);
18
cout << "push_front(num):" ;
19
for(it=d.begin();it!=d.end();it++){
20
cout << *it << " ";
21
}
22
cout << endl;
23
24
d.pop_front();
25
cout << "pop_front(num):" ;
26
for(it=d.begin();it!=d.end();it++){
27
cout << *it << " ";
28
}
29
cout << endl;
30
return 0;

最后

以上就是机灵火为你收集整理的双端队列(deque)总结(会更新)一.deque的全部内容，希望文章能够帮你解决双端队列(deque)总结(会更新)一.deque所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。