C++标准模板库(STL)deque双端队列
一. 定义与基本概念
在C++的标准模板库(STL)中,deque(双端队列,发音为“deck”)是一种序列容器,位于<deque>头文件中。类似vector,支持随机访问元素,但在两端进行插入和删除操作更为高效。deque中的元素在内存中可能不是连续存储的,而是由多个固定大小的块组成,每个块内部是连续存储的。
二. 创建deque对象
默认构造:可以创建一个空的deque对象。
1 | std::deque< int > myDeque; |
创建了一个空的、用于存储int类型元素的deque。
指定大小构造:可以创建具有特定大小的deque,并可选择初始化元素的值。
1 | std::deque< int > myDeque(5); |
创建了一个包含5个int类型元素的deque,这些元素会被默认初始化(对于基本类型int,默认值为0);
1 | std::deque< int > myDeque(5, 10); |
则创建了一个包含5个元素且每个元素都初始化为10的deque。
从其他容器初始化:可以使用另一个容器(如数组)来初始化deque。
1 2 | int arr[] = {1, 2, 3}; std::deque< int > myDeque(arr, arr + sizeof (arr)/ sizeof (arr[0])); |
这里使用数组arr的元素来初始化deque myDeque。
三. deque的基本操作
1. 元素访问
使用[]运算符:与vector类似,可以通过[]运算符来访问deque中的元素。
1 2 | std::deque< int > myDeque = {1, 2, 3}; std::cout << myDeque[1] << std::endl; |
这里通过[]运算符访问myDeque中的第二个元素,输出为2。
使用at()方法:at()方法也用于访问元素,并且会进行边界检查。
1 2 | std::deque< int > myDeque = {1, 2, 3}; std::cout << myDeque.at(2) << std::endl; |
访问myDeque中的第三个元素,如使用at()方法访问超出范围的索引,会抛出std::out_of_range异常。
2. 添加元素
push_back()和push_front():push_back()用于在deque的末尾添加一个元素,push_front()用于在deque的开头添加一个元素。
1 2 3 | std::deque< int > myDeque; myDeque.push_back(3); myDeque.push_front(1); |
此时myDeque包含两个元素,1在开头,3在末尾。
insert()(在指定位置插入元素):可以在deque的指定位置插入一个或多个元素。
1 2 3 4 | std::deque< int > myDeque = {1, 3}; std::deque< int >::iterator it = myDeque.begin(); ++it; myDeque.insert(it, 2); |
这里在deque中1和3之间插入了元素2。
3. 删除元素
pop_back()和pop_front():pop_back()用于删除deque末尾的一个元素,pop_front()用于删除deque开头的一个元素。
1 2 3 | std::deque< int > myDeque = {1, 2, 3}; myDeque.pop_front(); myDeque.pop_back(); |
操作后myDeque中只剩下元素2。
erase()(删除指定位置的元素):可以删除deque中指定位置的元素。
1 2 3 4 | std::deque< int > myDeque = {1, 2, 3}; std::deque< int >::iterator it = myDeque.begin(); ++it; myDeque.erase(it); |
这里删除了myDeque中的元素2。
4. 获取deque的大小和容量
size():返回deque中当前元素的个数。例如,std::deque<int> myDeque = {1, 2, 3}; std::cout << myDeque.size() << std::endl;会输出3,表示deque中有3个元素。
capacity()(在某些实现中):一些deque的实现可能提供capacity()方法来表示deque在不重新分配内存的情况下能够容纳的最大元素数量,但这不是标准要求的操作。与vector不同,deque的内存管理机制使得它不需要像vector那样频繁地重新分配内存来扩展容量。
四. 迭代器操作
deque提供了随机访问迭代器,支持与vector类似的迭代器操作。
1 2 3 4 5 6 7 8 9 10 11 | std::deque< int > myDeque = {1, 2, 3}; // 正向遍历 for (std::deque< int >::iterator it = myDeque.begin(); it!= myDeque.end(); ++it) { std::cout << *it << " " ; } std::cout << std::endl; // 反向遍历 for (std::deque< int >::reverse_iterator rit = myDeque.rbegin(); rit!= myDeque.rend(); ++rit) { std::cout << *rit << " " ; } std::cout << std::endl; |
这里使用begin()、end()、rbegin()和rend()方法分别获取正向和反向迭代器的起始和结束位置。
五. deque的特性与注意事项
内存管理与性能:deque的内存布局使得它在两端插入和删除元素的效率很高(时间复杂度为$O(1)$),类似于list在两端操作的效率。同时,它支持随机访问,随机访问元素的时间复杂度为$O(1)$,这一点与vector相同。然而,由于其内存结构相对复杂,与vector相比,在某些操作(如中间元素的插入和删除)上可能会有一些性能差异。
与vector和list的比较
与vector相比,deque在两端操作更高效,而vector在末尾添加元素的操作也很高效,但在开头添加元素效率较低。并且vector在内存重新分配时可能会导致性能下降,而deque的内存管理相对更灵活。
与list相比,deque支持随机访问,而list不支持。list在中间插入和删除元素的效率很高,但随机访问效率很低。
迭代器失效:在对deque进行插入或删除操作时,可能会导致迭代器失效。与vector类似,在deque中插入或删除元素可能会使指向该元素之后的迭代器失效,需要注意在操作后重新获取有效的迭代器。
C++编程语言基础
- C++:从入门到工作的教程
- 这是我的第一个 C++程序!
- C++中main函数有什么作用?
- C++中 #include 指令的作用
- C++中常用的预处理指令
- C++中 iostream 头文件定义了什么
- C++名称空间(namespace)
- C++标准库中 std 命名空间定义了些什么
- C++常用的头文件
- C++源代码的发布方式
- C++变量名的定义、变量的作用、使用规范
- C++的关键字列表
- C++数据类型:整型(整数类型)
- 二进制补码、原码、反码
- C++数据类型:char字符型(整数类型)
- ASCII码表及C++字符函数库(cctype)
- 计算机汉字编码
- C++数据类型:bool类型(整数类型)
- C++中 const 限定符
- C++数据类型:浮点数
- C++运算符:算术运算符
- C++运算符:类型转换规则
- 计算机数据存储大小端模式
- C++运算符:位运算 与 bitset类库
- C++运算符:关系运算符与逻辑运算符
- C++流程控制:顺序、选择、循环、跳转语句
- C++函数的定义、参数传递、重载、嵌套
- C++数组:一维、二维、多维数组的运用
- C-style字符串、库函数 与 std::string对象
- C++数据类型:结构体(struct)
- C++数据类型:联合体(union)
- C++数据类型:枚举(enum)
- C++数据类型别名:typedef
- C++指针
- C++内存操作符:new分配 与 delete释放
- C++标准模板库(STL)容器、算法、迭代器
- C++标准模板库(STL)vector顺序容器
- C++标准模板库(STL)array固定容器
- C++标准模板库(STL)list双向链表容器
- C++标准模板库(STL)deque双端队列
- C++标准模板库(STL)集合 set 关联容器
- C++标准模板库(STL)map关联容器
- C++标准模板库(STL)unordered_set
- C++标准模板库(STL)unordered_map
- C++标准模板库(STL)algorithm算法库
- C++文件操作
- C++数学库(cmath)数学常量与数学函数
- C++模板:函数模板、类模板
- C++与SQLite3联合打造实用的应用程序
- C++实战开发中常用的库(概述)
- 第二部分:C++面向对象编程
- C++:类的定义与声明、类对象应用
- 第三部分:数据结构与算法(概述)
- 第一部分:C++语言简介与学习路线