转载自 https://www.cnblogs.com/linuxAndMcu/p/10260124.html
一, 概述
deque(双端队列) 是由一段一段的定量连续空间构成, 可以向两端发展, 因此不论在尾部或头部安插元素都十分迅速. 在中间部分安插元素则比较费时, 因为必须移动其它元素.
二, 定义及初始化
使用之前必须加相应容器的头文件:
#include <deque> // deque 属于 std 命名域, 因此需要通过命名限定, 例如 using std::deque;
定义的实现代码如下:
- // 定义一个 int 类型的双端队列 a
- std::deque a;
- // 定义一个 int 类型的双端队列 a, 并设置初始大小为 10
- std::deque a(10);
- // 定义一个 int 类型的双端队列 a, 并设置初始大小为 10 且初始值都为 1
- std::deque a(10, 1);
- // 定义并用双端队列 a 初始化双端队列 b
- std::deque b(a);
- // 将双端队列 a 中从第 0 个到第 2 个 (共 3 个) 作为双端队列 b 的初始值
- std::deque b(a.begin(), a.begin()+3);
除此之外, 还可以直接使用数组来初始化向量:
- int n[] = {
- 1, 2, 3, 4, 5
- };
- // 将数组 n 的前 5 个元素作为双端队列 a 的初值
- // 说明: 当然不包括 arr[4] 元素, 末尾指针都是指结束元素的下一个元素,
- // 这个主要是为了和 deque.end() 指针统一.
- std::deque a(n, n + 5);
- // 将 n[1],n[2],n[3] 作为双端队列 a 的初值
- std::deque a(&n[1], &n[4]);
三, 基本操作函数
3.1 容量函数
容器大小: deq.size()
容器最大容量: deq.max_size()
更改容器大小: deq.resize()
容器判空: deq.empty()
减少容器大小到满足元素所占存储空间的大小: deq.shrink_to_fit()
- #include
- #include
- int main(int argc, char const* argv[]) {
- std::deque deq;
- for (int i = 0; i<6; ++i) {
- deq.push_back(i);
- }
- std::cout <<deq.size() <<std::endl; // 输出: 6
- std::cout << deq.max_size() << std::endl; // 输出: 1073741823
- deq.resize(0); // 更改元素大小
- std::cout << deq.size() << std::endl; // 输出: 0
- if (deq.empty())
- std::cout << "元素为空" << std::endl; // 输出: 元素为空
- return 0;
- }
3.2 添加函数
头部添加元素: deq.push_front(const T& x)
末尾添加元素: deq.push_back(const T& x)
任意位置插入一个元素: deq.insert(iterator it, const T& x)
任意位置插入 n 个相同元素: deq.insert(iterator it, int n, const T& x)
插入另一个向量的 [forst,last] 间的数据: deq.insert(iterator it, iterator first, iterator last)
- #include
- #include
- #include
- int main(int argc, char const* argv[]) {
- std::deque deq;
- // 头部增加元素
- deq.push_front(4);
- // 末尾添加元素
- deq.push_back(5);
- // 任意位置插入一个元素
- std::deque::iterator it = deq.begin();
- deq.insert(it, 2);
- // 任意位置插入 n 个相同元素
- it = deq.begin(); // 必须要有这句
- deq.insert(it, 3, 9);
- // 插入另一个向量的 [forst,last] 间的数据
- deque deq2(5,8);
- it = deq.begin(); // 必须要有这句
- deq.insert(it, deq2.end() - 1, deq2.end());
- // 遍历显示
- for (it = deq.begin(); it != deq.end(); it++)
- std::cout <<*it << " "; // 输出: 8 9 9 9 2 4 5
- std::cout << std::endl;
- return 0;
- }
3.3 删除函数
头部删除元素: deq.pop_front()
末尾删除元素: deq.pop_back()
任意位置删除一个元素: deq.erase(iterator it)
删除 [first,last] 之间的元素: deq.erase(iterator first, iterator last)
清空所有元素: deq.clear()
- #include
- #include
- #include
- int main(int argc, char* argv[]) {
- std::deque deq;
- for (int i = 0; i <8; i++)
- deq.push_back(i);
- // 头部删除元素
- deq.pop_front();
- // 末尾删除元素
- deq.pop_back();
- // 任意位置删除一个元素
- std::deque::iterator it = deq.begin();
- deq.erase(it);
- // 删除 [first,last] 之间的元素
- deq.erase(deq.begin(), deq.begin()+1);
- // 遍历显示
- for (it = deq.begin(); it != deq.end(); it++)
- std::cout <<*it << " ";
- std::cout << std::endl;
- // 清空所有元素
- deq.clear();
- // 遍历显示
- for (it = deq.begin(); it != deq.end(); it++)
- std::cout << *it << " "; // 输出: 3 4 5 6
- std::cout << std::endl;
- return 0;
- }
3.4 访问函数
下标访问: deq[1] // 并不会检查是否越界
at 方法访问: deq.at(1) // 以上两者的区别就是 at 会检查是否越界, 是则抛出 out of range 异常
访问第一个元素: deq.front()
访问最后一个元素: deq.back()
- #include
- #include
- int main(int argc, char const* argv[]) {
- std::deque deq;
- for (int i = 0; i <6; i++)
- deq.push_back(i);
- // 下标访问
- std::cout << deq[0] << std::endl; // 输出: 0
- // at 方法访问
- std::cout << deq.at(0) << std::endl; // 输出: 0
- // 访问第一个元素
- std::cout << deq.front() << std::endl; // 输出: 0
- // 访问最后一个元素
- std::cout << deq.back() << std::endl; // 输出: 5
- return 0;
- }
3.5 其他函数
多个元素赋值: deq.assign(int nSize, const T& x) // 类似于初始化时用数组进行赋值
交换两个同类型容器的元素: swap(deque&)
- #include
- #include
- int main(int argc, char const* argv[]) {
- // 多个元素赋值
- std::deque deq;
- deq.assign(3, 1);
- deque deq2;
- deq2.assign(3, 2);
- // 交换两个容器的元素
- deq.swap(deq2);
- // 遍历显示
- std::cout <<"deq:";
- for (int i = 0; i < deq.size(); i++)
- std::cout << deq[i] << " "; // 输出: 2 2 2
- std::cout << std::endl;
- // 遍历显示
- std::cout << "deq2:";
- for (int i = 0; i < deq2.size(); i++)
- std::cout << deq2[i] << " "; // 输出: 1 1 1
- std::cout << std::endl;
- return 0;
- }
四, 迭代器与算法
4.1 迭代器
开始迭代器指针: deq.begin()
末尾迭代器指针: deq.end() // 指向最后一个元素的下一个位置
指向常量的开始迭代器指针: deq.cbegin() // 意思就是不能通过这个指针来修改所指的内容, 但还是可以通过其他方式修改的, 而且指针也是可以移动的.
指向常量的末尾迭代器指针: deq.cend()
反向迭代器指针, 指向最后一个元素: deq.rbegin()
反向迭代器指针, 指向第一个元素的前一个元素: deq.rend()
- #include
- #include
- int main(int argc, char const* argv[]) {
- std::deque deq;
- deq.push_back(1);
- deq.push_back(2);
- deq.push_back(3);
- std::cout <<*(deq.begin()) << std::endl; // 输出: 1
- std::cout << *(--deq.end()) << std::endl; // 输出: 3
- std::cout << *(deq.cbegin()) << std::endl; // 输出: 1
- std::cout << *(--deq.cend()) << std::endl; // 输出: 3
- std::cout << *(deq.rbegin()) << std::endl; // 输出: 3
- std::cout << *(--deq.rend()) << std::endl; // 输出: 1
- std::cout << std::endl;
- return 0;
- }
4.2 算法
遍历元素
- std::deque::iterator it;
- for (it = deq.begin(); it != deq.end(); it++)
- std::cout <<*it << std::endl;
- // 或者
- for (int i = 0; i < deq.size(); i++) {
- std::cout << deq.at(i) << std::endl;
- }
元素翻转
- #include
- reverse(deq.begin(), deq.end());
元素排序
- #include
- std::sort(deq.begin(), deq.end()); // 采用的是从小到大的排序
- // 如果想从大到小排序, 可以采用先排序后反转的方式, 也可以采用下面方法:
- // 自定义从大到小的比较器, 用来改变排序方式
- bool Comp(const int& a, const int& b) {
- return a> b;
- }
- std::sort(deq.begin(), deq.end(), Comp);
五, 总结
可以看到, deque 与 vector 的用法基本一致, 除了以下几处不同:
deque 没有 capacity() 函数, 而 vector 有;
deque 有 push_front() 和 pop_front() 函数, 而 vector 没有;
deque 没有 data() 函数, 而 vector 有.
----------------
来源: http://www.bubuko.com/infodetail-3343065.html