deque

std::deque（double-ended queue）是 C++ 标准库中的双端顺序容器，支持在头部和尾部高效插入删除。

它的使用体验有点像“可双端增长的数组”：既提供类似 vector 的随机访问能力，也比 vector 更适合频繁头插头删。

头文件与基本特征

使用 deque 时，需要包含头文件：

#include <deque>

deque 的常见特征如下：

特征	说明
底层结构	分段连续存储（不是单块连续内存）
随机访问	支持，O(1)
头尾插入删除	通常为常数时间
中间插入删除	通常较慢，需要移动元素
迭代器失效	插删可能导致部分迭代器失效

基本用法

#include <deque>

int main() {
	std::deque<int> nums;

	nums.push_back(10);
	nums.push_back(20);
	nums.push_front(5);

	return 0;
}

访问与遍历

#include <deque>
#include <iostream>

int main() {
	std::deque<int> nums;
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(3);

	for (std::deque<int>::size_type i = 0; i < nums.size(); ++i) {
		std::cout << nums[i] << ' ';
	}
	std::cout << '\n';

	for (std::deque<int>::iterator it = nums.begin(); it != nums.end(); ++it) {
		std::cout << *it << ' ';
	}
	std::cout << '\n';

	return 0;
}

常用成员函数

函数	作用
front() / back()	访问头元素和尾元素
push_front() / push_back()	头插和尾插
pop_front() / pop_back()	删除头/尾元素
begin() / end()	获取迭代器
size() / empty()	元素数量与判空
insert() / erase()	中间插删
clear()	清空容器

典型场景

deque 常见在这些场景出现：

1. 需要频繁从两端入队/出队。
2. 既要双端操作，又希望保留下标随机访问能力。
3. 作为 queue 默认底层容器（标准库默认就是 deque）。

使用注意

1. 虽然支持随机访问，但内存不是像 vector 那样单块连续。
2. 若主要操作只有尾部追加并追求最佳遍历局部性，通常 vector 更常见。
3. 在保存迭代器、引用、指针时，需要关注插删后的有效性。