46 C++ STL模板库15-容器7-顺序容器-双端队列(deque)

STL模板库-容器7-容器适配器-双端队列(deque)

双端队列(deque) - 双向开口的连续线性空间（头尾插入/删除高效），支持随机访问.
头文件：#include <deque> .

一 成员类型

类型	说明
value_type	元素类型（如 int）
reference	value_type&
const_reference	const value_type&
iterator	随机访问迭代器（核心优势）
size_type	无符号整数（size()返回值类型）

二 构造函数

1. 函数说明

构造函数	用法示例	时间复杂度	适用场景
默认构造	deque<int> dq1;	O(1)	动态填充的空容器
填充构造	deque<int> dq2(5, 100); // 5个100	O(n)	初始化固定长度的默认值队列
范围构造	deque<int> dq3(arr, arr+3);	O(n)	转换已有数据为双端队列
拷贝构造	deque<int> dq4(dq3);	O(n)	创建独立副本
移动构造（C++11）	deque<int> dq5(std::move(dq4));	O(1)	高效转移资源
初始化列表（C++11）	deque<int> dq6{1,2,3};	O(n)	快速定义小型队列

2. 用法示例

1. 默认构造（创建空队列）

   std::deque<int> dq1;  // 创建空双端队列 
   dq1.push_back(10);     // 添加元素 
   std::cout << dq1[0];   // 输出: 10 
   

   场景：需要动态添加元素的初始容器

2. 填充构造（指定数量+默认值）

   // 创建含 5 个元素的队列，每个值为 100 
   std::deque<int> dq2(5, 100);  // 验证：输出所有元素 
   for (int val : dq2) std::cout << val << " ";  // 输出: 100 100 100 100 100 
   

   场景：初始化固定长度的缓冲区（如滑动窗口）

3. 范围构造（迭代器初始化）

   int arr[] = {7, 2, 5};
   // 用数组初始化队列 
   std::deque<int> dq3(arr, arr + sizeof(arr)/sizeof(arr[0]));  // 输出首尾元素 
   std::cout << dq3.front() << " " << dq3.back();  // 输出: 7 5 
   

   场景：将数组/容器数据转换为双端队列

4. 拷贝构造（复制已有队列）

   std::deque<char> origin{'A','B','C'};
   // 完整复制 origin 
   std::deque<char> dq4(origin);  // 修改副本不影响原队列 
   dq4[0] = 'X';
   std::cout << origin[0];  // 输出: A (原队列未变)
   

   场景：创建队列副本进行独立操作

5. 移动构造（高效转移资源）

   std::deque<std::string> temp{"Hi", "Bye"};
   // 转移 temp 的资源（原队列清空）
   std::deque<std::string> dq5(std::move(temp));  std::cout << "新队列: " << dq5[0]    // 输出: Hi << " | 原队列大小: " << temp.size();  // 输出: 0 
   

⚠️ 关键细节：

1. 移动构造后源队列失效（temp.empty() == true）
2. 初始化列表构造优先调用 initializer_list 构造函数
3. 迭代器范围构造支持所有容器类型（vector, list, 数组等）

三 元素访问

1. 函数说明

函数	说明	边界检查
operator[](size_type n)	访问索引n处元素	❌
at(size_type n)	访问索引n处元素	✅（越界抛异常）
front()	返回首元素	❌
back()	返回尾元素	❌

⚠️ at() 越界时抛出 std::out_of_range

2. 用法示例

1. 随机访问（operator[]）

• 无边界检查 - 高效但危险

  std::deque<int> dq{10, 20, 30};
  // 正常访问
  std::cout << dq[1];  // 输出：20
  // 越界访问（未定义行为！）
  // int val = dq[5];  // 可能崩溃或输出垃圾值 
  

2. 安全访问（at()）

• 带边界检查 - 越界时抛出异常

  try {std::cout << dq.at(0);  // 输出：10std::cout << dq.at(3);  // 抛出 std::out_of_range 
  } catch (const std::out_of_range& e) {std::cerr << "错误：" << e.what();  // 输出：deque::_M_range_check 
  }
  

3. 首尾访问（front()/back()）

• 高效获取端点元素

  dq.push_front(5);   // 队列：5,10,20,30
  dq.push_back(40);   // 队列：5,10,20,30,40 
  std::cout << "头部：" << dq.front()  // 5 << " | 尾部：" << dq.back(); // 40
  

4. 迭代器遍历

• 支持随机访问迭代器

  // 正向遍历 
  for (auto it = dq.begin(); it != dq.end(); ++it) {std::cout << *it << " ";  // 输出：5 10 20 30 40
  }
  // 反向遍历（C++11起）
  for (auto rit = dq.rbegin(); rit != dq.rend(); ++rit) {std::cout << *rit << " ";  // 输出：40 30 20 10 5 
  }
  

5. 范围循环（C++11）

• 简洁遍历语法

  // 只读访问 
  for (const auto& num : dq) {std::cout << num << " ";
  }
  // 修改元素
  for (auto& num : dq) {num *= 2;  // 所有元素翻倍
  }
  

3. 元素访问方法对比表

方法	示例	边界检查	时间复杂度	适用场景
随机访问	dq[2]	❌	O(1)	确定索引安全的快速访问
安全访问	dq.at(2)	✅（抛异常）	O(1)	需要防止越界的场景
首元素	dq.front()	❌	O(1)	队列处理（如FIFO）
尾元素	dq.back()	❌	O(1)	栈处理（如LIFO）
迭代器	*dq.begin()	隐式检查	O(1)	需要位置信息的遍历
范围循环	for (auto& x:dq)	自动边界	O(n)	简洁的完整遍历

四 容量操作

1. 函数说明

函数	说明	时间复杂度
bool empty() const	检查是否为空	O(1)
size_type size() const	返回元素数量	O(1)
void shrink_to_fit()	请求移除未使用容量（C++11）	O(n)
size_type max_size() const	返回最大可能元素数	O(1)

2. 用法示例

1. 判空操作 empty()

std::deque<std::string> messages;
// 检查队列是否为空 
if (messages.empty()) {  // 条件成立 std::cout << "消息队列为空，等待新数据...\n";
}
messages.push_back("Hello");
std::cout << "现在是否为空? " << (messages.empty() ? "是" : "否");  // 输出：否 

场景：处理任务队列前检查是否有待处理任务

2. 元素计数 size()

std::deque<int> sensorData{25, 18, 30, 22};
// 获取当前元素数量 
std::cout << "传感器数据量: " << sensorData.size();  // 输出：4 // 动态移除旧数据（保留最新3条）
while (sensorData.size() > 3) {sensorData.pop_front();
}
std::cout << "\n保留数据量: " << sensorData.size();  // 输出：3 

场景：实时数据流中维护固定长度的滑动窗口

3. 容量收缩 shrink_to_fit()

std::deque<double> buffer(1000, 0.0);  // 创建1000个元素的缓冲区 
buffer.erase(buffer.begin(), buffer.begin() + 900);  // 删除900个元素 
// 请求释放多余内存 
buffer.shrink_to_fit();

⚠️ 注意：
此操作仅为非强制性请求，实际效果取决于编译器实现

4. 最大容量 max_size()

std::deque<long> bigData;
std::cout << "系统支持最大元素数: " << bigData.max_size();  // 如输出：4611686018427387903(win10 GCC8.1.0)// 安全容量检查 
size_t planSize = 1'000'000'000;
if (planSize < bigData.max_size()) {bigData.resize(planSize);  // 安全分配 
} else {std::cerr << "超出系统支持范围!";
}

场景：大数据处理前验证系统支持上限

3. 容量操作对比表

操作	方法	时间复杂度	关键特性
检查是否为空	empty()	O(1)	比 size()==0 更语义化
获取元素数量	size()	O(1)	实时反映当前元素数
请求释放多余内存	shrink_to_fit()	O(n)	非强制，减少内存占用
查询系统支持上限	max_size()	O(1)	返回理论最大值（通常极大）

最佳实践推荐

1. 优先使用 empty() 而非 size()

   判空操作更清晰且部分实现中可能更高效

   // 推荐 ✔ 
   while (!tasks.empty()) { ... }// 不推荐 ✘ 
   while (tasks.size() > 0) { ... }
   

2. 内存管理策略

   // 批量删除后主动释放内存 
   dataDeque.erase(dataDeque.begin(), dataDeque.begin() + 1000);
   dataDeque.shrink_to_fit();  // 避免长期占用闲置内存 
   

3. 容量临界检测

   // 安全扩容检查 
   if (currentSize * 1.5 > deque.max_size()) {throw std::overflow_error("容量即将超出系统上限");
   }
   

4. 性能敏感场景

   • 频繁插入/删除时避免反复调用 size()（可缓存结果）
   • 超大容器操作前优先验证 max_size()

五 修改器（核心功能）

1. 函数说明

操作	函数签名	说明
尾部操作	push_back(const T& value) emplace_back(Args&&... args)（C++11）	尾部插入（高效）
	pop_back()	尾部删除
头部操作	push_front(const T& value) emplace_front(Args&&... args)（C++11）	头部插入（高效）
	pop_front()	头部删除
中间操作	insert(iterator pos, const T& value)	指定位置插入
删除	erase(iterator pos) erase(iterator first, iterator last)	删除元素
清空	void clear()	清空所有元素
交换	void swap(deque& other)	交换两个deque内容
替换	void assign(size_type n, const T& val)	替换所有元素为n个val
范围替换	void assign(InputIt first, InputIt last)	用迭代器范围替换元素

2. 用法示例

1. 高效首尾操作（O(1)复杂度）

1. 尾部插入

   deque<string> qs;
   // 传统拷贝插入 
   qs.push_back ("北京");// 高效直接构造（C++11）
   qs.emplace_back ("天津");
   // 等效于 push_back但避免临时对象拷贝 
   // 结果：[北京 天津]
   

2. 头部插入

   //头部插入
   qs.push_front("上海");  
   qs.emplace_front("上海"); 
   // 结果：[上海 上海 北京 天津]
   

3. 首尾删除

   if (!qs.empty())  qs.pop_front();   
   // 结果：[上海 北京 天津]// 尾部删除
   if (!qs.empty())  qs.pop_back(); 
   

   场景：实时日志系统（新日志尾部追加，系统通知头部插入，自动清理旧日志）

2. 中间元素操作（O(n)复杂度）

1. 定点插入

   std::deque<int> data{10, 30, 40};
   auto pos = data.begin() + 1;  // 指向30前 
   data.insert(pos, 20);         // 插入20 → [10,20,30,40]// 高效构造插入（避免拷贝）插入导致新增内存块，旧迭代器仍指向原块地址
   data.emplace(pos, 25);        // → [10,20,25,30,40]
   

2. 元素删除

   // 删除单个元素
   data.erase(data.begin() + 2);  // 移除25 → [10,20,30,40]// 批量删除范围 
   auto first = data.begin() + 1;
   auto last = data.end() - 1;
   data.erase(first, last);       // 保留首尾 → [10,40]
   

   场景：有序数据集维护（如实时插入温度读数并删除异常值）

3. 批量容器操作

1. 内容替换

   std::deque<char> buffer{'A','B','C'};// 替换为N个相同元素
   buffer.assign(3, 'X');  // → ['X','X','X']  // 用迭代器范围替换 
   std::vector vec{'D','E','F'};
   buffer.assign(vec.begin(), vec.end());  // → ['D','E','F']
   

2. 容器交换

   std::deque<int> a{1,2,3}, b{9,8};
   a.swap(b);  // O(1)操作
   // a → [9,8], b → [1,2,3]
   

3. 清空容器

   buffer.clear();  // 清空所有元素 
   std::cout << buffer.size();  // 输出: 0
   

4. 操作特性对比表

操作	方法	时间复杂度	关键优势
尾部插入	push_back() / emplace_back()	O(1)	避免拷贝（emplace）
头部插入	push_front() / emplace_front()	O(1)	高效头部操作
定点插入	insert() / emplace()	O(n)	灵活定位
范围删除	erase(first, last)	O(n)	批量清理
容器交换	swap()	O(1)	原子操作无元素复制
内存回收	clear()	O(n)	保留容器结构

• 注意事项

  1. 迭代器失效防护

     auto it = data.begin() + 2;
     data.push_front(0);     // ✘ it失效！
     // 正确做法：操作后重新获取迭代器
     it = data.begin() + 3;  // ✔️ 
     

  2. 安全删除模式

     // 防御空容器操作
     void safe_pop_front(std::deque<T>& dq) {if (!dq.empty()) dq.pop_front();
     }
     

  3. 内存优化技巧

     // 大容量清理后回收内存
     std::deque<int> temp;
     data.erase(old_start, old_end); 
     data.shrink_to_fit();          // 请求内存回收
     temp.swap(data);               // 强制内存释放（C++11前）
     

  4. 性能建议

     // 高频操作避免中间插入
     for (int i = 0; i < 10000; ++i) {// ✘ 避免: data.insert(mid_pos, i); // ✔️ 推荐: data.push_back(i); 
     }

六 迭代器操作

1. 函数说明

// 正向迭代器 
dq.begin();    dq.end();
dq.cbegin();   dq.cend();  // C++11// 反向迭代器
dq.rbegin();   dq.rend();
dq.crbegin();  dq.crend(); // C++11 

✅ 随机访问支持：
dq.begin() + 3 → 直接访问第4个元素

2. 用法示例

1. 正向迭代器操作

1. 非常量迭代器（修改元素）

   // 遍历并修改元素 
   for (auto it = tasks.begin(); it != tasks.end(); ++it) {*it = "[Urgent] " + *it;  // 添加紧急标记std::cout << *it << " → ";
   }
   // 输出：[Urgent] Design → [Urgent] Test → [Urgent] Deploy
   

2. 常量迭代器（安全只读访问）

   // 只读遍历（C++11起）
   for (auto cit = tasks.cbegin(); cit != tasks.cend(); ++cit) {// *cit = "Blocked";  // ❌ 编译错误（禁止修改）std::cout << *cit << " | ";
   }
   // 输出：[Urgent] Design | [Urgent] Test | [Urgent] Deploy
   

2. 反向迭代器操作

1. 反向遍历（从尾到头）

   // 反向输出任务序列
   std::cout << "\nReverse: ";
   for (auto rit = tasks.rbegin(); rit != tasks.rend(); ++rit) {std::cout << *rit << " ← ";
   }
   // 输出：Deploy ← Test ← Design ←
   

2. 常量反向迭代器

   // 只读反向访问（C++11）
   auto crit = tasks.crbegin();
   std::cout << "\nLast task: " << *crit;  // 输出：Deploy
   

3. 迭代器底层原理

   迭代器操作	物理指向	逻辑位置
   begin()	内存块1的首元素地址	队列头部
   end()	末元素后方的虚拟位置	尾部哨兵位
   rbegin()	内存块3的末元素地址	队列尾部
   rend()	首元素前方的虚拟位置	头部哨兵位

4. 注意事项

1. 迭代器失效规则

   auto it = tasks.begin() + 1;  // 指向Test
   tasks.push_front("Plan");     // ✘ it失效！
   std::cout << *it;             // 未定义行为 
   

   • 安全操作：首尾插入仅影响部分迭代器，中间插入使全部失效

2. 类型推导最佳实践

   // 精确控制迭代器类型
   std::deque<std::string>::const_reverse_iterator crit;  // 替代auto 
   

3. C++11 统一迭代模型

   // 所有容器通用遍历模式 
   for (const auto& task : tasks) {}          // 正向只读
   for (auto rit = tasks.rbegin(); rit != tasks.rend(); ++rit) {}  // 显式反向