1. 项目概述从容器到适配器的思维跃迁在C的日常开发中我们经常和vector、list打交道它们是构建程序数据骨架的基础。但当你需要更灵活的数据进出方式或者需要一种能自动“排序”的队列时基础序列容器就显得力不从心了。这时deque双端队列和priority_queue优先级队列就该登场了。很多人把它们当作两个孤立的容器来学但实际上它们是STL设计哲学中“适配器模式”和“泛型算法”的绝佳体现。deque是vector和list特性的一种折中与融合而priority_queue则是在底层容器通常是vector或deque之上披上了一层“堆”算法的外衣其核心排序逻辑更是离不开“仿函数”这一利器。这篇文章我将从一个有多年踩坑经验的开发者视角带你彻底吃透这两个容器。不止是接口怎么用更重要的是拆解它们的设计意图、底层实现的关键细节比如deque那独特的“中控器”结构以及priority_queue堆调整中下标计算的来龙去脉并手把手展示如何用仿函数来定制priority_queue的行为。无论你是正在刷题准备面试还是在实际项目中需要处理滑动窗口最大值、任务调度等问题理解它们的内在机制都能让你写出更高效、更优雅的代码。2. 双端队列deque不是简单的vectorlistdeque全称double-ended queue支持在头部和尾部进行常数时间的插入和删除操作。乍一看它像是vector支持随机访问和list支持高效头插删的结合体但它的内部实现远比这复杂和精巧。2.1 deque的核心设计中控器与分段连续空间deque的底层并不是一块连续的线性空间而是由一段段定长的连续空间称为缓冲区或buffer拼接而成。这些缓冲区的地址由一个名为“中控器”的指针数组通常是一个vector来管理。中控器数组中的每个指针指向一块实际的缓冲区。这种设计是deque所有特性的根源高效的头尾操作因为缓冲区是定长的在头部或尾部添加元素时通常只需要在已有的缓冲区中分配空间或者申请一块新的缓冲区并更新中控器。这避免了vector在头部插入时需要整体挪动数据的O(n)开销。伪随机访问deque支持通过[]或at()进行随机访问。其内部通过计算目标元素位于第几个缓冲区buffer以及在该缓冲区内的偏移量来实现访问。虽然比vector的直接指针运算多一次间接寻址但仍然是常数时间复杂度O(1)。迭代器设计的复杂性deque的迭代器是一个“智能指针”它必须保存多个状态当前元素指针、当前缓冲区首尾指针、以及指向中控器中当前缓冲区指针的指针。这使得deque迭代器的自增、自减操作比vector迭代器复杂因为它可能需要跨越缓冲区边界。一个简化的deque内存布局想象图如下注意这是逻辑示意并非实际内存结构中控器 (Map) [ptr0] - Buffer0: [ ] [ ] [ ] [ ] [ ] // 可能未满 [ptr1] - Buffer1: [ ] [ ] [ ] [ ] [ ] // 可能未满 [ptr2] - Buffer2: [ ] [ ] [ ] [ ] [ ] // 可能未满 [ptr3] - Buffer3: [ ] [ ] [ ] [ ] [ ] // 可能未满 ...deque的begin()和end()迭代器会分别指向第一个有效元素和最后一个有效元素的下一个位置并记录当前所在的缓冲区。2.2 关键接口与性能分析deque的接口和vector非常相似但关键区别在于头部的操作push_front(e)/pop_front(): 在头部插入/删除元素。时间复杂度O(1)。这是相对于vector的最大优势。push_back(e)/pop_back(): 在尾部插入/删除元素。时间复杂度O(1)与vector相同。operator[]/at(index): 随机访问元素。时间复杂度O(1)但常数项比vector大。insert(pos, e): 在指定位置插入。由于可能引起元素移动时间复杂度为O(n)。虽然比vector在头部插入快但在中间插入的性能并不比vector有优势且由于迭代器更复杂实际开销可能更大。erase(pos): 删除指定位置元素。时间复杂度O(n)。实操心得deque的适用场景与陷阱何时使用deque当你需要一个既支持高效随机访问又需要频繁在序列两端进行插入删除操作的容器时deque是最佳选择。典型场景是实现“滑动窗口”算法、维护一个双端都需要操作的队列。避免中间操作尽管deque提供了insert和erase但除非万不得已不要频繁在中间位置进行这些操作。它的优势在两端中间操作的成本很高。迭代器失效规则deque的迭代器失效规则比vector和list都复杂。在头部或尾部插入元素通常不会使其他位置的迭代器失效。但在中间插入或删除元素会导致所有迭代器失效。这是因为插入删除可能导致缓冲区重新分配或元素大范围移动。安全起见在修改deque后最好重新获取迭代器。内存占用deque由于有中控器和可能未满的缓冲区其内存开销通常比vector大。如果对内存非常敏感且只需要尾部操作vectorreserve是更经济的选择。2.3 deque的迭代器一个复杂的“状态机”理解deque的迭代器有助于理解其行为。一个典型的deque迭代器可能包含以下成员概念上template class T struct _deque_iterator { T* cur; // 指向当前缓冲区中的当前元素 T* first; // 指向当前缓冲区的起始位置 T* last; // 指向当前缓冲区的末尾最后一个元素的下一个位置 T** node; // 指向中控器中管理当前缓冲区的那个指针 // ... 其他辅助函数 };当迭代器时cur向前移动。如果cur到达了last缓冲区末尾迭代器就需要跳转到下一个缓冲区通过node找到中控器中的下一个指针更新first、last和cur。--操作同理。这就是为什么说deque提供了随机访问迭代器但其迭代器的移动操作比vector的普通指针开销要大。3. 优先级队列priority_queue披着队列外衣的堆priority_queue优先级队列它虽然名字里带“队列”但和我们熟悉的先进先出(FIFO)的queue有本质区别。它保证每次从队头取出的元素都是当前队列中优先级最高的元素。它的底层实现通常基于“堆”(heap)这种数据结构。3.1 堆Heap数据结构快速回顾堆是一种特殊的完全二叉树它满足堆属性对于大顶堆每个节点的值都大于或等于其子节点的值对于小顶堆每个节点的值都小于或等于其子节点的值。完全二叉树有一个极其重要的特性它可以被高效地存储在一个数组中。对于数组下标从0开始的情况给定一个节点下标i其父节点下标为(i - 1) / 2向下取整其左孩子下标为2 * i 1其右孩子下标为2 * i 2给定一个节点下标i其父节点下标为i / 2其左孩子下标为2 * i其右孩子下标为2 * i 1priority_queue默认使用大顶堆即最大的元素在堆顶数组下标0处。3.2 priority_queue作为容器适配器priority_queue是一个典型的容器适配器。这意味着它不是在底层从头实现了一个堆而是基于一个已有的序列容器默认为vector通过一套算法主要是push_heap和pop_heap来维持堆的性质。它的模板声明清晰地体现了这一点template class T, class Container vectorT, class Compare lesstypename Container::value_type class priority_queue;T: 元素类型。Container: 底层容器类型必须满足序列容器的要求并提供front(),push_back(),pop_back()等接口。通常用vector或deque。Compare: 用于比较元素优先级的仿函数类型默认为less即形成大顶堆“小于”比较但堆顶是最大元素稍后详解。3.3 核心操作与底层堆算法详解priority_queue的接口非常简洁主要就是push、pop、top、empty、size。3.3.1 push(e) 与向上调整Sift Up当向priority_queue插入一个新元素时首先调用底层容器的push_back(e)将新元素追加到数组末尾。这可能会破坏堆的性质。然后执行“向上调整”算法使新元素“上浮”到正确的位置。算法过程比较新元素下标为child与其父节点下标为parent (child - 1) / 2的值。如果对于大顶堆新元素值大于父节点值即Compare()(parent_value, child_value)为真对于默认的less就是parent child则交换它们的位置。将child更新为parent重复上述过程直到child到达根节点下标0或者不满足交换条件为止。时间复杂度O(log n)因为完全二叉树的高度是log n。3.3.2 pop() 与向下调整Sift Down当从priority_queue弹出堆顶元素时实际上并不是直接删除c[0]。因为直接删除数组头部元素需要移动后面所有元素成本是O(n)。标准做法是将堆顶元素c[0]与数组最后一个元素c.back()交换。调用底层容器的pop_back()移除原堆顶元素现在在末尾。此时新的堆顶元素原最后一个元素可能破坏了堆的性质。执行“向下调整”算法使其“下沉”。算法过程从根节点parent 0开始找出其左右孩子中优先级更高的那个对于大顶堆就是值更大的孩子记为child。比较parent和child的值。如果parent的优先级低于child对于大顶堆即parent child则交换它们。将parent更新为child重复上述过程直到parent到达叶子节点或者不满足交换条件为止。时间复杂度O(log n)。3.3.3 top()、empty()、size()top(): 直接返回底层容器的c.front()即c[0]。时间复杂度O(1)。empty(): 返回底层容器的empty()。时间复杂度O(1)。size(): 返回底层容器的size()。时间复杂度O(1)。注意事项pop()不返回值的陷阱priority_queue的pop()函数返回类型是void。它只移除堆顶元素并不返回它。如果你需要获取被移除的元素必须先用top()获取再调用pop()。// 错误pop()不返回值 // int max_val my_pq.pop(); // 正确做法 int max_val my_pq.top(); my_pq.pop();4. 仿函数Functor让算法拥有“可配置的比较逻辑”仿函数也叫函数对象是STL六大组件之一。它本质是一个类或结构体但重载了函数调用运算符operator()使得这个类的对象可以像函数一样被调用。4.1 为什么需要仿函数对比函数指针在C语言中如果我们想给qsort传递自定义的比较规则需要传递一个函数指针。C的仿函数提供了更优的解决方案可内联性仿函数是类对象其operator()可以被编译器内联。而通过函数指针调用函数编译器通常难以进行内联优化。在priority_queue或sort这种需要频繁调用比较操作的场景性能差异可能显现。可携带状态仿函数作为类可以拥有成员变量从而在多次调用间保持状态。例如一个记录比较次数的仿函数。类型安全仿函数是模板参数在编译期确定类型比运行时函数指针更安全。4.2 STL内置仿函数与自定义仿函数STL在functional头文件中定义了许多内置仿函数算术仿函数plusT,minusT,multipliesT,dividesT,modulusT,negateT。关系仿函数equal_toT,not_equal_toT,greaterT,lessT,greater_equalT,less_equalT。priority_queue默认使用lessT来构建大顶堆这有点反直觉需要理解堆算法中比较操作用于判断是否应该交换父子节点。默认情况下它检查父节点是否“小于”子节点如果是就交换最终保证了根节点是最大的。逻辑仿函数logical_andT,logical_orT,logical_notT。自定义仿函数示例实现一个按绝对值大小排序的priority_queue绝对值大的优先级高。#include queue #include vector #include iostream #include cmath // for abs struct AbsLess { // 注意我们希望构建大顶堆所以“优先级高”的元素应该排在前面。 // 在比较函数中如果a的优先级低于b则返回true。 // 对于按绝对值排序的大顶堆如果 |a| |b|则a的优先级低于b。 bool operator()(int a, int b) const { return std::abs(a) std::abs(b); } }; int main() { // 使用自定义仿函数注意模板参数顺序元素类型、底层容器、比较仿函数类型 std::priority_queueint, std::vectorint, AbsLess pq; pq.push(-5); pq.push(3); pq.push(-1); pq.push(7); while (!pq.empty()) { std::cout pq.top() ; // 输出7 -5 3 -1 pq.pop(); } return 0; }4.3 仿函数在priority_queue中的核心作用在priority_queue的模板声明中第三个参数Compare就是仿函数类型。这个仿函数决定了堆中元素的“优先级”顺序。Compare是一个二元谓词它接受两个参数a和b。其返回值意义为如果a的优先级严格低于b则返回true。对于大顶堆默认我们希望值大的元素优先级高。STL默认使用lessT。那么当a b为true时说明a的优先级低于b所以在堆调整中b应该放在a的上层。最终根节点是最大值。对于小顶堆我们希望值小的元素优先级高。我们需要使用greaterT。当a b为true时说明a的优先级低于b因为a更大所以b更小的值应该放在上层。最终根节点是最小值。// 大顶堆默认 std::priority_queueint max_heap; // 等价于 std::priority_queueint, std::vectorint, std::lessint // 小顶堆需要显式指定比较器 std::priority_queueint, std::vectorint, std::greaterint min_heap;理解了这个逻辑你就能正确地编写任何自定义优先级的比较仿函数了。核心口诀仿函数返回true意味着第一个参数的优先级低于第二个参数。5. 模拟实现一个简易的priority_queue为了彻底理解priority_queue和仿函数最好的方式就是自己动手实现一个简化版。我们将它命名为MyPriorityQueue。5.1 类框架与模板定义首先定义类模板包含三个模板参数元素类型T底层容器Container默认为vectorT比较仿函数Compare默认为lessT。#include vector #include functional // for std::less namespace my { template class T, class Container std::vectorT, class Compare std::lesstypename Container::value_type class priority_queue { private: Container _con; // 底层容器 Compare _comp; // 比较仿函数对象 // 内部辅助函数向上调整、向下调整 void _adjust_up(size_t child); void _adjust_down(size_t parent); public: // 构造函数 priority_queue() default; template class InputIterator priority_queue(InputIterator first, InputIterator last); // 容量操作 bool empty() const; size_t size() const; // 元素访问 const T top() const; // 修改操作 void push(const T val); void pop(); }; }5.2 核心辅助函数向上调整与向下调整这两个函数是堆算法的核心它们利用了我们之前讲过的父子节点下标计算公式。5.2.1 _adjust_up(size_t child)template class T, class Container, class Compare void my::priority_queueT, Container, Compare::_adjust_up(size_t child) { while (child 0) { size_t parent (child - 1) / 2; // 计算父节点下标 // 如果孩子节点的优先级不低于父节点则停止调整 // 注意_comp(parent_val, child_val) 为true 表示父节点优先级低于子节点需要交换 if (!_comp(_con[parent], _con[child])) { break; } std::swap(_con[parent], _con[child]); child parent; // 继续向上比较 } }关键点解析循环条件child 0当孩子节点到达根节点下标0时停止。计算父节点下标(child - 1) / 2。这是完全二叉树在数组表示中的核心公式。比较逻辑_comp(_con[parent], _con[child])。如果返回true表示父节点优先级低于子节点对于默认大顶堆就是父节点值小于子节点。此时需要交换让优先级高的元素上去。使用std::swap进行交换然后更新child索引为parent继续向上迭代。5.2.2 _adjust_down(size_t parent)template class T, class Container, class Compare void my::priority_queueT, Container, Compare::_adjust_down(size_t parent) { size_t child parent * 2 1; // 先假设左孩子为候选 size_t n size(); while (child n) { // 如果右孩子存在且右孩子优先级比左孩子高则更新候选孩子为右孩子 if (child 1 n _comp(_con[child], _con[child 1])) { child; // child 现在指向右孩子 } // 如果父节点优先级不低于候选孩子则调整结束 if (!_comp(_con[parent], _con[child])) { break; } std::swap(_con[parent], _con[child]); parent child; child parent * 2 1; // 继续向下调整 } }关键点解析初始化child为左孩子parent * 2 1。循环条件child n确保孩子索引有效。选择优先级更高的孩子如果右孩子存在(child1 n)并且右孩子的优先级高于左孩子_comp(_con[child], _con[child 1])为真则将child更新为右孩子索引。这一步确保了总是与优先级更高的那个孩子进行比较和可能的交换。比较与交换逻辑和向上调整类似如果父节点优先级低于选中的孩子则交换。更新索引交换后原父节点下沉到了child位置所以将parent更新为child并重新计算其左孩子索引继续循环。5.3 对外接口的实现有了核心的调整函数其他接口的实现就水到渠成了。// 构造函数用迭代器范围构造并建堆 template class T, class Container, class Compare template class InputIterator my::priority_queueT, Container, Compare::priority_queue(InputIterator first, InputIterator last) : _con(first, last) { // 从最后一个非叶子节点开始向前逐个进行向下调整构建堆 // 最后一个非叶子节点下标为 (size() - 2) / 2 for (int i (size() - 2) / 2; i 0; --i) { _adjust_down(i); } } template class T, class Container, class Compare bool my::priority_queueT, Container, Compare::empty() const { return _con.empty(); } template class T, class Container, class Compare size_t my::priority_queueT, Container, Compare::size() const { return _con.size(); } template class T, class Container, class Compare const T my::priority_queueT, Container, Compare::top() const { // 调用前最好检查非空这里省略了 return _con.front(); } template class T, class Container, class Compare void my::priority_queueT, Container, Compare::push(const T val) { _con.push_back(val); // 1. 尾插 _adjust_up(size() - 1); // 2. 向上调整最后一个元素 } template class T, class Container, class Compare void my::priority_queueT, Container, Compare::pop() { if (empty()) return; // 处理空队列 std::swap(_con[0], _con[size() - 1]); // 1. 交换堆顶与堆尾 _con.pop_back(); // 2. 删除原堆顶现堆尾 if (!empty()) { _adjust_down(0); // 3. 对新的堆顶进行向下调整 } }实操心得建堆的时间复杂度在接收迭代器范围的构造函数中我们通过从最后一个非叶子节点开始向下调整来建堆。这个方法的时间复杂度是O(n)而不是直觉上的O(n log n)。这是一个经典的算法结论。相比之下如果通过连续pushn个元素来建堆时间复杂度是O(n log n)。因此如果已知所有元素使用范围构造函数效率更高。6. 综合应用与常见问题排查理解了原理和实现我们来看看如何在实际中应用它们以及会遇到哪些坑。6.1 典型应用场景1. 使用deque处理滑动窗口最大值LeetCode 239这是deque的经典应用。我们需要维护一个窗口并快速获取窗口内的最大值。一个高效的解法是使用一个双端队列deque来存储可能成为窗口最大值的元素的索引且队列中的索引对应的值是递减的。vectorint maxSlidingWindow(vectorint nums, int k) { vectorint res; dequeint dq; // 存储的是下标 for (int i 0; i nums.size(); i) { // 1. 维护队列如果队头索引已不在窗口内弹出 if (!dq.empty() dq.front() i - k) { dq.pop_front(); } // 2. 维护队列从队尾开始弹出所有小于当前值的索引它们不可能是最大值了 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } // 3. 当前索引入队 dq.push_back(i); // 4. 当窗口形成后记录结果队头即最大值索引 if (i k - 1) { res.push_back(nums[dq.front()]); } } return res; }这里充分利用了deque在两端pop的O(1)复杂度。2. 使用priority_queue实现Top K问题或任务调度例如从海量数据中找出前K个最大的数。我们可以维护一个大小为K的小顶堆。vectorint topK(vectorint nums, int k) { if (k 0) return {}; // 小顶堆堆顶是当前堆中最小的数即第K大的候选者中最弱的一个 priority_queueint, vectorint, greaterint min_heap; for (int num : nums) { if (min_heap.size() k) { min_heap.push(num); } else if (num min_heap.top()) { // 如果新数比堆顶当前第K大大则替换它 min_heap.pop(); min_heap.push(num); } } // 最后堆中剩下的就是最大的K个数但不一定有序 vectorint res; while (!min_heap.empty()) { res.push_back(min_heap.top()); min_heap.pop(); } // 如果需要从大到小排序需要反转一下 reverse(res.begin(), res.end()); return res; }6.2 常见问题与排查技巧问题1自定义类型放入priority_queue编译报错“无效的模板参数”或“没有匹配的operator”。原因priority_queue默认使用lessT它依赖于operator来比较元素。如果你的自定义类型没有重载operator或者你使用了自定义仿函数但仿函数的operator()不是const成员函数就会出错。解决为你的自定义类型重载operator。或者在声明priority_queue时提供一个正确的自定义仿函数类型并确保其operator()是const的。struct MyType { int id; int priority; // 方法1重载 operator bool operator(const MyType other) const { // 定义你的比较逻辑比如按priority比较 return priority other.priority; // 大顶堆 } }; // 使用默认比较 // priority_queueMyType pq; // 方法2使用自定义仿函数 struct CompareMyTypeById { bool operator()(const MyType a, const MyType b) const { // 注意const return a.id b.id; // 按id小顶堆 } }; priority_queueMyType, vectorMyType, CompareMyTypeById pq;问题2priority_queue里存的是指针但排序结果不符合预期。原因默认的less对指针比较的是地址大小而不是指针所指向对象的值。解决必须提供自定义仿函数来解引用指针并比较。struct PtrCompare { bool operator()(const MyType* a, const MyType* b) const { // 假设MyType有value成员 return a-value b-value; // 大顶堆 } }; priority_queueMyType*, vectorMyType*, PtrCompare pq;问题3在循环中同时使用top()和pop()但有时pop()后程序崩溃。原因可能是在pop()一个空的priority_queue。top()在队列为空时是未定义行为UB而pop()在空队列上也是UB。解决在调用top()或pop()之前务必检查队列是否为空。while (!pq.empty()) { auto val pq.top(); // 安全 pq.pop(); // 安全 // ... 处理val }问题4使用deque的迭代器时程序在某些操作后出现随机错误。原因极有可能是迭代器失效。记住deque的迭代器失效规则在头部或尾部插入/删除通常不会使其他迭代器失效但指向被删除元素的迭代器肯定失效。在中间进行insert或erase会导致所有迭代器失效。解决如果需要在中间频繁插入删除考虑使用list。如果必须用deque并在修改后还需要使用迭代器最安全的做法是重新获取迭代器例如it dq.begin();。问题5自定义仿函数看起来没问题但priority_queue排序结果完全反了。原因混淆了比较逻辑。牢记仿函数Comp(a, b)返回true表示a的优先级低于b。如果你想实现小顶堆值小的优先级高那么当a b时a的优先级低于b所以仿函数应该返回a b即使用greater。排查画一个小例子比如三个数手动模拟一下堆的调整过程检查你的仿函数在每次比较时返回的布尔值是否符合你期望的优先级关系。
C++ STL deque与priority_queue：从容器适配器到堆算法的深度解析
1. 项目概述从容器到适配器的思维跃迁在C的日常开发中我们经常和vector、list打交道它们是构建程序数据骨架的基础。但当你需要更灵活的数据进出方式或者需要一种能自动“排序”的队列时基础序列容器就显得力不从心了。这时deque双端队列和priority_queue优先级队列就该登场了。很多人把它们当作两个孤立的容器来学但实际上它们是STL设计哲学中“适配器模式”和“泛型算法”的绝佳体现。deque是vector和list特性的一种折中与融合而priority_queue则是在底层容器通常是vector或deque之上披上了一层“堆”算法的外衣其核心排序逻辑更是离不开“仿函数”这一利器。这篇文章我将从一个有多年踩坑经验的开发者视角带你彻底吃透这两个容器。不止是接口怎么用更重要的是拆解它们的设计意图、底层实现的关键细节比如deque那独特的“中控器”结构以及priority_queue堆调整中下标计算的来龙去脉并手把手展示如何用仿函数来定制priority_queue的行为。无论你是正在刷题准备面试还是在实际项目中需要处理滑动窗口最大值、任务调度等问题理解它们的内在机制都能让你写出更高效、更优雅的代码。2. 双端队列deque不是简单的vectorlistdeque全称double-ended queue支持在头部和尾部进行常数时间的插入和删除操作。乍一看它像是vector支持随机访问和list支持高效头插删的结合体但它的内部实现远比这复杂和精巧。2.1 deque的核心设计中控器与分段连续空间deque的底层并不是一块连续的线性空间而是由一段段定长的连续空间称为缓冲区或buffer拼接而成。这些缓冲区的地址由一个名为“中控器”的指针数组通常是一个vector来管理。中控器数组中的每个指针指向一块实际的缓冲区。这种设计是deque所有特性的根源高效的头尾操作因为缓冲区是定长的在头部或尾部添加元素时通常只需要在已有的缓冲区中分配空间或者申请一块新的缓冲区并更新中控器。这避免了vector在头部插入时需要整体挪动数据的O(n)开销。伪随机访问deque支持通过[]或at()进行随机访问。其内部通过计算目标元素位于第几个缓冲区buffer以及在该缓冲区内的偏移量来实现访问。虽然比vector的直接指针运算多一次间接寻址但仍然是常数时间复杂度O(1)。迭代器设计的复杂性deque的迭代器是一个“智能指针”它必须保存多个状态当前元素指针、当前缓冲区首尾指针、以及指向中控器中当前缓冲区指针的指针。这使得deque迭代器的自增、自减操作比vector迭代器复杂因为它可能需要跨越缓冲区边界。一个简化的deque内存布局想象图如下注意这是逻辑示意并非实际内存结构中控器 (Map) [ptr0] - Buffer0: [ ] [ ] [ ] [ ] [ ] // 可能未满 [ptr1] - Buffer1: [ ] [ ] [ ] [ ] [ ] // 可能未满 [ptr2] - Buffer2: [ ] [ ] [ ] [ ] [ ] // 可能未满 [ptr3] - Buffer3: [ ] [ ] [ ] [ ] [ ] // 可能未满 ...deque的begin()和end()迭代器会分别指向第一个有效元素和最后一个有效元素的下一个位置并记录当前所在的缓冲区。2.2 关键接口与性能分析deque的接口和vector非常相似但关键区别在于头部的操作push_front(e)/pop_front(): 在头部插入/删除元素。时间复杂度O(1)。这是相对于vector的最大优势。push_back(e)/pop_back(): 在尾部插入/删除元素。时间复杂度O(1)与vector相同。operator[]/at(index): 随机访问元素。时间复杂度O(1)但常数项比vector大。insert(pos, e): 在指定位置插入。由于可能引起元素移动时间复杂度为O(n)。虽然比vector在头部插入快但在中间插入的性能并不比vector有优势且由于迭代器更复杂实际开销可能更大。erase(pos): 删除指定位置元素。时间复杂度O(n)。实操心得deque的适用场景与陷阱何时使用deque当你需要一个既支持高效随机访问又需要频繁在序列两端进行插入删除操作的容器时deque是最佳选择。典型场景是实现“滑动窗口”算法、维护一个双端都需要操作的队列。避免中间操作尽管deque提供了insert和erase但除非万不得已不要频繁在中间位置进行这些操作。它的优势在两端中间操作的成本很高。迭代器失效规则deque的迭代器失效规则比vector和list都复杂。在头部或尾部插入元素通常不会使其他位置的迭代器失效。但在中间插入或删除元素会导致所有迭代器失效。这是因为插入删除可能导致缓冲区重新分配或元素大范围移动。安全起见在修改deque后最好重新获取迭代器。内存占用deque由于有中控器和可能未满的缓冲区其内存开销通常比vector大。如果对内存非常敏感且只需要尾部操作vectorreserve是更经济的选择。2.3 deque的迭代器一个复杂的“状态机”理解deque的迭代器有助于理解其行为。一个典型的deque迭代器可能包含以下成员概念上template class T struct _deque_iterator { T* cur; // 指向当前缓冲区中的当前元素 T* first; // 指向当前缓冲区的起始位置 T* last; // 指向当前缓冲区的末尾最后一个元素的下一个位置 T** node; // 指向中控器中管理当前缓冲区的那个指针 // ... 其他辅助函数 };当迭代器时cur向前移动。如果cur到达了last缓冲区末尾迭代器就需要跳转到下一个缓冲区通过node找到中控器中的下一个指针更新first、last和cur。--操作同理。这就是为什么说deque提供了随机访问迭代器但其迭代器的移动操作比vector的普通指针开销要大。3. 优先级队列priority_queue披着队列外衣的堆priority_queue优先级队列它虽然名字里带“队列”但和我们熟悉的先进先出(FIFO)的queue有本质区别。它保证每次从队头取出的元素都是当前队列中优先级最高的元素。它的底层实现通常基于“堆”(heap)这种数据结构。3.1 堆Heap数据结构快速回顾堆是一种特殊的完全二叉树它满足堆属性对于大顶堆每个节点的值都大于或等于其子节点的值对于小顶堆每个节点的值都小于或等于其子节点的值。完全二叉树有一个极其重要的特性它可以被高效地存储在一个数组中。对于数组下标从0开始的情况给定一个节点下标i其父节点下标为(i - 1) / 2向下取整其左孩子下标为2 * i 1其右孩子下标为2 * i 2给定一个节点下标i其父节点下标为i / 2其左孩子下标为2 * i其右孩子下标为2 * i 1priority_queue默认使用大顶堆即最大的元素在堆顶数组下标0处。3.2 priority_queue作为容器适配器priority_queue是一个典型的容器适配器。这意味着它不是在底层从头实现了一个堆而是基于一个已有的序列容器默认为vector通过一套算法主要是push_heap和pop_heap来维持堆的性质。它的模板声明清晰地体现了这一点template class T, class Container vectorT, class Compare lesstypename Container::value_type class priority_queue;T: 元素类型。Container: 底层容器类型必须满足序列容器的要求并提供front(),push_back(),pop_back()等接口。通常用vector或deque。Compare: 用于比较元素优先级的仿函数类型默认为less即形成大顶堆“小于”比较但堆顶是最大元素稍后详解。3.3 核心操作与底层堆算法详解priority_queue的接口非常简洁主要就是push、pop、top、empty、size。3.3.1 push(e) 与向上调整Sift Up当向priority_queue插入一个新元素时首先调用底层容器的push_back(e)将新元素追加到数组末尾。这可能会破坏堆的性质。然后执行“向上调整”算法使新元素“上浮”到正确的位置。算法过程比较新元素下标为child与其父节点下标为parent (child - 1) / 2的值。如果对于大顶堆新元素值大于父节点值即Compare()(parent_value, child_value)为真对于默认的less就是parent child则交换它们的位置。将child更新为parent重复上述过程直到child到达根节点下标0或者不满足交换条件为止。时间复杂度O(log n)因为完全二叉树的高度是log n。3.3.2 pop() 与向下调整Sift Down当从priority_queue弹出堆顶元素时实际上并不是直接删除c[0]。因为直接删除数组头部元素需要移动后面所有元素成本是O(n)。标准做法是将堆顶元素c[0]与数组最后一个元素c.back()交换。调用底层容器的pop_back()移除原堆顶元素现在在末尾。此时新的堆顶元素原最后一个元素可能破坏了堆的性质。执行“向下调整”算法使其“下沉”。算法过程从根节点parent 0开始找出其左右孩子中优先级更高的那个对于大顶堆就是值更大的孩子记为child。比较parent和child的值。如果parent的优先级低于child对于大顶堆即parent child则交换它们。将parent更新为child重复上述过程直到parent到达叶子节点或者不满足交换条件为止。时间复杂度O(log n)。3.3.3 top()、empty()、size()top(): 直接返回底层容器的c.front()即c[0]。时间复杂度O(1)。empty(): 返回底层容器的empty()。时间复杂度O(1)。size(): 返回底层容器的size()。时间复杂度O(1)。注意事项pop()不返回值的陷阱priority_queue的pop()函数返回类型是void。它只移除堆顶元素并不返回它。如果你需要获取被移除的元素必须先用top()获取再调用pop()。// 错误pop()不返回值 // int max_val my_pq.pop(); // 正确做法 int max_val my_pq.top(); my_pq.pop();4. 仿函数Functor让算法拥有“可配置的比较逻辑”仿函数也叫函数对象是STL六大组件之一。它本质是一个类或结构体但重载了函数调用运算符operator()使得这个类的对象可以像函数一样被调用。4.1 为什么需要仿函数对比函数指针在C语言中如果我们想给qsort传递自定义的比较规则需要传递一个函数指针。C的仿函数提供了更优的解决方案可内联性仿函数是类对象其operator()可以被编译器内联。而通过函数指针调用函数编译器通常难以进行内联优化。在priority_queue或sort这种需要频繁调用比较操作的场景性能差异可能显现。可携带状态仿函数作为类可以拥有成员变量从而在多次调用间保持状态。例如一个记录比较次数的仿函数。类型安全仿函数是模板参数在编译期确定类型比运行时函数指针更安全。4.2 STL内置仿函数与自定义仿函数STL在functional头文件中定义了许多内置仿函数算术仿函数plusT,minusT,multipliesT,dividesT,modulusT,negateT。关系仿函数equal_toT,not_equal_toT,greaterT,lessT,greater_equalT,less_equalT。priority_queue默认使用lessT来构建大顶堆这有点反直觉需要理解堆算法中比较操作用于判断是否应该交换父子节点。默认情况下它检查父节点是否“小于”子节点如果是就交换最终保证了根节点是最大的。逻辑仿函数logical_andT,logical_orT,logical_notT。自定义仿函数示例实现一个按绝对值大小排序的priority_queue绝对值大的优先级高。#include queue #include vector #include iostream #include cmath // for abs struct AbsLess { // 注意我们希望构建大顶堆所以“优先级高”的元素应该排在前面。 // 在比较函数中如果a的优先级低于b则返回true。 // 对于按绝对值排序的大顶堆如果 |a| |b|则a的优先级低于b。 bool operator()(int a, int b) const { return std::abs(a) std::abs(b); } }; int main() { // 使用自定义仿函数注意模板参数顺序元素类型、底层容器、比较仿函数类型 std::priority_queueint, std::vectorint, AbsLess pq; pq.push(-5); pq.push(3); pq.push(-1); pq.push(7); while (!pq.empty()) { std::cout pq.top() ; // 输出7 -5 3 -1 pq.pop(); } return 0; }4.3 仿函数在priority_queue中的核心作用在priority_queue的模板声明中第三个参数Compare就是仿函数类型。这个仿函数决定了堆中元素的“优先级”顺序。Compare是一个二元谓词它接受两个参数a和b。其返回值意义为如果a的优先级严格低于b则返回true。对于大顶堆默认我们希望值大的元素优先级高。STL默认使用lessT。那么当a b为true时说明a的优先级低于b所以在堆调整中b应该放在a的上层。最终根节点是最大值。对于小顶堆我们希望值小的元素优先级高。我们需要使用greaterT。当a b为true时说明a的优先级低于b因为a更大所以b更小的值应该放在上层。最终根节点是最小值。// 大顶堆默认 std::priority_queueint max_heap; // 等价于 std::priority_queueint, std::vectorint, std::lessint // 小顶堆需要显式指定比较器 std::priority_queueint, std::vectorint, std::greaterint min_heap;理解了这个逻辑你就能正确地编写任何自定义优先级的比较仿函数了。核心口诀仿函数返回true意味着第一个参数的优先级低于第二个参数。5. 模拟实现一个简易的priority_queue为了彻底理解priority_queue和仿函数最好的方式就是自己动手实现一个简化版。我们将它命名为MyPriorityQueue。5.1 类框架与模板定义首先定义类模板包含三个模板参数元素类型T底层容器Container默认为vectorT比较仿函数Compare默认为lessT。#include vector #include functional // for std::less namespace my { template class T, class Container std::vectorT, class Compare std::lesstypename Container::value_type class priority_queue { private: Container _con; // 底层容器 Compare _comp; // 比较仿函数对象 // 内部辅助函数向上调整、向下调整 void _adjust_up(size_t child); void _adjust_down(size_t parent); public: // 构造函数 priority_queue() default; template class InputIterator priority_queue(InputIterator first, InputIterator last); // 容量操作 bool empty() const; size_t size() const; // 元素访问 const T top() const; // 修改操作 void push(const T val); void pop(); }; }5.2 核心辅助函数向上调整与向下调整这两个函数是堆算法的核心它们利用了我们之前讲过的父子节点下标计算公式。5.2.1 _adjust_up(size_t child)template class T, class Container, class Compare void my::priority_queueT, Container, Compare::_adjust_up(size_t child) { while (child 0) { size_t parent (child - 1) / 2; // 计算父节点下标 // 如果孩子节点的优先级不低于父节点则停止调整 // 注意_comp(parent_val, child_val) 为true 表示父节点优先级低于子节点需要交换 if (!_comp(_con[parent], _con[child])) { break; } std::swap(_con[parent], _con[child]); child parent; // 继续向上比较 } }关键点解析循环条件child 0当孩子节点到达根节点下标0时停止。计算父节点下标(child - 1) / 2。这是完全二叉树在数组表示中的核心公式。比较逻辑_comp(_con[parent], _con[child])。如果返回true表示父节点优先级低于子节点对于默认大顶堆就是父节点值小于子节点。此时需要交换让优先级高的元素上去。使用std::swap进行交换然后更新child索引为parent继续向上迭代。5.2.2 _adjust_down(size_t parent)template class T, class Container, class Compare void my::priority_queueT, Container, Compare::_adjust_down(size_t parent) { size_t child parent * 2 1; // 先假设左孩子为候选 size_t n size(); while (child n) { // 如果右孩子存在且右孩子优先级比左孩子高则更新候选孩子为右孩子 if (child 1 n _comp(_con[child], _con[child 1])) { child; // child 现在指向右孩子 } // 如果父节点优先级不低于候选孩子则调整结束 if (!_comp(_con[parent], _con[child])) { break; } std::swap(_con[parent], _con[child]); parent child; child parent * 2 1; // 继续向下调整 } }关键点解析初始化child为左孩子parent * 2 1。循环条件child n确保孩子索引有效。选择优先级更高的孩子如果右孩子存在(child1 n)并且右孩子的优先级高于左孩子_comp(_con[child], _con[child 1])为真则将child更新为右孩子索引。这一步确保了总是与优先级更高的那个孩子进行比较和可能的交换。比较与交换逻辑和向上调整类似如果父节点优先级低于选中的孩子则交换。更新索引交换后原父节点下沉到了child位置所以将parent更新为child并重新计算其左孩子索引继续循环。5.3 对外接口的实现有了核心的调整函数其他接口的实现就水到渠成了。// 构造函数用迭代器范围构造并建堆 template class T, class Container, class Compare template class InputIterator my::priority_queueT, Container, Compare::priority_queue(InputIterator first, InputIterator last) : _con(first, last) { // 从最后一个非叶子节点开始向前逐个进行向下调整构建堆 // 最后一个非叶子节点下标为 (size() - 2) / 2 for (int i (size() - 2) / 2; i 0; --i) { _adjust_down(i); } } template class T, class Container, class Compare bool my::priority_queueT, Container, Compare::empty() const { return _con.empty(); } template class T, class Container, class Compare size_t my::priority_queueT, Container, Compare::size() const { return _con.size(); } template class T, class Container, class Compare const T my::priority_queueT, Container, Compare::top() const { // 调用前最好检查非空这里省略了 return _con.front(); } template class T, class Container, class Compare void my::priority_queueT, Container, Compare::push(const T val) { _con.push_back(val); // 1. 尾插 _adjust_up(size() - 1); // 2. 向上调整最后一个元素 } template class T, class Container, class Compare void my::priority_queueT, Container, Compare::pop() { if (empty()) return; // 处理空队列 std::swap(_con[0], _con[size() - 1]); // 1. 交换堆顶与堆尾 _con.pop_back(); // 2. 删除原堆顶现堆尾 if (!empty()) { _adjust_down(0); // 3. 对新的堆顶进行向下调整 } }实操心得建堆的时间复杂度在接收迭代器范围的构造函数中我们通过从最后一个非叶子节点开始向下调整来建堆。这个方法的时间复杂度是O(n)而不是直觉上的O(n log n)。这是一个经典的算法结论。相比之下如果通过连续pushn个元素来建堆时间复杂度是O(n log n)。因此如果已知所有元素使用范围构造函数效率更高。6. 综合应用与常见问题排查理解了原理和实现我们来看看如何在实际中应用它们以及会遇到哪些坑。6.1 典型应用场景1. 使用deque处理滑动窗口最大值LeetCode 239这是deque的经典应用。我们需要维护一个窗口并快速获取窗口内的最大值。一个高效的解法是使用一个双端队列deque来存储可能成为窗口最大值的元素的索引且队列中的索引对应的值是递减的。vectorint maxSlidingWindow(vectorint nums, int k) { vectorint res; dequeint dq; // 存储的是下标 for (int i 0; i nums.size(); i) { // 1. 维护队列如果队头索引已不在窗口内弹出 if (!dq.empty() dq.front() i - k) { dq.pop_front(); } // 2. 维护队列从队尾开始弹出所有小于当前值的索引它们不可能是最大值了 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } // 3. 当前索引入队 dq.push_back(i); // 4. 当窗口形成后记录结果队头即最大值索引 if (i k - 1) { res.push_back(nums[dq.front()]); } } return res; }这里充分利用了deque在两端pop的O(1)复杂度。2. 使用priority_queue实现Top K问题或任务调度例如从海量数据中找出前K个最大的数。我们可以维护一个大小为K的小顶堆。vectorint topK(vectorint nums, int k) { if (k 0) return {}; // 小顶堆堆顶是当前堆中最小的数即第K大的候选者中最弱的一个 priority_queueint, vectorint, greaterint min_heap; for (int num : nums) { if (min_heap.size() k) { min_heap.push(num); } else if (num min_heap.top()) { // 如果新数比堆顶当前第K大大则替换它 min_heap.pop(); min_heap.push(num); } } // 最后堆中剩下的就是最大的K个数但不一定有序 vectorint res; while (!min_heap.empty()) { res.push_back(min_heap.top()); min_heap.pop(); } // 如果需要从大到小排序需要反转一下 reverse(res.begin(), res.end()); return res; }6.2 常见问题与排查技巧问题1自定义类型放入priority_queue编译报错“无效的模板参数”或“没有匹配的operator”。原因priority_queue默认使用lessT它依赖于operator来比较元素。如果你的自定义类型没有重载operator或者你使用了自定义仿函数但仿函数的operator()不是const成员函数就会出错。解决为你的自定义类型重载operator。或者在声明priority_queue时提供一个正确的自定义仿函数类型并确保其operator()是const的。struct MyType { int id; int priority; // 方法1重载 operator bool operator(const MyType other) const { // 定义你的比较逻辑比如按priority比较 return priority other.priority; // 大顶堆 } }; // 使用默认比较 // priority_queueMyType pq; // 方法2使用自定义仿函数 struct CompareMyTypeById { bool operator()(const MyType a, const MyType b) const { // 注意const return a.id b.id; // 按id小顶堆 } }; priority_queueMyType, vectorMyType, CompareMyTypeById pq;问题2priority_queue里存的是指针但排序结果不符合预期。原因默认的less对指针比较的是地址大小而不是指针所指向对象的值。解决必须提供自定义仿函数来解引用指针并比较。struct PtrCompare { bool operator()(const MyType* a, const MyType* b) const { // 假设MyType有value成员 return a-value b-value; // 大顶堆 } }; priority_queueMyType*, vectorMyType*, PtrCompare pq;问题3在循环中同时使用top()和pop()但有时pop()后程序崩溃。原因可能是在pop()一个空的priority_queue。top()在队列为空时是未定义行为UB而pop()在空队列上也是UB。解决在调用top()或pop()之前务必检查队列是否为空。while (!pq.empty()) { auto val pq.top(); // 安全 pq.pop(); // 安全 // ... 处理val }问题4使用deque的迭代器时程序在某些操作后出现随机错误。原因极有可能是迭代器失效。记住deque的迭代器失效规则在头部或尾部插入/删除通常不会使其他迭代器失效但指向被删除元素的迭代器肯定失效。在中间进行insert或erase会导致所有迭代器失效。解决如果需要在中间频繁插入删除考虑使用list。如果必须用deque并在修改后还需要使用迭代器最安全的做法是重新获取迭代器例如it dq.begin();。问题5自定义仿函数看起来没问题但priority_queue排序结果完全反了。原因混淆了比较逻辑。牢记仿函数Comp(a, b)返回true表示a的优先级低于b。如果你想实现小顶堆值小的优先级高那么当a b时a的优先级低于b所以仿函数应该返回a b即使用greater。排查画一个小例子比如三个数手动模拟一下堆的调整过程检查你的仿函数在每次比较时返回的布尔值是否符合你期望的优先级关系。
