重生之我要搞懂 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 Continervector T class mystack {通过模板参数的灵活配置我们可以在使用时自由选择栈的底层实现。既可以是基于链表的链式栈也可以是基于数组的数组栈。适配器内部封装了一个被适配容器的实例化对象所有对外接口均可通过调用该对象的对应接口来实现。需要特别注意的是栈和队列作为容器适配器而非独立容器不提供迭代器。这是因为迭代器的遍历特性会破坏栈的「后进先出」LIFO和队列的「先进先出」FIFO语义若支持迭代器则无法保证其核心特性的完整性。template class T, class Continervector 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 ContainervectorT class mystack{ public: void push(const T x){_con.push_front(x);} private: Container _con; }; int main() { mystackint mst; return 0; }如上例所示我们自定义的mystack内部组合了一个默认vector类型的对象_conpush接口中调用了vector并不存在的push_front接口。但由于main函数中仅构造了mst对象并未调用push接口因此编译时不会报错。五、deque 的底层逻辑5.1 deque 的定义与容器关联前面我们自定义的stack采用了vector作为默认底层容器但STL标准库中stack和queue的默认适配容器其实是deque。要理解这一设计选择我们首先需要明确deque是什么。dequedouble-ended queue双端队列是STL中的核心序列容器定义于deque头文件中。顾名思义它支持在容器的头部和尾部进行高效的元素插入与删除操作兼具 vector 和 list 的部分特性。deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示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数组与中控数组的空间状态分为三种情况buffer空间充足且中控数组空间充足插入第二个、第三个…… 数据时直接在当前buffer数组中从左到右依次插入直至当前 buffer 数组被填满。buffer空间不足且中控数组空间充足当 cur last当前 buffer 已满时开辟一块新的 buffer 数组将新buffer的指针插入到中控数组中原 buffer 指针的后一个位置随后调整迭代器指针将node指针向后移动一格指向新buffer的指针位置first、last 分别指向新 buffer 的起始和末尾位置cur指向新buffer中待插入数据的起始位置再继续插入数据。buffer空间不足且中控数组空间不足若继续插入数据直至中控数组空间也不足则触发中控数组的扩容开辟一块更大的中控数组通常采用二倍扩容策略将原中控数组中的指针数据拷贝至新数组随后调整迭代器的各指针位置以适配新的中控数组。相比 vector 的扩容需拷贝所有元素数据deque 仅需拷贝中控数组的指针扩容效率显著更高。5.3.3 头部插入头部插入的逻辑设计巧妙看似出乎意料实则贴合其双端扩展的核心定位无论初始的第一个 buffer数组是否已满在进行第一个头部数据插入时都需要新建一个buffer数组。具体操作流程为先开辟新的 buffer 数组将其指针存储在中控数组中原第一个 buffer 指针的前一个位置随后调整迭代器的各指针node 指针向前移动一格指向新 buffer 的指针位置first、last 分别指向新 buffer 的起始和末尾位置cur 指针则定位到新 buffer 的末尾位置最后从后往前在新 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有效数据的起始迭代器其内部四个指针的指向规则如下first指针指向当前有效数据最左侧buffer数组的起始位置last指针指向当前有效数据最左侧buffer数组的结束位置node指针指向该最左侧buffer数组的指针在中控数组中的存储位置cur指针指向当前迭代器在该buffer数组中具体的数据位置头插数据时会随插入位置动态调整。5.4.3 迭代器前置 的实现逻辑迭代器前置的核心流程为先将cur指针向后移动一位指向当前buffer数组的下一个位置若cur移动后到达当前buffer的末尾即 cur last则需切换到下一个buffer数组。此时将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的 “特性合体”在性能上形成了独特的权衡高效的头插尾删deque的头插、尾插操作均为 amortized O (1) 复杂度性能显著优于 vector头插需移动大量元素O (n)且因缓存利用率高于list实际表现更优。支持下标随机访问但性能略逊于 vectordeque 支持 O (1) 的下标随机访问但需通过 “中控数组索引 buffer 内偏移” 的两级指针计算定位数据计算开销大于 vector 的连续空间直接访问因此随机访问性能稍弱。中间插入删除效率低为 O (n) 复杂度在deque中间位置插入或删除元素时需移动大量数据以保证空间逻辑连续效率较低。关于第三点的设计妥协若避免全量数据挪动改为对当前buffer单独扩容或缩容会导致各 buffer大小不一致此时operator[]无法通过简单的 N/szN 为目标索引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头文件中。优先级队列包含三个核心模板参数T 为容器适配器中存储的数据类型Container 为适配器所适配的底层容器Compare 为比较器用于定义优先级规则并指导建堆过程。其默认底层容器选择vector而非deque原因在于堆的底层逻辑依赖数组结构堆的建堆如向上调整、向下调整及访问操作如通过 *21 定位子节点会频繁调用 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库提供的标准仿函数也可以使用我们自主实现的仿函数。通过传入不同的比较器就能动态切换建堆的逻辑小堆/大堆无需修改算法本身的代码。templateclass T, class Continer vectorT,class compare greaterT class priority_queue {在向上调整算法的比较逻辑中通过_cmp(_con[futher], _con[child])的方式调用仿函数。此时若传入的是std::less比较器则执行 “小于” 比较若传入的是std::greater比较器则执行 “大于” 比较。通过这种设计可在类外部根据需求动态切换比较逻辑无需修改算法核心代码。需要注意的是在优先级队列的默认实现中使用std::less作为比较器时会构建大堆优先级高的元素在前传入std::greater时则构建小堆优先级低的元素在前。顺带一提仿函数通常被设计为空类即类中无成员变量。根据C标准空类的大小默认不为 0而是1字节。这是为了保证该类的不同对象在内存中拥有不同的地址确保对象的唯一性。6.1.2仿函数的应用我们可以在排序里面使用仿函数如下只需要和上面一样设置一个比较参数然后用这个比较参数传递仿函数控制排序的升和降。templateclass 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() { Lessint LessFunc; Greaterint 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, Lessint()); BubbleSort(a, 8, Greaterint());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; // 明确按价格比较 } };将这个仿函数传入优先级队列就能实现按商品价格降序建堆的需求。简言之自定义仿函数的核心价值是让比较逻辑完全贴合业务需求突破内置比较器仅支持 “默认值比较” 的局限。