重生之我要搞懂 C++ 容器适配器：stack/queue/deque/priority_queue 一网打尽

目录

一、什么是适配器

二、什么是stack和queue

三、基于底层容器封装实现适配器

3.1 为什么未包含 头文件仍可将其作为模板默认参数？

3.2 为什么 stack.h 头文件在 vector 头文件之上仍能找到定义？

四、模板按需实例化

五、deque 的底层逻辑

5.1 deque 的定义与容器关联

5.2 deque 的底层组件

5.3deque是怎么插入和获取数据的

5.3.1 插入第一个数据

5.3.2 尾部插入

5.3.3 头部插入

5.3.4 获取数据

5.4deque是如何借助其迭代器维护其假想连续的结构

5.4.1 总体结构

5.4.2 start 迭代器的指针指向安排（last 迭代器同理）

5.4.3 迭代器前置 ++ 的实现逻辑

5.5 deque与vector、list的优劣势总结

5.5.1 与 vector 对比

5.5.2 与 list 对比

六，优先级队列

6.1什么是优先级队列

6.1.1 仿函数

6.1.2仿函数的应用

6.2 何时需要自定义仿函数

6.2.1 指针类型的比较：需比较指针指向的数据而非地址

6.2.2 类类型的比较：需比较类的特定成员变量

经过前面vector和list两个核心容器的完整拆解，本篇我们将正式进入stack与queue的系统讲解。文章会由浅入深，不仅覆盖两个容器的核心用法，还会深入引入底层依赖的deque设计思想，干货满满。

前排预告：与前两个容器重复的通用接口本文不再赘述，我们将全部篇幅聚焦于stack和queue独有的特性与底层实现。

一、什么是适配器

适配器是一种经典的设计模式（设计模式是一套被反复验证、广为知晓、经过分类总结的代码设计经验，我们之前深入讲解的迭代器便是迭代器模式的典型应用）。该模式的核心作用是将一个类的现有接口，转换为客户期望的另一种接口形式，从而让原本因接口不兼容而无法协作的类能够协同工作。

二、什么是stack和queue

与vector、string及list不同，stack（栈）与queue（队列）并非独立容器，而是容器适配器。它们不直接管理元素的底层存储，而是对某一现有容器进行接口封装，通过限制与重塑容器的访问方式，赋予其特定的抽象语义（如栈的 LIFO「后进先出」、队列的 FIFO「先进先出」）。

关于栈与队列的基础特性及通用接口用法，这里不再赘述，我们直接进入核心实现的干货讲解。

三、基于底层容器封装实现适配器

以stack为例，它包含两个模板参数：第一个是元素的存储类型，第二个则是作为适配器底层支撑的容器类型。通过对传入的底层container进行接口适配与转换，即可实现stack的核心功能。

因此，stack的构造函数与析构函数可直接由编译器自动生成，通过调用底层container的原生构造与析构函数完成资源管理，无需手动实现。其余核心接口则均可通过封装底层container的对应接口来实现。

namespace work { template <class T, class Continer=vector <T> > class mystack {

通过模板参数的灵活配置，我们可以在使用时自由选择栈的底层实现。既可以是基于链表的链式栈，也可以是基于数组的数组栈。适配器内部封装了一个被适配容器的实例化对象，所有对外接口均可通过调用该对象的对应接口来实现。

需要特别注意的是，栈和队列作为容器适配器而非独立容器，不提供迭代器。这是因为迭代器的遍历特性会破坏栈的「后进先出」（LIFO）和队列的「先进先出」（FIFO）语义，若支持迭代器则无法保证其核心特性的完整性。

template <class T, class Continer=vector <T> > class mystack{ public: void push(const T& x){_con.push_back(x);} private: Continer _con; };

3.1 为什么未包含 <vector> 头文件仍可将其作为模板默认参数？

这是实现容器适配器时一个典型的文件包含疑问：在stack.h头文件中，我们并未显式包含<vector>头文件，却能将vector作为模板参数的默认值使用？

核心原因在于头文件的编译机制：stack.h本身不会独立参与编译，而是在编译前的预处理阶段，在包含它的.cpp文件中进行文本展开。

只要使用stack适配器的.cpp文件，在包含stack.h之前先包含了<vector>头文件，那么当stack.在.cpp中展开后，就能完整访问vector的定义，从而正常使用其作为模板默认参数。模板本身是在实例化时才进行完整编译的。

3.2 为什么 stack.h 头文件在 vector 头文件之上仍能找到定义？

核心原因在于C++模板的延迟实例化特性：模板在未被实例化时不会进行完整编译，仅做基本的语法检查。

我们在.cpp文件中先包含stack.h再包含<vector>，只是完成了头文件的文本展开；

当在main函数中真正构造stack的实例化对象时，才会触发模板的完整编译，此时从实例化点向上查找，自然能找到完整的vector定义。

但需注意：若在stack.h中定义一个非模板函数并直接调用vector的接口，编译时会立即报错找不到vector定义，因为非模板函数不依赖实例化，会在头文件展开后直接参与编译。

四、模板按需实例化

模板按需实例化的核心特性是：模板内部的各类接口，只有在被调用时才会进行实例化（例如构造对象时实例化构造函数，插入数据时实例化 push 接口）。

这一特性导致，若未调用模板内的某些接口，编译器仅会对其进行简单的语法扫描。对于接口内部的细节逻辑错误，编译器无法提前察觉；

而对于明显的语法错误（如遗漏分号），则取决于编译器版本，较老的编译器（如 VS2013）可能无法检测，较新的编译器（如 VS2022）则会直接报错。

由此便会出现 “未调用接口时不报错，调用后才报错” 的情况，以下例子：

template <class T, class Container=vector<T>> class mystack{ public: void push(const T& x){_con.push_front(x);} private: Container _con; }; int main() { mystack<int> mst; return 0; }

如上例所示，我们自定义的mystack内部组合了一个默认vector类型的对象_con，push接口中调用了vector并不存在的push_front接口。但由于main函数中仅构造了mst对象，并未调用push接口，因此编译时不会报错。

五、deque 的底层逻辑

5.1 deque 的定义与容器关联

前面我们自定义的stack采用了vector作为默认底层容器，但STL标准库中stack和queue的默认适配容器其实是deque。要理解这一设计选择，我们首先需要明确deque是什么。

deque（double-ended queue，双端队列）是STL中的核心序列容器，定义于<deque>头文件中。顾名思义，它支持在容器的头部和尾部进行高效的元素插入与删除操作，兼具 vector 和 list 的部分特性。

deque堪称vector与list的 “特性合体”，但它并非简单的功能叠加，而是在两者基础上形成了独特的优劣势。

在深入剖析deque的底层逻辑之前，我们先系统总结vector与list的核心特性，deque的优缺点将在后续底层原理讲解后展开。

vector 核心特性优点：

1. 尾插尾删效率优异，且支持高效的下标随机访问，时间复杂度为 O (1)。

2. 物理空间连续存储，CPU 高速缓存命中率高，能充分利用缓存局部性原理提升性能。

缺点：

1. 空间需动态扩容，扩容过程涉及旧空间数据拷贝、新空间申请与释放，存在一定的时间与空间（空间预留导致的浪费）代价。

2. 头部或中间位置插入、删除元素效率低，需移动大量元素，时间复杂度为 O (n)。

list 核心特性优点：

1. 按需申请与释放空间，无需预先扩容，避免了空间浪费与扩容开销。

2. 任意位置插入、删除元素效率极高，仅需调整指针指向，时间复杂度为 O (1)。

缺点：

1. 不支持下标随机访问，遍历需依赖迭代器，时间复杂度为 O (n)。

2. 节点物理空间不连续，CPU 高速缓存利用率低，无法有效利用缓存局部性。

5.2 deque 的底层组件

deque 的底层结构由三大核心组件构成：缓冲区数组（buffer）、中控数组（map）以及迭代器。如下图所示，中控数组是一个存储指针的数组，每个指针指向一块用于存储实际数据的缓冲区数组；而deque的迭代器则由四个关键指针组成，用于维护其在底层结构中的位置与遍历逻辑。

5.3deque是怎么插入和获取数据的

5.3.1 插入第一个数据

插入第一个数据时，deque会先创建一个指针类型的中控数组（STL 源码中常称为map），随后创建第一个缓冲区（buffer）数组，并将该 buffer 的指针存储在中控数组的中间位置（而非最左侧）这一设计是为了后续支持头部和尾部的双向高效扩展。

接着，在buffer数组中从左到右插入第一个数据。

此时，deque迭代器的四个指针会按如下规则指向：

node指针指向中控数组的中间位置（即第一个buffer指针的存储位置）；

first指针指向当前buffer数组的起始位置；

last指针指向当前buffer数组的末尾位置；

cur指针则指向第一个被插入数据的具体位置。

5.3.2 尾部插入

尾部插入根据buffer数组与中控数组的空间状态，分为三种情况：

1. buffer空间充足且中控数组空间充足插入第二个、第三个…… 数据时，直接在当前buffer数组中从左到右依次插入，直至当前 buffer 数组被填满。
2. buffer空间不足且中控数组空间充足当 cur == last（当前 buffer 已满）时，开辟一块新的 buffer 数组，将新buffer的指针插入到中控数组中原 buffer 指针的后一个位置；随后调整迭代器指针：将node指针向后移动一格指向新buffer的指针位置，first、last 分别指向新 buffer 的起始和末尾位置，cur指向新buffer中待插入数据的起始位置，再继续插入数据。
3. buffer空间不足且中控数组空间不足若继续插入数据直至中控数组空间也不足，则触发中控数组的扩容：开辟一块更大的中控数组（通常采用二倍扩容策略），将原中控数组中的指针数据拷贝至新数组；随后调整迭代器的各指针位置以适配新的中控数组。相比 vector 的扩容（需拷贝所有元素数据），deque 仅需拷贝中控数组的指针，扩容效率显著更高。

5.3.3 头部插入

头部插入的逻辑设计巧妙，看似出乎意料实则贴合其双端扩展的核心定位：无论初始的第一个 buffer数组是否已满，在进行第一个头部数据插入时，都需要新建一个buffer数组。

具体操作流程为：

1. 先开辟新的 buffer 数组，将其指针存储在中控数组中原第一个 buffer 指针的前一个位置；
2. 随后调整迭代器的各指针：node 指针向前移动一格指向新 buffer 的指针位置，first、last 分别指向新 buffer 的起始和末尾位置，cur 指针则定位到新 buffer 的末尾位置；
3. 最后从后往前在新 buffer 中插入第一个头部数据。

5.3.4 获取数据

deque的数据访问依赖于对中控数组与缓冲区数组的两级指针定位。我们先假设有一个指针指向中控数组（STL 源码中常称为 map）中有效数据的起始位置，该指针解引用后得到的是对应位置存储的缓冲区指针（为便于表述，记为 buf 指针），这里的逻辑可简单理解为：整型数组的某位置指针解引用得到整型值，而指针数组的某位置指针解引用得到的仍是指针。

获取buf指针后，便锁定了目标数据所在的缓冲区数组，后续可通过指针运算与解引用操作访问该缓冲区内的具体数据。

具体定位逻辑分为两步：假设要访问第 N 个数据，每个缓冲区的固定大小为sz。通过 N / sz 可确定目标缓冲区在中控数组中的索引位置，通过 N % sz 则可确定数据在该缓冲区内的偏移位置。由此可推导出数据访问的核心公式：

5.4deque是如何借助其迭代器维护其假想连续的结构

5.4.1 总体结构

deque的底层由两个迭代器构成，如下图：

5.4.2 start 迭代器的指针指向安排（last 迭代器同理）

start 迭代器作为deque有效数据的起始迭代器，其内部四个指针的指向规则如下：

1. first指针：指向当前有效数据最左侧buffer数组的起始位置；
2. last指针：指向当前有效数据最左侧buffer数组的结束位置；
3. node指针：指向该最左侧buffer数组的指针在中控数组中的存储位置；
4. cur指针：指向当前迭代器在该buffer数组中具体的数据位置（头插数据时会随插入位置动态调整）。

5.4.3 迭代器前置 ++ 的实现逻辑

迭代器前置++的核心流程为：

1. 先将cur指针向后移动一位，指向当前buffer数组的下一个位置；
2. 若cur移动后到达当前buffer的末尾（即 cur == last），则需切换到下一个buffer数组。
3. 此时将node指针向后移动一位，指向中控数组中下一个buffer的指针位置，再将cur指针设置为新buffer数组的起始位置（first）。

核心代码逻辑如下：

self& operator++() { ++cur; if (cur == last) { set_node(node + 1); cur = first; } return *this; } void set_node(map_pointer new_node) { node = new_node; first = *new_node; last = first + difference_type(buffer_size()); }

5.5 deque与vector、list的优劣势总结

deque作为vector与list的 “特性合体”，在性能上形成了独特的权衡：

1. 高效的头插尾删：deque的头插、尾插操作均为 amortized O (1) 复杂度，性能显著优于 vector（头插需移动大量元素，O (n)），且因缓存利用率高于list，实际表现更优。
2. 支持下标随机访问，但性能略逊于 vector：deque 支持 O (1) 的下标随机访问，但需通过 “中控数组索引 + buffer 内偏移” 的两级指针计算定位数据，计算开销大于 vector 的连续空间直接访问，因此随机访问性能稍弱。
3. 中间插入删除效率低，为 O (n) 复杂度：在deque中间位置插入或删除元素时，需移动大量数据以保证空间逻辑连续，效率较低。

关于第三点的设计妥协：若避免全量数据挪动，改为对当前buffer单独扩容或缩容，会导致各 buffer大小不一致，此时operator[]无法通过简单的 N/sz（N 为目标索引，sz为固定buffer 大小）快速定位目标buffer，会进一步拉低随机访问的效率。

因此，STL 标准库选择以 “挪动数据” 为妥协，优先保证 operator[] 的高效性。

self& operator+=(difference_type n) { difference_type offset = n + (cur - first); if (offset >= 0 && offset < difference_type(buffer_size())) cur += n; else { difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size()) : -difference_type((-offset - 1) / buffer_size()) - 1; set_node(node + node_offset); cur = first + (offset - node_offset * difference_type(buffer_size())); } return *this; }

5.5.1 与 vector 对比

• 头部插入/删除效率更高：vector在头部插入或删除元素时，需整体搬移后续所有元素，时间复杂度为 O (n)；而deque凭借其 “分段连续空间” 的底层结构（由缓冲区 buffer 与中控数组 map 构成），头部插入/删除仅需调整中控数组的块指针或分配新的缓冲区，无需整体搬移元素。

• 扩容代价显著更低：vector扩容时需重新申请更大的连续内存，并将所有元素整体搬移至新空间；而deque仅在中控数组（map）空间不足时触发扩容，且扩容时只需拷贝中控数组的指针，无需搬移已存储在缓冲区中的实际数据。

因此，在“频繁进行头部或尾部插入/删除”的场景下，deque的理论时间复杂度与实际性能均优于 vector。

5.5.2 与 list 对比

• 空间利用率更高：list作为双向链表，每个节点都需额外存储前驱、后继指针，存在显著的元数据开销；而deque的缓冲区（buffer）内部采用连续存储，无需额外的节点指针，仅需中控数组（map）的少量指针开销，空间利用率明显优于 list。

• 缓存局部性更好：list的节点在物理空间上完全离散存储，无法有效利用 CPU 缓存的局部性原理，缓存命中率极低；而deque的缓冲区内部是连续空间，至少能保证块内数据的高效缓存访问，缓存友好性显著优于 list。

综上，deque既结合了vector与list的核心优势，又规避了两者的最大缺陷（无需高效中间插入删除，也不依赖极致的随机访问性能），因此是stack和queue理想的默认底层容器。

六，优先级队列

6.1什么是优先级队列

STL中的优先级队列（priority_queue）底层是基于堆数据结构实现的。之所以命名为“优先级队列” 而非直接叫“堆”，主要是出于易用性的考量：并非所有学习C++ 的开发者都预先系统学习过数据结构，而 “队列” 的概念更易理解，普通队列遵循 “先进先出”（FIFO）的出队规则，优先级队列则在此基础上，遵循“按优先级高低出队”的规则，这种命名方式更贴合其使用语义。

此外，优先级队列没有单独的头文件，与queue一同定义于<queue>头文件中。

优先级队列包含三个核心模板参数：

1. T 为容器适配器中存储的数据类型；
2. Container 为适配器所适配的底层容器；
3. Compare 为比较器，用于定义优先级规则并指导建堆过程。

其默认底层容器选择vector而非deque，原因在于堆的底层逻辑依赖数组结构：堆的建堆（如向上调整、向下调整）及访问操作（如通过 *2+1 定位子节点）会频繁调用 operator[] 进行随机访问。而deque的operator[] 需通过 “中控数组索引 + 缓冲区偏移” 的两级指针计算实现，效率约为vector（连续空间直接访问）的一半。vector是优先级队列更合适的默认底层容器。

6.1.1 仿函数

在讲解优先级队列的比较器之前，我们需要先补充一个核心知识点：仿函数（Functor）。

仿函数本质上是一个类或结构体，其核心特征是重载了函数调用运算符 operator()。

之所以被称为 “仿函数”，是因为它在使用时的语法形式与普通函数完全一致。通过 “对象名 + 参数列表” 的方式调用，例如 my_functor(x)，就像在调用一个名为my_functor的函数。这里的operator()中的括号，与普通函数（如 void func()）参数列表的括号作用完全相同，用于接收调用时传入的参数。

template <class T> class greater{ public: bool operator()(T x,T y){return x > y;} }; template <class T> class less{ public: bool operator()(T x, T y){return x < y;} };

如上，我们写了两个仿函数，一个是greater比较大仿函数。一个是less比较小仿函数。还不理解我们使用一下就明白了：

void AdjustUp(size_t child ){ int futher = (child - 1) / 2; while (futher >= 0){ //if(_con[futher] > _con[child]) if(_cmp(_con[futher] , _con[child])){ std::swap(_con[futher], _con[child]); child = futher; futher = (child - 1) / 2; } else break; } }

如上，这是一个堆的向上调整算法。代码中注释掉的 _con[futher] > _con[child] 是原始的大小比较逻辑，若父节点大于子节点则交换，这种逻辑用于构建小堆；反之，若父节点小于子节点则交换，则用于构建大堆。可见，建小堆还是大堆，核心取决于比较逻辑的方向。

我们可以想象一个实际场景：某电商平台的购物筛选系统，底层基于堆排序实现，若需要将商品价格从“升序排序”改为“降序排序”，难道要手动修改代码中的比较符号吗？这显然不够灵活。因此，核心问题是：如何在不修改核心算法代码的前提下，自由切换比较逻辑的方向？

仿函数的出现完美解决了这一问题。我们只需在堆类的模板参数中增加一个Compare参数，专门用于传递比较器，既可以使用STL库提供的标准仿函数，也可以使用我们自主实现的仿函数。通过传入不同的比较器，就能动态切换建堆的逻辑（小堆/大堆），无需修改算法本身的代码。

template<class T, class Continer = vector<T>,class compare = greater<T>> class priority_queue {

在向上调整算法的比较逻辑中，通过_cmp(_con[futher], _con[child])的方式调用仿函数。

此时，若传入的是std::less比较器，则执行 “小于” 比较；若传入的是std::greater比较器，则执行 “大于” 比较。

通过这种设计，可在类外部根据需求动态切换比较逻辑，无需修改算法核心代码。

需要注意的是，在优先级队列的默认实现中，使用std::less作为比较器时会构建大堆（优先级高的元素在前），传入std::greater时则构建小堆（优先级低的元素在前）。

顺带一提，仿函数通常被设计为空类（即类中无成员变量）。根据C++标准，空类的大小默认不为 0，而是1字节。这是为了保证该类的不同对象在内存中拥有不同的地址，确保对象的唯一性。

6.1.2仿函数的应用

我们可以在排序里面使用仿函数，如下，只需要和上面一样设置一个比较参数，然后用这个比较参数传递仿函数控制排序的升和降。

template<class Compare> void BubbleSort(int* a, int n, Compare com){ for (int j = 0; j < n; j++){ int flag = 0; for (int i = 1; i < n - j; i++){ // if (a[i] < a[i - 1]) if (com(a[i], a[i - 1])){ swap(a[i - 1], a[i]); flag = 1; } } } } int a[] = { 9,1,2,5,7,4,6,3 }; int main() { Less<int> LessFunc; Greater<int> GreaterFunc; int a[] = { 9,1,2,5,7,4,6,3 }; BubbleSort(a, 8, LessFunc); BubbleSort(a, 8, GreaterFunc); return 0; }

也可以用匿名对象。less和greater仿函数不需要自己写，库里面有，主要在functio头文件里面，但是也有可能被间接包含。但是有些时候需要我们自己写。

BubbleSort(a, 8, Less<int>()); BubbleSort(a, 8, Greater<int>());

6.2 何时需要自定义仿函数

当 STL内置的std::less和 std::greater无法满足业务的比较逻辑时，就需要我们自己编写仿函数。

常见场景主要有以下两类：

6.2.1 指针类型的比较：需比较指针指向的数据而非地址

若容器中存储的是指针类型，内置比较器默认会比较指针的数值（即内存地址），而非指针指向的实际数据。但内存地址在每次程序运行时可能不同，这会导致比较结果的不确定性，完全不符合我们的预期。

典型例子：假设优先级队列中存储的是int*指针，我们希望按指针指向的int值大小建堆，而非按地址大小。此时内置的std::less会直接比较两个指针的地址，无法满足需求，因此需要自定义仿函数：

struct LessIntPtr { bool operator()(int* p1, int* p2) { return *p1 < *p2; // 解引用指针，比较实际数据 } };

通过这个仿函数，就能在优先级队列中按指针指向的int值大小进行比较。

6.2.2 类类型的比较：需比较类的特定成员变量

若容器中存储的是自定义类类型，内置比较器无法知道我们想按哪个规则比较（比如按类的某个成员变量排序），此时也需要自定义仿函数，明确指定比较逻辑。

典型例子：假设有一个Goods类，包含price（价格）和sales（销量）两个成员变量。

我们希望在优先级队列中按“价格从高到低”排序，而非按整个Goods对象的默认规则（若未重载 < 则根本无法比较）。此时可自定义仿函数：

class Goods { public: double price; int sales; Goods(double p, int s) : price(p), sales(s) {} }; struct GreaterPrice { bool operator()(const Goods& g1, const Goods& g2) { return g1.price > g2.price; // 明确按价格比较 } };

将这个仿函数传入优先级队列，就能实现按商品价格降序建堆的需求。

简言之，自定义仿函数的核心价值是让比较逻辑完全贴合业务需求，突破内置比较器仅支持 “默认值比较” 的局限。