C++容器deque

定义

std::deque - cppreference.cn - C++参考手册

  • 双端队列，允许在容器的前端和后端高效地进行插入和删除操作
  • deque 的元素不是连续存储的：典型的实现使用一系列单独分配的固定大小数组，并带有额外的簿记，这意味着对 deque 的索引访问必须执行两次指针解引用，而 vector 的索引访问只需执行一次
  • deque 的存储空间会根据需要自动扩展和收缩，但是扩容不涉及全量数据复制
特性 std::deque std::vector
头部插入/删除 O(1) O(n) - 需要移动所有元素
尾部插入/删除 O(1) O(1) - 均摊
中间插入/删除 O(n) O(n)
随机访问 O(1) O(1)
内存布局 分段连续 完全连续
迭代器失效 插入/删除时，指向被移动元素的迭代器失效 尾部插入可能使所有迭代器失效（重新分配时）；其他插入/删除使后续迭代器失效
内存预留 不支持 reserve() 支持 reserve() 避免重新分配

构造函数

1、默认构造函数

int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1;
	queue1.push_front(u8"北京");
	queue1.push_back(u8"上海");

	cout << "queue1.front()-> " << getStringFromU8string(queue1.front()) << endl;
	cout << "queue1.back()-> " << getStringFromU8string(queue1.back()) << endl;
	cout << "queue1.size()-> " << queue1.size() << endl;
	cout << "queue1.empty()-> " << boolalpha << queue1.empty() << endl;

	// 从头到尾
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.front()) << endl;
		queue1.pop_front();
	}
}

2、指定元素个数的构造函数

指定个数，没有指定元素值，就都默认值

int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1(4);
	queue1.push_front(u8"北京");
	queue1.push_back(u8"上海");

	cout << "queue1.front()-> " << getStringFromU8string(queue1.front()) << endl;
	cout << "queue1.back()-> " << getStringFromU8string(queue1.back()) << endl;
	cout << "queue1.size()-> " << queue1.size() << endl;
	cout << "queue1.empty()-> " << boolalpha << queue1.empty() << endl;

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}
}

3、指定元素个数与初始值的构造函数

int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1(4, u8"&&");
	queue1.push_front(u8"北京");
	queue1.push_back(u8"上海");

	cout << "queue1.front()-> " << getStringFromU8string(queue1.front()) << endl;
	cout << "queue1.back()-> " << getStringFromU8string(queue1.back()) << endl;
	cout << "queue1.size()-> " << queue1.size() << endl;
	cout << "queue1.empty()-> " << boolalpha << queue1.empty() << endl;

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}
}

4、拷贝构造函数

int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1;
	queue1.push_front(u8"北京");
	queue1.push_back(u8"上海");

	// 拷贝构造函数
	deque<std::u8string> queue2(queue1);

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}

	// 从头到尾
	while (!queue2.empty())
	{
		cout << "queue2-> " << getStringFromU8string(queue2.front()) << endl;
		queue2.pop_front();
	}
}

5、移动构造函数

移动后，原队列数据清空

int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1;
	queue1.push_front(u8"北京");
	queue1.push_back(u8"上海");

	// 移动构造函数
	deque<std::u8string> queue2(std::move(queue1));

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}

	// 从头到尾
	while (!queue2.empty())
	{
		cout << "queue2-> " << getStringFromU8string(queue2.front()) << endl;
		queue2.pop_front();
	}
}

6、初始化列表构造函数

int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1 = { u8"北京" ,u8"上海" };
	deque<std::u8string> queue2{ u8"广州" ,u8"深圳" };

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}

	// 从头到尾
	while (!queue2.empty())
	{
		cout << "queue2-> " << getStringFromU8string(queue2.front()) << endl;
		queue2.pop_front();
	}
}

7、区间构造函数

#include <iostream>
#include <string>
#include <deque>
#include <array>

using namespace std;

std::string getStringFromU8string(const std::u8string& u8str) {
	return std::string(reinterpret_cast<const char*>(u8str.data()), u8str.size());
}

std::u8string getU8stingFromString(const std::string& str) {
	return std::u8string(reinterpret_cast<const char8_t*>(str.data()), str.size());
}

int main()
{
	system("chcp 65001");

	std::array<std::u8string, 2> arr1 = { u8"北京" ,u8"上海" };
	// 区间构造函数
	deque<std::u8string> queue1(arr1.begin(), arr1.end());

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}

	for (auto it : arr1)
	{
		cout << "arr1-> " << getStringFromU8string(it) << endl;
	}
}

元素访问

使用 front() 和 back() 前必须确保 deque 非空

函数 描述
d[i] 返回索引 i 处元素的引用（不检查越界）。
d.at(i) 返回索引 i 处元素的引用（会进行越界检查，越界抛出 std::out_of_range）。
d.front() 返回第一个元素的引用。
d.back() 返回最后一个元素的引用。 
int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1 = { u8"北京" ,u8"上海" };
	cout << "queue1[0]= " << getStringFromU8string(queue1[0]) << endl;
	cout << "queue1.at(1)= " << getStringFromU8string(queue1.at(1)) << endl;
	cout << "queue1.front()= " << getStringFromU8string(queue1.front()) << endl;
	cout << "queue1.back()= " << getStringFromU8string(queue1.back()) << endl;

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}
}

容量大小

函数 描述
d.empty() 如果 deque 为空，返回 true。
d.size() 返回当前元素数量。
d.max_size() 返回容器可容纳的最大元素数量。 
int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1 = { u8"北京" ,u8"上海" };
	cout << "queue1.size()= " << queue1.size() << endl;
	cout << "queue1.max_size()= " << queue1.max_size() << endl;
	cout << "queue1.empty()= " << boolalpha << queue1.empty() << endl;

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}
}

修改函数

函数 描述
d.push_back(value) 在末尾插入一个元素。
d.push_front(value) 在开头插入一个元素。
d.pop_back() 删除最后一个元素。
d.pop_front() 删除第一个元素。
d.emplace_back(args...) 在末尾就地构造一个元素（比 push_back 更高效）
d.emplace_front(args...) 在开头就地构造一个元素（比 push_front 更高效）
d.insert(pos, value) 在位置 pos 插入元素。
d.erase(pos) 删除位置 pos 的元素。
d.clear() 删除所有元素。
d.resize(n) 调整大小到 n。如果变大，新元素用默认值初始化。
d.swap(other) 与另一个 deque 交换内容。 
int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1 = { u8"北京" ,u8"上海" };
	cout << "queue1.size()= " << queue1.size() << endl;
	cout << "queue1.max_size()= " << queue1.max_size() << endl;
	cout << "queue1.empty()= " << boolalpha << queue1.empty() << endl;
	queue1.emplace_front(u8"广州");
	queue1.emplace_back(u8"深圳");

	// 中间插入数据
	queue1.insert(queue1.begin() + 1, u8"测试");

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}


	// 清空数据
	queue1.clear();
	cout << "clear queue1.size()= " << queue1.size() << endl;
	cout << "clear queue1.max_size()= " << queue1.max_size() << endl;

	// 设置大小
	queue1.resize(3);
	cout << "resize queue1.size()= " << queue1.size() << endl;
	cout << "resize queue1.max_size()= " << queue1.max_size() << endl;

	// 按下标记赋值
	queue1[0] = u8"张三";
	queue1[1] = u8"李四";
	for (auto it : queue1)
	{
		cout << "queue1-> " << getStringFromU8string(it) << endl;
	}
}

遍历

出队遍历

这种方式遍历后，数据清空

int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1 = { u8"北京" ,u8"上海" };

	// 从尾到头
	while (!queue1.empty())
	{
		cout << "从尾到头 queue1-> " << getStringFromU8string(queue1.back()) << endl;
		queue1.pop_back();
	}
	cout << "clear queue1.size()= " << queue1.size() << endl;
	cout << "clear queue1.max_size()= " << queue1.max_size() << endl;

	// 重新入队
	queue1.emplace_front(u8"张三");
	queue1.emplace_front(u8"李四");

	// 从头到尾
	while (!queue1.empty())
	{
		cout << "从头到尾 queue1-> " << getStringFromU8string(queue1.front()) << endl;
		queue1.pop_front();
	}
}

迭代器

int main()
{
	system("chcp 65001");
	deque<std::u8string> queue1 = { u8"北京" ,u8"上海" };
	// for
	for (auto it : queue1)
	{
		cout << "queue1-> " << getStringFromU8string(it) << endl;
	}

	// begin-end
	for (auto it = queue1.begin(); it != queue1.end(); it++)
	{
		cout << "begin-end -> " << getStringFromU8string(*it) << endl;
	}

	// cbegin-cend
	for (auto it = queue1.cbegin(); it != queue1.cend(); it++)
	{
		cout << "cbegin-cend -> " << getStringFromU8string(*it) << endl;
	}

	// rbegin-rend
	for (auto it = queue1.rbegin(); it != queue1.rend(); it++)
	{
		cout << "rbegin-rend -> " << getStringFromU8string(*it) << endl;
	}
}

时间复杂度

操作 时间复杂度 说明
push_front / pop_front O(1) 关键优势：在头部高效操作
push_back / pop_back O(1) 与 vector 相当
insert (中间) O(n) 在中间插入需要移动后续元素
erase (中间) O(n) 在中间删除需要移动后续元素
operator[] / at() O(1) 支持随机访问
front() / back() O(1) 访问首尾元素

其他

特性 std::deque std::vector
头部插入/删除 O(1) O(n) - 需要移动所有元素
尾部插入/删除 O(1) O(1) - 均摊
中间插入/删除 O(n) O(n)
随机访问 O(1) O(1)
内存布局 分段连续 完全连续
迭代器失效 插入/删除时，指向被移动元素的迭代器失效 尾部插入可能使所有迭代器失效（重新分配时）；其他插入/删除使后续迭代器失效
内存预留 不支持 reserve() 支持 reserve() 避免重新分配
# c++ # java # 开发语言
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

2026最新AI Agent高频面试题（分类型精简详解）

本文梳理AI Agent高频面试考点，覆盖基础概念、架构、推理规划、工具调用、记忆、RAG融合、多智能体与工程落地。区分Agent、Workflow与普通工具调用，讲解ReAct、Plan‑and‑Execute等主流范式，分析三级记忆机制与上下文溢出的解决办法，对比传统RAG与Agent‑RAG差异，介绍多智能体协作模式。同时总结落地痛点、优化手段和安全风控要点，划分初/中/高级面试复习重点，可

avatar AI Agent技术社区
cover

深入理解 AI Agent · AGENT #03：从单 Agent 到多 Agent

avatar AI Agent技术社区
cover

AI Agent安全风险启示：工业巡检机器人的AI安全管控

avatar AI Agent技术社区