C++ deque容器

C++ deque容器

---

---

前言

本文包含deque容器基本概念、deque构造函数、deque赋值操作、deque大小操作、deque插入和删除、deque数据存取、deque排序。

---

1. deque容器基本概念

功能：

双端数组，可以对头端进行插入删除操作

deque与vector区别：

（1）、vector对于头部的插入删除效率低，数据量越大，效率越低

（2）、deque相对而言，对头部的插入删除速度回比vector快

（3）、vector访问元素时的速度会比deque快，这和两者内部实现有关

deque内部工作原理：

（1）、deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据

（2）、中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间

（3）、deque容器的迭代器也是支持随机访问的

2. deque构造函数

功能描述：

deque容器构造

函数原型：

（1）、deque<T> deqT; 默认构造形式

（2）、deque(beg, end); 构造函数将[beg, end)区间中的元素拷贝给本身

（3）、deque(n, elem); 构造函数将n个elem拷贝给本身

（4）、deque(const deque &deq); 拷贝构造函数

// deque双端数组容器构造函数#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <deque>  // 使用deque双端数组容器，需包含头文件deque// const对此容器只是只读，不可以修改
void Fun_Print(const deque<int>& d) {   // 使用引用方式&，传入deque<int>类型的形参d// deque<int>::iterator 拿到deque<int>这种容器的迭代器类型；每个容器都有一个专属的迭代器类型// const_iterator只读迭代器；iterator普通迭代器for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 1、默认构造方式，无参构造deque<int> d;for (int i = 0; i < 10; i++){// push_back()向容器尾部插入数据id.push_back(i);}Fun_Print(d);  // 0 1 2 3 4 5 6 7 8 9// 2、将d容器开始迭代器到结束迭代器之间的数据元素，拷贝给d1容器deque<int> d1(d.begin(), d.end());Fun_Print(d1);  // 0 1 2 3 4 5 6 7 8 9// 3、将10个100拷贝给d2容器deque<int> d2(10, 100);Fun_Print(d2);  // 100 100 100 100 100 100 100 100 100 100// 4、拷贝构造deque<int> d3(d2);Fun_Print(d3);  // 100 100 100 100 100 100 100 100 100 100
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

3. deque赋值操作

功能描述：

给deque容器进行赋值

函数原型：

（1）、deque& operator=(const deque &deq); 重载等号操作符

（2）、assign(beg, end); 将[beg, end)区间中的数据拷贝赋值给本身

（3）、assign(n, elem); 将n个elem拷贝赋值给本身

// deque双端数组容器赋值#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <deque>  // 使用deque双端数组容器，需包含头文件deque// const对此容器只是只读，不可以修改
void Fun_Print(const deque<int>& d) {   // 使用引用方式&，传入deque<int>类型的形参d// deque<int>::iterator 拿到deque<int>这种容器的迭代器类型；每个容器都有一个专属的迭代器类型// const_iterator只读迭代器；iterator普通迭代器for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 创建deque容器对象，并且通过模板参数指定容器中存放的数据的类型deque<int> d;for (int i = 0; i < 10; i++){// push_back()向容器尾部插入数据id.push_back(i);}Fun_Print(d);  // 0 1 2 3 4 5 6 7 8 9// 1、重载operator=deque<int> d1;d1 = d;Fun_Print(d1);  // 0 1 2 3 4 5 6 7 8 9// 2、将d容器开始迭代器到结束迭代器之间的数据元素，赋值给d2容器deque<int> d2;d2.assign(d.begin(), d.end());Fun_Print(d2);  // 0 1 2 3 4 5 6 7 8 9// 3、将10个100赋值给d3deque<int> d3;d3.assign(10, 100);Fun_Print(d3);  // 100 100 100 100 100 100 100 100 100 100
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

4. deque大小操作

功能描述：

对deque容器的大小进行操作 （没有容量，可以无限扩展）

函数原型：

（1）、deque.empty(); 判断容器是否为空

（2）、deque.size(); 返回容器中元素的个数

（3）、deque.resize(num);

3.1）、重新指定容器的长度为num,若容器变长，则以默认值填充新位置 （默认填充0）

3.2）、如果容器变短，则末尾超出容器长度的元素被删除

（4）、deque.resize(num, elem);

4.1）、重新指定容器的长度为num,若容器变长，则以elem值填充新位置 （填充elem）

4.2）、如果容器变短，则末尾超出容器长度的元素被删除

// deque双端数组容器大小操作#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <deque>  // 使用deque双端数组容器，需包含头文件deque// const对此容器只是只读，不可以修改
void Fun_Print(const deque<int>& d) {   // 使用引用方式&，传入deque<int>类型的形参d// deque<int>::iterator 拿到deque<int>这种容器的迭代器类型；每个容器都有一个专属的迭代器类型// const_iterator只读迭代器；iterator普通迭代器for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 创建deque容器对象，并且通过模板参数指定容器中存放的数据的类型deque<int> d;for (int i = 0; i < 10; i++){// push_back()向容器尾部插入数据id.push_back(i);}Fun_Print(d);  // 0 1 2 3 4 5 6 7 8 9// 1、empty()判断容器是否为空，返回真，则为空if (d.empty()) {cout << "d容器为空！" << endl;}else {cout << "d容器不为空！" << endl;// 2、size()返回容器数据元素个数cout << "d容器个数为：" << d.size() << endl;  // 10}// 3.1、resize()指定容器长度为15，默认填充0d.resize(15);Fun_Print(d);  // 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0// 3.2、resize()指定容器长度为5，删除超出容器长度的数据元素d.resize(5);Fun_Print(d);  // 0 1 2 3 4// 4.1、resize()指定容器长度为10，默认填充10d.resize(10, 10);Fun_Print(d);  // 0 1 2 3 4 10 10 10 10 10// 4.2、resize()指定容器长度为5，删除超出容器长度的数据元素d.resize(5, 5);Fun_Print(d);  // 0 1 2 3 4
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

5. deque 插入和删除

功能描述：

向deque容器中插入和删除数据

函数原型：

（1）、两端插入操作：

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

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

pop_back(); 删除容器最后一个数据

pop_front(); 删除容器第一个数据

// deque双端数组容器插入#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <deque>  // 使用deque双端数组容器，需包含头文件deque// const对此容器只是只读，不可以修改
void Fun_Print(const deque<int>& d) {   // 使用引用方式&，传入deque<int>类型的形参d// deque<int>::iterator 拿到deque<int>这种容器的迭代器类型；每个容器都有一个专属的迭代器类型// const_iterator只读迭代器；iterator普通迭代器for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 创建deque容器对象，并且通过模板参数指定容器中存放的数据的类型deque<int> d;// 1、push_back()向容器尾部插入数据1、2d.push_back(1);d.push_back(2);Fun_Print(d);  // 1 2// 2、push_front()向容器头部插入数据3、4d.push_front(3);d.push_front(4);Fun_Print(d);  // 4 3 1 2// 3、pop_back()删除容器最后一个数据d.pop_back();Fun_Print(d);  // 4 3 1 // 4、pop_front()删除容器第一个数据d.pop_front();Fun_Print(d);  // 3 1
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

（2）、指定位置操作：

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

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

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

erase(beg,end); 删除[beg,end)区间的数据，返回下一个数据的位置

erase(pos); 删除pos位置的数据，返回下一个数据的位置

clear(); 清空容器的所有数据

// deque双端数组容器插入和删除#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <deque>  // 使用deque双端数组容器，需包含头文件deque// const对此容器只是只读，不可以修改
void Fun_Print(const deque<int>& d) {   // 使用引用方式&，传入deque<int>类型的形参d// deque<int>::iterator 拿到deque<int>这种容器的迭代器类型；每个容器都有一个专属的迭代器类型// const_iterator只读迭代器；iterator普通迭代器for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 创建deque容器对象，并且通过模板参数指定容器中存放的数据的类型deque<int> d;// 1、insert()在容器开始迭代器处插入数据10d.insert(d.begin(), 10);Fun_Print(d);  // 10// 2、insert()在容器结束迭代器处插入5个10d.insert(d.end(), 5, 100);Fun_Print(d);  // 10 100 100 100 100 100// 3、insert()在容器结束迭代器处，插入d容器开始迭代器到结束迭代器中的数据元素d.insert(d.end(), d.begin(), d.end());Fun_Print(d);  // 10 100 100 100 100 100 10 100 100 100 100 100deque<int>::iterator it = d.begin();  // 创建一个迭代器itit += 6;  // 使it位置为6// 4、erase()按区间删除数据元素，从第6个迭代器位置开始，删除d容器之后所有数据元素d.erase(it, d.end());Fun_Print(d);  // 10 100 100 100 100 100// 5、erase()删除d容器开始迭代器的数据元素d.erase(d.begin());Fun_Print(d);  // 100 100 100 100 100// 6、clear()清空容器所有数据元素d.clear();Fun_Print(d);  // 
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

6. deque 数据存取

功能描述：

对deque 中的数据的存取操作

函数原型：

（1）、at(int idx); 返回索引idx所指的数据

（2）、operator[]; 返回下标idx所指的数据

（3）、front(); 返回容器中第一个数据元素

（4）、back(); 返回容器中最后一个数据元素

// deque双端数组容器数据存取#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <deque>  // 使用deque双端数组容器，需包含头文件dequevoid test() {// 创建deque容器对象，并且通过模板参数指定容器中存放的数据的类型deque<int> d;for (int i = 0; i < 10; i++){// push_back()向容器尾部插入数据id.push_back(i);}// 1、at()返回容器索引i所指的数据元素for (int i = 0; i < d.size(); i++) {  // size()返回容器数据元素个数cout << d.at(i) << " ";  // 0 1 2 3 4 5 6 7 8 9}cout << endl;// 2、[]返回容器下标i所指的数据元素for (int i = 0; i < d.size(); i++) {cout << d[i] << " ";  // 0 1 2 3 4 5 6 7 8 9}cout << endl;// 3、front()返回容器的第一个数据元素cout << "d容器的第一个数据元素为：" << d.front() << endl;  // 0// 4、front()返回容器的最后一个数据元素cout << "d容器的最后一个数据元素为：" << d.back() << endl;  // 9
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

7. deque 排序

功能描述：

利用算法实现对deque容器进行排序

算法：

sort(iterator beg, iterator end) 对beg和end区间内元素进行排序

// deque双端数组容器排序#include <iostream>  // 包含标准输入输出流头文件
using namespace std;  // 使用标准命名空间#include <deque>  // 使用deque双端数组容器，需包含头文件deque
#include <algorithm>  // 标准算法头文件；使用sort，需包含头文件algorithm// const对此容器只是只读，不可以修改
void Fun_Print(const deque<int>& d) {   // 使用引用方式&，传入deque<int>类型的形参d// deque<int>::iterator 拿到deque<int>这种容器的迭代器类型；每个容器都有一个专属的迭代器类型// const_iterator只读迭代器；iterator普通迭代器for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {//*it= 100;  // 报错，容器中数据不可修改：表达式必须是可修改的左值cout << *it << " ";  // it是个迭代器类型，本是是个指针，需使用*解引用}cout << endl;
}void test() {// 创建deque容器对象，并且通过模板参数指定容器中存放的数据的类型deque<int> d;// push_back()向容器尾部插入数据d.push_back(80);d.push_back(20);d.push_back(40);d.push_front(10);d.push_front(90);d.push_front(50);Fun_Print(d);  // 50 90 10 80 20 40// sort()排序；默认排序规则，从小到大，升序// 对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序；vector容器也可以利用sort进行排序sort(d.begin(), d.end());Fun_Print(d);  // 10 20 40 50 80 90
}int main() {test();system("pause");  // 相当于在本地 Windows 调试器中的：请按任意键继续...；暂停，方便看清楚输出结果return 0;  // 程序正常退出
}

---

总结

（1）、deque 容器和 vector 容器的构造方式几乎一致，灵活使用即可；

（2）、deque 赋值操作也与 vector 相同；

（3）、deque 没有容量的概念；

（4）、deque 判断是否为空 — empty；

（5）、deque 返回元素个数 — size；

（6）、deque 重新指定个数 — resize；

（7）、deque 插入和删除提供的位置是迭代器！

（8）、deque尾插 — push_back；

（9）、deque 尾删 — pop_back；

（10）、deque 头插 — push_front；

（11）、deque 头删 — pop_front；

（12）、除了用迭代器获取deque容器中元素，[ ]和at也可以；

（13）、front() 返回容器第一个元素；

（14）、back() 返回容器最后一个元素；

（15）、sort() 算法非常实用，使用时包含头文件 algorithm即可。