Cpp

deque

scorlw 发布于

deque

c++

deque（[‘dek]）（双端队列）是double-ended queue 的一个不规则缩写。deque是具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩。

image-20200813202649973

deque上常见操作的复杂性（效率）如下：

  • 随机访问 - 常数O(1)
  • 在结尾或开头插入或移除元素 - 摊销不变O(1)
  • 插入或移除元素 - 线性O(n)

常用函数

(1) 构造函数

1
2
3
4
5
6
7
8
9
deque():创建一个空deque

deque(int nSize):**创建一个deque,元素个数为nSize**

deque(int nSize,const T& t):创建一个deque,元素个数为nSize,且值均为t

deque(const deque &):复制构造函数
    
deque<int> a = {1,2,3,4,5};初始化

(2) 增加函数

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
void push_front(const T& x):双端队列头部增加一个元素X

void push_back(const T& x):双端队列尾部增加一个元素x

iterator insert(iterator it,const T& x):双端队列中某一元素前增加一个元素x
/*
{
    deque<int> ta = {1,2,3,4,5};
    for(int i : ta)
        cout << i;
    cout << endl;
    auto it = ta.begin();
    auto it1 = ta.insert(it + 2, 9);
    cout << *it1 << endl;
    for(int i : ta)
        cout << i;
    cout << endl;
}
//输出
12345
9
129345
*/

void insert(iterator it,int n,const T& x):双端队列中某一元素前增加n个相同的元素x

void insert(iterator it,const_iterator first,const_iteratorlast):双端队列中某一元素前插入另一个相同类型向量的[forst,last)间的数据

(3) 删除函数

1
2
3
4
5
6
7
8
9
iterator erase(iterator it):删除双端队列中的某一个元素

iterator erase(iterator first,iterator last):删除双端队列中[first,last）中的元素

void pop_front():删除双端队列中最前一个元素

void pop_back():删除双端队列中最后一个元素

void clear():清空双端队列

(4) 遍历函数

1
2
3
4
5
6
7
8
9
10
11
12
13
reference at(int pos):返回pos位置元素的引用

reference front():返回首元素的引用

reference back():返回尾元素的引用

iterator begin():返回向量头指针，指向第一个元素

iterator end():返回指向向量中最后一个元素下一个元素的指针（不包含在向量中）

reverse_iterator rbegin():反向迭代器，指向最后一个元素

reverse_iterator rend():反向迭代器，指向第一个元素的前一个元素

(5) 判断函数

1
bool empty() const:向量是否为空，若true,则向量中无元素

(6) 大小函数

1
2
3
int size() const:返回向量中元素的个数

int max_size() const:返回最大可允许的双端队列元素数量值

(7) 其他函数

1
2
3
void swap(deque&):交换两个同类型向量的数据

void assign(int n,const T& x):向量中第n个元素的值设置为x

deque与vector内存分配比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int>v(2);
v[0]=10;
int *p = &v[0];
cout<<"vector第一个元素迭代指针*p="<<*p<<endl;
v.push_back(20);
cout<<"vector容量变化后原vector第1个元素迭代指针*p="<<*p<<endl;

deque<int> d(2);
d[0]=10;
int *q = &d[0];
cout<<"deque第一个元素迭代指针*q="<<*q<<endl;
d.push_back(20);
cout<<"deque容量变化后第一个元素迭代器指针*q="<<*q<<endl;
system("pause");
return 0;

输出：

1
2
3
4
vector第一个元素迭代指针*p=10
vector容量变化后原vector第1个元素迭代指针*p=2036720
deque第一个元素迭代指针*q=10
deque容量变化后第一个元素迭代器指针*q=10

该段程序的功能是：deque、vector初始化后大小为2，第一个元素都为10，当通过push_back函数分别给两个容器增加一个元素后，从结果发现原先保持的指针元素值对vector容器前后发生了变化，而对deque容器前后没有发生变化。原因为，在建立vector容器时，一般来说伴随这建立空间->填充数据->重建更大空间->复制原空间数据->删除原空间->添加新数据，如此反复，保证vector始终是一块独立的连续内存空间；在建立deque容器时，一般便随着建立空间->建立数据->建立新空间->填充新数据，如此反复，没有原空间数据的复制和删除过程，是由多个连续的内存空间组成的。

原文地址：https://blog.csdn.net/longshengguoji/article/details/8519812#