一.stack 的介绍和使用1.stack 的介绍https://cplusplus.com/reference/stack/stack/?kwstack#google_vignette1.stack是一种容器适配器专门设计用来处理LIFO后进先出的场景。在这种数据结构中元素的插入和删除都只能在容器的一端进行。2.stack 本身并不管理数据而是作为容器适配器存在的——它把某个底层容器包起来只暴露出一组特定的接口从尾部栈顶压入数据、从尾部弹出数据。这组受限的接口正好满足了栈“后进先出”的行为特征。3.stack 的底层容器不是固定的可以是任何符合要求的容器类。这个容器至少需要支持以下四个操作empty()判断是否为空back()获取尾部元素即栈顶push_back()在尾部插入元素入栈pop_back()从尾部删除元素出栈4.常见的容器如 vector、deque、list 都满足这些要求。如果你不指定底层容器stack 默认会使用 deque。2.stack 的使用在STL的stack 是没有迭代器的因为如果有了迭代器就可以随意访问元素了这样就无法保证后进先出的性质了。3.stack 的模拟实现从栈的接口中可以看出栈实际是一种特殊的vector因此使用vector完全可以模拟实现stack。#pragma once #include vector // vector 也可以作为底层容器 #include deque // deque 是默认底层容器 #include iostream using namespace std; namespace hjq { // stack 容器适配器 // T栈中存储的数据类型 // Container底层容器类型默认为 deque把 Container 的尾部当作栈顶 templateclass T, class Container dequeT class stack { public: // 构造函数默认即可底层容器会自己初始化 stack() {} // 容量相关 // 判断栈是否为空 bool empty() const { return _con.empty(); } // 返回栈中元素个数 size_t size() const { return _con.size(); } // 元素访问 // 返回栈顶元素可修改 T top() { return _con.back(); // 尾部就是栈顶 } // 返回栈顶元素只读 const T top() const { return _con.back(); } // 修改操作 // 入栈在尾部插入元素 void push(const T x) { _con.push_back(x); // 尾部插入 → 入栈 } // 出栈删除尾部元素 void pop() { _con.pop_back(); // 尾部删除 → 出栈 } // 交换两个栈的内容C11 void swap(stackT, Container st) { std::swap(_con, st._con); } private: Container _con; // 底层容器所有操作都转发给它 }; void test() { // 可以用 vector 做底层容器 // stackint, vectorint st; // 可以用 list 做底层容器 // stackint, listint st; // 默认用 deque 做底层容器 stackint st; st.push(1); st.push(2); st.push(3); // 遍历栈后进先出 while (!st.empty()) { cout st.top() ; // 输出栈顶元素 st.pop(); // 弹出栈顶 } cout endl; } } int main() { hjq::test(); return 0; }在这里的代码里不需要写构造函数因为在默认构造函数的初始化列表阶段自定义类型成员 _con 会自动调用它的默认构造函数。二.queue 的介绍和使用1. queue的介绍http://www.cplusplus.com/reference/queue/queue/1.队列queue 是一种容器适配器专门用在 FIFO先进先出 的场景中。数据从容器的一端进入从另一端出去就像排队一样——先来的先服务。2.队列本身不管理数据而是作为容器适配器存在的——它把某个底层容器包起来只暴露一组特定的接口从队尾入队、从队头出队。这组受限的接口正好满足了队列“先进先出”的行为特征。3.队列的底层容器不是固定的可以是任何符合要求的容器。这个容器至少需要支持以下六个操作empty()判断队列是否为空size()返回队列中元素的个数front()获取队头元素的引用back()获取队尾元素的引用push_back()在队尾插入元素入队pop_front()在队头删除元素出队4. 常见的容器如 deque 和 list 都满足这些要求。如果你不指定底层容器queue 默认会使用 dequ2.queue 的使用queue 是没有迭代器的因为有了迭代器就可以随意访问元素了就无法保证先进先出的性质了。3.queue的模拟实现因为queue的接口中存在头删和尾插因此使用vector来封装效率太低故可以借助list来模拟实现queue具体如下#pragma once #include deque // deque 是默认底层容器 #include iostream using namespace std; namespace hjq { // queue 容器适配器 // T队列中存储的数据类型 // Container底层容器类型默认为 deque // 特点尾部当作队尾入队头部当作队头出队 templateclass T, class Container dequeT class queue { public: // 构造函数默认即可底层容器会自己初始化 queue() {} // 容量相关 // 判断队列是否为空 bool empty() const { return _con.empty(); } // 返回队列中元素个数 size_t size() const { return _con.size(); } // 元素访问 // 返回队头元素可修改 T front() { return _con.front(); // 头部就是队头 } // 返回队尾元素可修改 T back() { return _con.back(); // 尾部就是队尾 } // 返回队头元素只读 const T front() const { return _con.front(); } // 返回队尾元素只读 const T back() const { return _con.back(); } //修改操作 // 入队在尾部插入元素 void push(const T val) { _con.push_back(val); // 尾部插入 -- 入队 } // 出队在头部删除元素 void pop() { _con.pop_front(); // 头部删除 -- 出队 } private: Container _con; // 底层容器所有操作都转发给它 }; void test() { // 可以用 list 做底层容器 // queueint, listint q; // 默认用 deque 做底层容器 queueint q; q.push(1); q.push(2); q.push(3); // 遍历队列先进先出 while (!q.empty()) { cout q.front() ; // 输出队头元素 q.pop(); // 弹出队头 } cout endl; } } int main() { hjq::test(); return 0; }跟stack一样不需要写构造函数因为在默认构造函数的初始化列表阶段自定义类型成员 _con 会自动调用它的默认构造函数。三. priority_queue的介绍和使用1.priority_queue的介绍http://www.cplusplus.com/reference/queue/priority_queue/1.优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素5. 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。2.priority_queue的使用优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意默认情况下priority_queue是大堆。priority_queue 中的元素按权值大小排列只有堆顶元素权值最高才能被访问或取出。它不提供遍历功能所以也没有迭代器。【注意】1. 默认情况下priority_queue是大堆。#include vector #include queue #include functional // greater算法的头文件 void TestPriorityQueue() { // 默认情况下创建的是大堆其底层按照小于符号()比较 vectorint v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5}; priority_queueint q1; for (auto e : v) { q1.push(e); } cout q1.top() endl; // 如果要创建小堆将第三个模板参数换成greater比较方式即可 priority_queueint, vectorint, greaterint q2(v.begin(), v.end()); cout q2.top() endl; }2. 如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供 或者 的重载。class Date { public: Date(int year 2026, int month 8, int day 27) : _year(year) , _month(month) , _day(day) {} bool operator(const Date d) const // 运算符重载 { return (_year d._year) || (_year d._year _month d._month) || (_year d._year _month d._month _day d._day); } bool operator(const Date d) const // 运算符重载 { return (_year d._year) || (_year d._year _month d._month) || (_year d._year _month d._month _day d._day); } friend ostream operator(ostream _cout, const Date d) { _cout d._year - d._month - d._day; return _cout; } friend struct DateLess; private: int _year; int _month; int _day; }; void test_priority_queue1() { // 大堆需要用户在自定义类型中提供 的重载 priority_queueDate q1; q1.push(Date(2026, 8, 27)); q1.push(Date(2026, 8, 26)); q1.push(Date(2026, 8, 28)); cout q1.top() endl; // 输出2026-8-28最大日期 // 小堆需要用户在自定义类型中提供 的重载 priority_queueDate, vectorDate, greaterDate q2; q2.push(Date(2026, 8, 27)); q2.push(Date(2026, 8, 26)); q2.push(Date(2026, 8, 28)); cout q2.top() endl; // 输出2026-8-26最小日期 } // 自定义仿函数按小于比较日期 struct DateLess { bool operator()(const Date d1, const Date d2) { return (d1._year d2._year) || (d1._year d2._year d1._month d2._month) || (d1._year d2._year d1._month d2._month d1._day d2._day); } }; void test_priority_queue2() { // 大堆第3个模板参数传自定义仿函数 DateLess priority_queueDate, vectorDate, DateLess q1; q1.push(Date(2026, 8, 27)); q1.push(Date(2026, 8, 26)); q1.push(Date(2026, 8, 28)); cout q1.top() endl; // 输出2026-8-28最大日期 }3.priority_queue的模拟实现通过对priority_queue的底层结构就是堆因此此处只需对对进行通用的封装即可。#pragma once #include iostream #include vector #include functional using namespace std; // priority_queue 本质上就是堆 // 底层默认用 vector 存数据通过向上/向下调整维护堆结构 namespace hjq { //仿函数 less用于建大堆 // 判断 left 是否小于 right templateclass T struct less { bool operator()(const T left, const T right) { return left right; } }; // 仿函数 greater用于建小堆 // 判断 left 是否大于 right templateclass T struct greater { bool operator()(const T left, const T right) { return left right; } }; // priority_queue 类模板 // T存储的数据类型 // Container底层容器默认 vector // Compare比较方式默认 less建大堆 templateclass T, class Container vectorT, class Compare std::lessT class priority_queue { public: // 默认构造 priority_queue() {} //迭代器区间构造 // 用 [first, last) 区间构造堆 template class InputIterator priority_queue(InputIterator first, InputIterator last) { // 1. 先把数据全部插入底层容器 while (first ! last) { _con.push_back(*first); first; } // 2. 建堆从最后一个非叶子节点开始向下调整 // 最后一个非叶子节点 (size - 2) / 2 int child _con.size() - 1; int parent (child - 1) / 2; for (int i parent; i 0; i--) { adjust_down(i); } } // adjust_up向上调整 // 用于 push尾部插入新元素后向上调整恢复堆结构 void adjust_up(size_t child) { Compare com; // 仿函数对象决定是大堆还是小堆 size_t parent (child - 1) / 2; while (child 0) { // 如果父节点不满足堆序要求交换父子 if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); child parent; parent (child - 1) / 2; } else { break; // 满足堆序停止调整 } } } // 插入元素 void push(const T x) { _con.push_back(x); // 尾插 adjust_up(_con.size() - 1); // 从尾部向上调整 } // adjust_down向下调整 // 用于 pop 和建堆从某个节点向下调整恢复堆结构 // 前提左右子树都已经满足堆序 void adjust_down(size_t parent) { Compare com; size_t child parent * 2 1; // 左孩子 while (child _con.size()) { // 1. 选出左右孩子中更符合堆序的那个 if (child 1 _con.size() com(_con[child], _con[child 1])) { child; // 右孩子更符合 } // 2. 父节点与孩子比较不满足堆序就交换 if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); parent child; child parent * 2 1; } else { break; // 满足堆序 } } // 删除堆顶 void pop() { std::swap(_con[0], _con[_con.size() - 1]); // 堆顶换到尾部 _con.pop_back(); // 删除尾部 adjust_down(0); // 从根向下调整 } //获取堆顶只读不能返回可修改的引用否则会破坏堆结构 const T top() { return _con[0]; } // 容量相关 bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; // 底层容器 }; } void test_queue_priority() { // 大堆测试 hjq::priority_queueint q1; q1.push(5); q1.push(1); q1.push(4); q1.push(2); q1.push(3); q1.push(6); cout q1.top() endl; q1.pop(); q1.pop(); cout q1.top() endl; // 小堆测试 vectorint v{5, 1, 4, 2, 3, 6}; hjq::priority_queueint, vectorint, hjq::greaterint q2(v.begin(), v.end()); cout q2.top() endl; q2.pop(); q2.pop(); cout q2.top() endl; }4.仿函数1仿函数的定义仿函数又称为函数对象本质上是一个重载了operator()运算符的类对象。它让一个类用起来像函数一样可以直接通过对象调用。语法上仿函数的调用方式和普通函数几乎一样。但实际上调用仿函数时背后执行的是类中重载的operator()函数只不过这种写法看起来和函数调用没区别。// 仿函数函数对象重载了 operator() 的类 // 让对象可以像函数一样被调用 // 定义一个仿函数类 Less用来比较两个整数的大小 struct Less { // 重载 operator()接收两个 int 参数返回比较结果 // 这个类有了这个函数就可以像函数一样调用了 bool operator()(const int x, const int y) { return x y; } }; void test_functor() { // 方式一先创建对象再通过对象调用 Less less; // 实例化一个 Less 对象 cout less(1, 2) endl; // 调用 less.operator()(1, 2) // 输出1 // 方式二用匿名对象直接调用 cout Less()(1, 2) endl; // Less() 构造匿名对象 // 再调用 operator()(1, 2) // 输出1 }https://cplusplus.com/reference/functional/greater/https://cplusplus.com/reference/functional/less/// 仿函数函数对象重载了 operator() 的类对象可以像函数一样使用 //小于比较仿函数 // 功能判断 x 是否小于 y templateclass T struct Less { bool operator()(const T x, const T y) { return x y; // 调用类型自身的 运算符 } }; //大于比较仿函数 // 功能判断 x 是否大于 y templateclass T struct Greater { bool operator()(const T x, const T y) { return x y; // 调用类型自身的 运算符 } }; void test_functor() { // 使用 Less 仿函数 Lessint less; // 实例化对象 cout less(1, 2) endl; // 1 2 → true -- 输出 1 // 使用 Greater 仿函数 Greaterint greater; // 实例化对象 cout greater(1, 2) endl; // 1 2 → false -- 输出 0 }仿函数 less 和 greater 是继承的 binary_function可以看作是对于一类函数的总体声明而且这是函数做不到的。// greater标准库中的大于比较仿函数 // 继承 binary_function 只是为了兼容旧版适配器 // 实际比较逻辑就是x y template class T struct greater : binary_functionT, T, bool { bool operator()(const T x, const T y) const { return x y; }; // less标准库中的小于比较仿函数 // 继承 binary_function 只是为了兼容旧版适配器 // 实际比较逻辑就是x y template class T struct less : binary_functionT, T, bool { bool operator()(const T x, const T y) const { return x y; } };2模板实例化时仿函数的使用类模板和函数模板在使用仿函数时传的东西不一样类模板是显式实例化在 中指定模板参数的实际类型所以传的是类型。比如 priority_queue//第1个模板参数是存储数据的类型 //第2个模板参数是基础容器的类型 //第3个模板参数是仿函数的类型 template class T, class Container vectorT, class Compare lesstypename Container::value_type class priority_queue; void test() { // 建小堆 priority_queueint, vectorint, greaterint pq; // 传仿函数greaterint类型 }函数模板是隐式实例化编译器根据实参推演模板参数所以传的是对象。比如 sort// 第1个模板参数迭代器的类型 // 第2个模板参数是仿函数的类型 template class RandomAccessIterator, class Compare // 函数的第1,2个参数是迭代器对象 // 函数的第3个参数是仿函数类的对象 void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); void test() { vectorint v { 5,3,2,4,1 }; // 排降序() sort (v.begin(), b.end(), greaterint()); // 传仿函数类greaterint的匿名对象 for (const auto x : v) cout x ; cout endl; }给大家小结一下就是类模板用类型造对象函数模板拿对象推类型。给 priority_queue 的是类型 greaterint给 sort 的是对象 greaterint()。四.容器适配器1.什么是适配器适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。2.STL标准库中stack和queue 的底层结构虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用deque比如3.deque的简单介绍(了解)https://cplusplus.com/reference/deque/deque/deque的原理介绍:deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。vector、list、deque 对比vector 是一段连续的物理空间。优点支持随机访问O(1) 就能拿到任意位置的元素。空间利用率高底层是连续空间不容易产生内存碎片。CPU 高速缓存命中率高遍历时性能好。缺点空间不够时需要增容增容代价很大重新分配空间、搬移元素、释放旧空间还有一定的空间浪费。头部和中间插入删除效率低O(N)。list 不是连续空间由一个个独立的节点通过指针链接起来。优点按需申请释放空间不会浪费。任意位置插入删除都是 O(1)不需要搬移数据。缺点不支持随机访问只能顺着指针一个个找。空间利用率低每个节点还要额外存两个指针小节点容易造成内存碎片。CPU 高速缓存命中率低节点在内存中分散分布。deque 介于两者之间并不是真正连续的空间而是由一段段连续的小空间拼接而成底层类似一个动态的二维数组。它的特点支持头插头删vector 做不了的事它行。支持随机访问list 做不了的事它也行。看起来像是融合了 vector 和 list 的优点。deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示当deque需要增容时不需要像vector那样经历重新配置空间、搬移元素、释放旧空间等一系列操作。它只需要新增一个buffer缓冲区把新数据存进去然后让中控数组map新增一个指针指向这个新buffer将其管理起来即可。deque的底层实际上是一段分段连续的空间并非真正的连续空间。为了维护整体连续以及随机访问的假象这个重任就落在了deque的迭代器身上。因此deque的迭代器设计非常复杂内部包含了4 个指针用来在多个缓冲区之间跳转和定位。下图展示了deque的中控数组、缓冲区、迭代器三者之间的关系deque 的优缺点deque优点与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。queue缺点但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构。4.为什么选择deque作为stack和queue的底层默认容器stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器比如vector和list都可以queue是先进先出的特殊线性数据结构只要具有push_back和pop_front操作的线性结构都可以作为queue的底层容器比如list。但是STL中对stack和queue默认选择deque作为其底层容器主要是因为stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长时deque不仅效率高而且内存使用率高。结合了deque的优点而完美的避开了其缺陷。
【C++】《三种容器适配器没你想的那么复杂：从 stack到queue再到 priority_queue，顺便聊聊仿函数》
一.stack 的介绍和使用1.stack 的介绍https://cplusplus.com/reference/stack/stack/?kwstack#google_vignette1.stack是一种容器适配器专门设计用来处理LIFO后进先出的场景。在这种数据结构中元素的插入和删除都只能在容器的一端进行。2.stack 本身并不管理数据而是作为容器适配器存在的——它把某个底层容器包起来只暴露出一组特定的接口从尾部栈顶压入数据、从尾部弹出数据。这组受限的接口正好满足了栈“后进先出”的行为特征。3.stack 的底层容器不是固定的可以是任何符合要求的容器类。这个容器至少需要支持以下四个操作empty()判断是否为空back()获取尾部元素即栈顶push_back()在尾部插入元素入栈pop_back()从尾部删除元素出栈4.常见的容器如 vector、deque、list 都满足这些要求。如果你不指定底层容器stack 默认会使用 deque。2.stack 的使用在STL的stack 是没有迭代器的因为如果有了迭代器就可以随意访问元素了这样就无法保证后进先出的性质了。3.stack 的模拟实现从栈的接口中可以看出栈实际是一种特殊的vector因此使用vector完全可以模拟实现stack。#pragma once #include vector // vector 也可以作为底层容器 #include deque // deque 是默认底层容器 #include iostream using namespace std; namespace hjq { // stack 容器适配器 // T栈中存储的数据类型 // Container底层容器类型默认为 deque把 Container 的尾部当作栈顶 templateclass T, class Container dequeT class stack { public: // 构造函数默认即可底层容器会自己初始化 stack() {} // 容量相关 // 判断栈是否为空 bool empty() const { return _con.empty(); } // 返回栈中元素个数 size_t size() const { return _con.size(); } // 元素访问 // 返回栈顶元素可修改 T top() { return _con.back(); // 尾部就是栈顶 } // 返回栈顶元素只读 const T top() const { return _con.back(); } // 修改操作 // 入栈在尾部插入元素 void push(const T x) { _con.push_back(x); // 尾部插入 → 入栈 } // 出栈删除尾部元素 void pop() { _con.pop_back(); // 尾部删除 → 出栈 } // 交换两个栈的内容C11 void swap(stackT, Container st) { std::swap(_con, st._con); } private: Container _con; // 底层容器所有操作都转发给它 }; void test() { // 可以用 vector 做底层容器 // stackint, vectorint st; // 可以用 list 做底层容器 // stackint, listint st; // 默认用 deque 做底层容器 stackint st; st.push(1); st.push(2); st.push(3); // 遍历栈后进先出 while (!st.empty()) { cout st.top() ; // 输出栈顶元素 st.pop(); // 弹出栈顶 } cout endl; } } int main() { hjq::test(); return 0; }在这里的代码里不需要写构造函数因为在默认构造函数的初始化列表阶段自定义类型成员 _con 会自动调用它的默认构造函数。二.queue 的介绍和使用1. queue的介绍http://www.cplusplus.com/reference/queue/queue/1.队列queue 是一种容器适配器专门用在 FIFO先进先出 的场景中。数据从容器的一端进入从另一端出去就像排队一样——先来的先服务。2.队列本身不管理数据而是作为容器适配器存在的——它把某个底层容器包起来只暴露一组特定的接口从队尾入队、从队头出队。这组受限的接口正好满足了队列“先进先出”的行为特征。3.队列的底层容器不是固定的可以是任何符合要求的容器。这个容器至少需要支持以下六个操作empty()判断队列是否为空size()返回队列中元素的个数front()获取队头元素的引用back()获取队尾元素的引用push_back()在队尾插入元素入队pop_front()在队头删除元素出队4. 常见的容器如 deque 和 list 都满足这些要求。如果你不指定底层容器queue 默认会使用 dequ2.queue 的使用queue 是没有迭代器的因为有了迭代器就可以随意访问元素了就无法保证先进先出的性质了。3.queue的模拟实现因为queue的接口中存在头删和尾插因此使用vector来封装效率太低故可以借助list来模拟实现queue具体如下#pragma once #include deque // deque 是默认底层容器 #include iostream using namespace std; namespace hjq { // queue 容器适配器 // T队列中存储的数据类型 // Container底层容器类型默认为 deque // 特点尾部当作队尾入队头部当作队头出队 templateclass T, class Container dequeT class queue { public: // 构造函数默认即可底层容器会自己初始化 queue() {} // 容量相关 // 判断队列是否为空 bool empty() const { return _con.empty(); } // 返回队列中元素个数 size_t size() const { return _con.size(); } // 元素访问 // 返回队头元素可修改 T front() { return _con.front(); // 头部就是队头 } // 返回队尾元素可修改 T back() { return _con.back(); // 尾部就是队尾 } // 返回队头元素只读 const T front() const { return _con.front(); } // 返回队尾元素只读 const T back() const { return _con.back(); } //修改操作 // 入队在尾部插入元素 void push(const T val) { _con.push_back(val); // 尾部插入 -- 入队 } // 出队在头部删除元素 void pop() { _con.pop_front(); // 头部删除 -- 出队 } private: Container _con; // 底层容器所有操作都转发给它 }; void test() { // 可以用 list 做底层容器 // queueint, listint q; // 默认用 deque 做底层容器 queueint q; q.push(1); q.push(2); q.push(3); // 遍历队列先进先出 while (!q.empty()) { cout q.front() ; // 输出队头元素 q.pop(); // 弹出队头 } cout endl; } } int main() { hjq::test(); return 0; }跟stack一样不需要写构造函数因为在默认构造函数的初始化列表阶段自定义类型成员 _con 会自动调用它的默认构造函数。三. priority_queue的介绍和使用1.priority_queue的介绍http://www.cplusplus.com/reference/queue/priority_queue/1.优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素5. 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。2.priority_queue的使用优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意默认情况下priority_queue是大堆。priority_queue 中的元素按权值大小排列只有堆顶元素权值最高才能被访问或取出。它不提供遍历功能所以也没有迭代器。【注意】1. 默认情况下priority_queue是大堆。#include vector #include queue #include functional // greater算法的头文件 void TestPriorityQueue() { // 默认情况下创建的是大堆其底层按照小于符号()比较 vectorint v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5}; priority_queueint q1; for (auto e : v) { q1.push(e); } cout q1.top() endl; // 如果要创建小堆将第三个模板参数换成greater比较方式即可 priority_queueint, vectorint, greaterint q2(v.begin(), v.end()); cout q2.top() endl; }2. 如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供 或者 的重载。class Date { public: Date(int year 2026, int month 8, int day 27) : _year(year) , _month(month) , _day(day) {} bool operator(const Date d) const // 运算符重载 { return (_year d._year) || (_year d._year _month d._month) || (_year d._year _month d._month _day d._day); } bool operator(const Date d) const // 运算符重载 { return (_year d._year) || (_year d._year _month d._month) || (_year d._year _month d._month _day d._day); } friend ostream operator(ostream _cout, const Date d) { _cout d._year - d._month - d._day; return _cout; } friend struct DateLess; private: int _year; int _month; int _day; }; void test_priority_queue1() { // 大堆需要用户在自定义类型中提供 的重载 priority_queueDate q1; q1.push(Date(2026, 8, 27)); q1.push(Date(2026, 8, 26)); q1.push(Date(2026, 8, 28)); cout q1.top() endl; // 输出2026-8-28最大日期 // 小堆需要用户在自定义类型中提供 的重载 priority_queueDate, vectorDate, greaterDate q2; q2.push(Date(2026, 8, 27)); q2.push(Date(2026, 8, 26)); q2.push(Date(2026, 8, 28)); cout q2.top() endl; // 输出2026-8-26最小日期 } // 自定义仿函数按小于比较日期 struct DateLess { bool operator()(const Date d1, const Date d2) { return (d1._year d2._year) || (d1._year d2._year d1._month d2._month) || (d1._year d2._year d1._month d2._month d1._day d2._day); } }; void test_priority_queue2() { // 大堆第3个模板参数传自定义仿函数 DateLess priority_queueDate, vectorDate, DateLess q1; q1.push(Date(2026, 8, 27)); q1.push(Date(2026, 8, 26)); q1.push(Date(2026, 8, 28)); cout q1.top() endl; // 输出2026-8-28最大日期 }3.priority_queue的模拟实现通过对priority_queue的底层结构就是堆因此此处只需对对进行通用的封装即可。#pragma once #include iostream #include vector #include functional using namespace std; // priority_queue 本质上就是堆 // 底层默认用 vector 存数据通过向上/向下调整维护堆结构 namespace hjq { //仿函数 less用于建大堆 // 判断 left 是否小于 right templateclass T struct less { bool operator()(const T left, const T right) { return left right; } }; // 仿函数 greater用于建小堆 // 判断 left 是否大于 right templateclass T struct greater { bool operator()(const T left, const T right) { return left right; } }; // priority_queue 类模板 // T存储的数据类型 // Container底层容器默认 vector // Compare比较方式默认 less建大堆 templateclass T, class Container vectorT, class Compare std::lessT class priority_queue { public: // 默认构造 priority_queue() {} //迭代器区间构造 // 用 [first, last) 区间构造堆 template class InputIterator priority_queue(InputIterator first, InputIterator last) { // 1. 先把数据全部插入底层容器 while (first ! last) { _con.push_back(*first); first; } // 2. 建堆从最后一个非叶子节点开始向下调整 // 最后一个非叶子节点 (size - 2) / 2 int child _con.size() - 1; int parent (child - 1) / 2; for (int i parent; i 0; i--) { adjust_down(i); } } // adjust_up向上调整 // 用于 push尾部插入新元素后向上调整恢复堆结构 void adjust_up(size_t child) { Compare com; // 仿函数对象决定是大堆还是小堆 size_t parent (child - 1) / 2; while (child 0) { // 如果父节点不满足堆序要求交换父子 if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); child parent; parent (child - 1) / 2; } else { break; // 满足堆序停止调整 } } } // 插入元素 void push(const T x) { _con.push_back(x); // 尾插 adjust_up(_con.size() - 1); // 从尾部向上调整 } // adjust_down向下调整 // 用于 pop 和建堆从某个节点向下调整恢复堆结构 // 前提左右子树都已经满足堆序 void adjust_down(size_t parent) { Compare com; size_t child parent * 2 1; // 左孩子 while (child _con.size()) { // 1. 选出左右孩子中更符合堆序的那个 if (child 1 _con.size() com(_con[child], _con[child 1])) { child; // 右孩子更符合 } // 2. 父节点与孩子比较不满足堆序就交换 if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); parent child; child parent * 2 1; } else { break; // 满足堆序 } } // 删除堆顶 void pop() { std::swap(_con[0], _con[_con.size() - 1]); // 堆顶换到尾部 _con.pop_back(); // 删除尾部 adjust_down(0); // 从根向下调整 } //获取堆顶只读不能返回可修改的引用否则会破坏堆结构 const T top() { return _con[0]; } // 容量相关 bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; // 底层容器 }; } void test_queue_priority() { // 大堆测试 hjq::priority_queueint q1; q1.push(5); q1.push(1); q1.push(4); q1.push(2); q1.push(3); q1.push(6); cout q1.top() endl; q1.pop(); q1.pop(); cout q1.top() endl; // 小堆测试 vectorint v{5, 1, 4, 2, 3, 6}; hjq::priority_queueint, vectorint, hjq::greaterint q2(v.begin(), v.end()); cout q2.top() endl; q2.pop(); q2.pop(); cout q2.top() endl; }4.仿函数1仿函数的定义仿函数又称为函数对象本质上是一个重载了operator()运算符的类对象。它让一个类用起来像函数一样可以直接通过对象调用。语法上仿函数的调用方式和普通函数几乎一样。但实际上调用仿函数时背后执行的是类中重载的operator()函数只不过这种写法看起来和函数调用没区别。// 仿函数函数对象重载了 operator() 的类 // 让对象可以像函数一样被调用 // 定义一个仿函数类 Less用来比较两个整数的大小 struct Less { // 重载 operator()接收两个 int 参数返回比较结果 // 这个类有了这个函数就可以像函数一样调用了 bool operator()(const int x, const int y) { return x y; } }; void test_functor() { // 方式一先创建对象再通过对象调用 Less less; // 实例化一个 Less 对象 cout less(1, 2) endl; // 调用 less.operator()(1, 2) // 输出1 // 方式二用匿名对象直接调用 cout Less()(1, 2) endl; // Less() 构造匿名对象 // 再调用 operator()(1, 2) // 输出1 }https://cplusplus.com/reference/functional/greater/https://cplusplus.com/reference/functional/less/// 仿函数函数对象重载了 operator() 的类对象可以像函数一样使用 //小于比较仿函数 // 功能判断 x 是否小于 y templateclass T struct Less { bool operator()(const T x, const T y) { return x y; // 调用类型自身的 运算符 } }; //大于比较仿函数 // 功能判断 x 是否大于 y templateclass T struct Greater { bool operator()(const T x, const T y) { return x y; // 调用类型自身的 运算符 } }; void test_functor() { // 使用 Less 仿函数 Lessint less; // 实例化对象 cout less(1, 2) endl; // 1 2 → true -- 输出 1 // 使用 Greater 仿函数 Greaterint greater; // 实例化对象 cout greater(1, 2) endl; // 1 2 → false -- 输出 0 }仿函数 less 和 greater 是继承的 binary_function可以看作是对于一类函数的总体声明而且这是函数做不到的。// greater标准库中的大于比较仿函数 // 继承 binary_function 只是为了兼容旧版适配器 // 实际比较逻辑就是x y template class T struct greater : binary_functionT, T, bool { bool operator()(const T x, const T y) const { return x y; }; // less标准库中的小于比较仿函数 // 继承 binary_function 只是为了兼容旧版适配器 // 实际比较逻辑就是x y template class T struct less : binary_functionT, T, bool { bool operator()(const T x, const T y) const { return x y; } };2模板实例化时仿函数的使用类模板和函数模板在使用仿函数时传的东西不一样类模板是显式实例化在 中指定模板参数的实际类型所以传的是类型。比如 priority_queue//第1个模板参数是存储数据的类型 //第2个模板参数是基础容器的类型 //第3个模板参数是仿函数的类型 template class T, class Container vectorT, class Compare lesstypename Container::value_type class priority_queue; void test() { // 建小堆 priority_queueint, vectorint, greaterint pq; // 传仿函数greaterint类型 }函数模板是隐式实例化编译器根据实参推演模板参数所以传的是对象。比如 sort// 第1个模板参数迭代器的类型 // 第2个模板参数是仿函数的类型 template class RandomAccessIterator, class Compare // 函数的第1,2个参数是迭代器对象 // 函数的第3个参数是仿函数类的对象 void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); void test() { vectorint v { 5,3,2,4,1 }; // 排降序() sort (v.begin(), b.end(), greaterint()); // 传仿函数类greaterint的匿名对象 for (const auto x : v) cout x ; cout endl; }给大家小结一下就是类模板用类型造对象函数模板拿对象推类型。给 priority_queue 的是类型 greaterint给 sort 的是对象 greaterint()。四.容器适配器1.什么是适配器适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。2.STL标准库中stack和queue 的底层结构虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用deque比如3.deque的简单介绍(了解)https://cplusplus.com/reference/deque/deque/deque的原理介绍:deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。vector、list、deque 对比vector 是一段连续的物理空间。优点支持随机访问O(1) 就能拿到任意位置的元素。空间利用率高底层是连续空间不容易产生内存碎片。CPU 高速缓存命中率高遍历时性能好。缺点空间不够时需要增容增容代价很大重新分配空间、搬移元素、释放旧空间还有一定的空间浪费。头部和中间插入删除效率低O(N)。list 不是连续空间由一个个独立的节点通过指针链接起来。优点按需申请释放空间不会浪费。任意位置插入删除都是 O(1)不需要搬移数据。缺点不支持随机访问只能顺着指针一个个找。空间利用率低每个节点还要额外存两个指针小节点容易造成内存碎片。CPU 高速缓存命中率低节点在内存中分散分布。deque 介于两者之间并不是真正连续的空间而是由一段段连续的小空间拼接而成底层类似一个动态的二维数组。它的特点支持头插头删vector 做不了的事它行。支持随机访问list 做不了的事它也行。看起来像是融合了 vector 和 list 的优点。deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示当deque需要增容时不需要像vector那样经历重新配置空间、搬移元素、释放旧空间等一系列操作。它只需要新增一个buffer缓冲区把新数据存进去然后让中控数组map新增一个指针指向这个新buffer将其管理起来即可。deque的底层实际上是一段分段连续的空间并非真正的连续空间。为了维护整体连续以及随机访问的假象这个重任就落在了deque的迭代器身上。因此deque的迭代器设计非常复杂内部包含了4 个指针用来在多个缓冲区之间跳转和定位。下图展示了deque的中控数组、缓冲区、迭代器三者之间的关系deque 的优缺点deque优点与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。queue缺点但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构。4.为什么选择deque作为stack和queue的底层默认容器stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器比如vector和list都可以queue是先进先出的特殊线性数据结构只要具有push_back和pop_front操作的线性结构都可以作为queue的底层容器比如list。但是STL中对stack和queue默认选择deque作为其底层容器主要是因为stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长时deque不仅效率高而且内存使用率高。结合了deque的优点而完美的避开了其缺陷。