std::dequedouble-ended queue双端队列是 C 标准库中的序列容器定义在deque头文件中。它允许在两端高效地插入和删除同时支持随机访问。可以把它看作一个“可以在头部和尾部快速操作的动态数组”。1. 基本概念模板声明cpptemplate class T, class Allocator std::allocatorT class deque;T元素类型。Allocator分配器默认使用std::allocatorT。特点动态大小无需提前指定容量。在头部和尾部插入/删除元素的时间复杂度为O(1)均摊。支持随机访问operator[]和at()时间复杂度O(1)。在中间插入/删除元素时间复杂度O(n)。元素不是连续存储的而是分段连续。不提供capacity()和reserve()因为内存分段管理。迭代器是随机访问迭代器可用于std::sort等算法。2. 底层实现典型实现方式将元素存储在多个固定大小的连续内存块中。使用一个“中控数组”map来管理这些块的指针。当在头部或尾部插入元素时如果当前块已满就分配一个新块并更新中控数组。中控数组本身也可能需要重新分配但已有的元素块不会被移动因此指向元素的引用和指针通常不会失效除非在中间插入/删除。这种设计使得deque在两端操作非常高效同时又不像std::list那样每个元素都有额外的指针开销。3. 与 vector、list 的对比特性std::vectorstd::dequestd::list内存布局单块连续分段连续双向链表非连续随机访问O(1)O(1)O(n)尾部插入/删除均摊 O(1)均摊 O(1)O(1)头部插入/删除O(n)均摊 O(1)O(1)中间插入/删除O(n)O(n)O(1)迭代器类型随机访问随机访问双向引用/指针稳定性重新分配时失效两端操作不失效中间操作失效插入/删除不失效内存开销低中等中控数组块高每元素两个指针是否支持sort是是否需用list::sort4. 常用成员函数函数说明push_back(val)/emplace_back(args...)在尾部插入元素push_front(val)/emplace_front(args...)在头部插入元素pop_back()删除尾部元素pop_front()删除头部元素at(pos)带边界检查的访问越界抛std::out_of_rangeoperator[](pos)无边界检查的访问front()/back()返回首/尾元素的引用size()/empty()元素个数 / 是否为空clear()清空所有元素insert(pos, val)在指定位置插入元素erase(pos)删除指定位置元素begin()/end()迭代器rbegin()/rend()反向迭代器shrink_to_fit()请求释放未使用的内存C115. 迭代器失效规则在两端插入元素所有迭代器失效但引用和指针不失效。在两端删除元素只有指向被删除元素的迭代器、引用、指针失效。在中间插入/删除元素所有迭代器、引用、指针都失效。重新分配中控数组可能使迭代器失效但元素本身不移动引用仍有效。因此如果需要长期持有指向deque元素的引用应避免在中间进行插入/删除。#include deque #include iostream #include algorithm // std::sort int main() { std::dequeint dq; // 1. 从两端插入元素 dq.push_back(10); dq.push_back(20); dq.push_front(5); dq.push_front(1); std::cout 初始 deque: ; for (int x : dq) std::cout x ; std::cout \n大小: dq.size() \n; // 2. 随机访问 std::cout d[0] dq[0] , d.at(2) dq.at(2) \n; // 3. 修改元素 dq[1] 100; dq.at(2) 200; std::cout 修改后: ; for (int x : dq) std::cout x ; std::cout \n; // 4. 从两端删除 dq.pop_front(); dq.pop_back(); std::cout pop后: ; for (int x : dq) std::cout x ; std::cout \n; // 5. 排序deque 支持随机访问迭代器 std::sort(dq.begin(), dq.end()); std::cout 排序后: ; for (int x : dq) std::cout x ; std::cout \n; // 6. 在中间插入和删除 auto it dq.begin(); it; // 指向第二个元素 dq.insert(it, 99); // 在第二个元素前插入99 std::cout 插入99后: ; for (int x : dq) std::cout x ; std::cout \n; dq.erase(dq.begin()); // 删除第一个元素 std::cout 删除第一个后: ; for (int x : dq) std::cout x ; std::cout \n; return 0; }