C++ 泛型世界的两块拼图：容器适配器与仿函数-北京尧图网络

浮世尘弦个人主页⭐个人专栏《C语言》、《数据结构与算法》、《C》非淡薄无以明志非宁静无以致远前言前言stack和queue是C中的容器适配器不是自己实现存储的新容器而是把现有的容器包装一下只暴露特定的接口让他的行为变成栈或队列这就是容器适配器。在本篇内容中我们使用不同的容器来实现栈和队列比较他们的优缺点进而学习deque容器。这也是本篇的重点内容。让我们开始学习今天的内容吧文章目录C参考文档(cplusplus)一回顾stack和queue的基础特性1stack2queue二使用容器适配器模拟实现栈三使用list模拟实现队列四vector vs list 深度对比⭐五deque(双端队列1deque的介绍2deque的结构3deque的遍历和插入元素4deque的优缺点5性能对比六优先级队列priority_queue1优先级队列的介绍和特征2模拟实现一个优先级队列3优先级队列的作用七仿函数1仿函数的介绍2仿函数的使用结尾C参考文档(cplusplus)stack文档queue文档一回顾stack和queue的基础特性1stack栈最基本的特点是后进先出仅允许在栈顶操作。核心接口push压栈、pop弹栈、top取栈顶。2queue队列最基本的特点是先进先出仅在队头和队尾进行操作。核心接口push入队、pop出队、front取队头、back取队尾。详细可见【数据结构】详解栈和队列二使用容器适配器模拟实现栈首先再介绍一下容器适配器容器适配器就是一种设计模式该种模式是将一个类的接口转换成客户希望的另外一个接口stack和queue都是容器适配器。首先看之前手动管理内存实现的栈//手动管理内存实现栈 template class T class stack { private: T* q; //动态数组指针用来在堆上开辟空间 size_t top;//栈顶元素索引/元素的个数 size_t capacity;//总容量 };使用vector实现栈和使用list实现有什么区别首先栈的基础操作和vector在尾部的操作完美契合。操作匹配std::stack是 LIFO后进先出所有操作push、pop、top都只在栈顶进行。而vector正好提供了push_back()、pop_back()、back()并且都是在尾部操作。效率极高在vector尾部增删元素不需要移动其他元素。虽然vector扩容时会拷贝数据但均摊时间复杂度是 O(1)。而且vector内存连续CPU 缓存命中率极高但是使用vector依旧有许多的缺点。如果使用list,list的内存不连续导致缓存命中率较差实际与逆行速度比vector慢。在单次插入/删除下每次new/delete堆分配开销大。在内存开销上list每个节点要多开两个指针导致内存占用大。接下来是容器适配器下使用vector实现的栈namespace att { //使用容器vector实现栈 template class T//T为容器中元素的类型 class stack { public: //入栈 void push(const T x) { var.push_back(x); } //出栈 void pop() { var.pop_back(); } //返回栈顶元素 const T top()const { return var.back(); } //栈中元素个数 size_t size()const { return var.size(); } //判空 bool empty()const { return var.empty(); } private: vectorT var; }; }测试展示三使用list模拟实现队列由于vector不支持头删pop_front()所以不能使用vector实现队列因此直接使用list实现队列//容器适配器下的队列 namespace att { //使用容器list实现队列 template class T, class Container//T为容器中元素的类型 class stack { public: //入队列 void push(const T x) { var.push_back(x); } //出队列 void pop() { var.pop_front(); } //返回队头元素 const T front()const { return var.front(); } //返回队尾元素 const T back()const { return var.back(); } //队列中元素个数 size_t size()const { return var.size(); } //判空 bool empty()const { return var.empty(); } private: Container var; }; }测试展示四vector vs list 深度对比⭐对比维度vector动态数组list双向链表底层结构物理空间连续的动态数组物理空间不连续的双向链表随机访问✅ 支持高效下标随机访问O(1)❌ 不支持下标随机访问只能遍历O(n)插入/删除❌ 头部和中间插入删除效率低O(n)需搬移元素✅ 尾部操作效率不错均摊 O(1)✅ 任意位置插入删除极快O(1)已知位置❌ 需要遍历找到位置且每次分配/释放节点开销大空间管理❌ 空间不足需扩容有代价效率损失空间浪费通常 1.5~2倍扩容✅ 按需申请释放空间不需要扩容没有预留浪费缓存与内存✅ 物理空间连续高速缓存利用率高✅ 额外内存开销极小❌ 缓存不友好节点散落堆各处❌ 每个节点需额外存前驱、后继指针内存开销大易产生碎片迭代器失效❌ 扩容后所有指针、引用、迭代器全部失效✅ 除被删元素外其他元素的迭代器/引用始终有效为了解决vector和list的问题C引入了一个新的容器deque,库中使用的默认容器就是deque五deque(双端队列1deque的介绍std::deque是 C STL 中的双端队列容器。你可以把它理解为“支持头尾两端高效插入删除的动态数组”。与vector比较头插效率高不需要搬移元素与 list比较空间利用率比较高。deque是vector和list的缝合使用随机迭代器。融合了两种容器的优点。2deque的结构deque并不是真正的连续的空间。而是由一段段连续的小空间组成类似一个动态的二维数组中控数组当中放的是不同空间的指针指向的空间是连续的中控数组不是从数组的开头开辟空间的而是在数组的中间方便左右两边插入或者删除元素。每个空间依靠4个迭代器来维护cur指向当前元素位置first和last分别指向起始元素位置和最后一个元素的下一个位置node作为一个二级指针指向中控数组的每个节点。上面是每个连续空间的迭代器还有两个迭代器维护中控数组本身分别是start和finishstart指向中控数组当中第一个元素finish指向中控数组当中最后一个元素。3deque的遍历和插入元素deque的遍历deque插入元素头插尾插4deque的优缺点对比维度具体表现判定双端操作头尾插入/删除均为 O(1)不像vector头部操作需要搬移✅优点随机访问提供[]和at()支持 O(1) 随机访问list做不到✅优点扩容机制只需分配新缓冲区并在中控数组加指针不拷贝/移动旧元素✅优点引用稳定性头尾增删时除被删元素外其他元素的指针和引用保持有效✅优点STL 适配stack和queue默认底层容器兼顾尾插、头删、尾删的高效性✅优点中间插删依然是 O(n)且因分段连续搬移元素的常数开销比vector更大❌缺点缓存命中率内存分段连续遍历跨缓冲区需指针跳转CPU 预读效率不如vector❌缺点内存控制无capacity()和reserve()不支持像vector那样精确预分配内存❌缺点内存碎片有中控数组和多个缓冲区的额外开销碎片多于vector但远少于list❌缺点迭代器不是原生指针是封装了缓冲区边界检查的复杂对象实现复杂且有轻微开销❌缺点补充deque的缺点deque不适合遍历因为在遍历时deque需要频繁的检查是否移动到小数组的边界导致效率低下。而实际情景下可能需要经常进行遍历因此实际情况下通常使用的线性结构大多数是vector和list这样的deque使用的不多。而使用deque作为stack和queue的底层容器则是stack和queue不需要遍历只需要在一端进行操作。因此避免了deque的缺点使用了其优点。5性能对比使用排序对比一下vector和deque的下标访问效率//容器排序效率比对 //deque和vector直接进行对比 void test1() { srand(time(0)); const int N 1000000; dequeint dq; vectorint v; for (int i 0; i N; i) { auto e rand() i; v.push_back(e); dq.push_back(e); } int begin1 clock(); sort(v.begin(), v.end()); int end1 clock(); int begin2 clock(); sort(dq.begin(), dq.end()); int end2 clock(); printf(vector:%d\n, end1 - begin1); printf(deque:%d\n, end2 - begin2); } //deque拷贝成vector进行排序和直接排序对比 void test2() { srand(time(0)); const int N 1000000; dequeint dq1; dequeint dq2; for (int i 0; i N; i) { auto e rand() i; dq1.push_back(e); dq2.push_back(e); } int begin1 clock(); sort(dq1.begin(), dq1.end()); int end1 clock(); int begin2 clock(); // 拷贝到vector vectorint v(dq2.begin(), dq2.end()); sort(v.begin(), v.end()); dq2.assign(v.begin(), v.end()); int end2 clock(); printf(deque sort:%d\n, end1 - begin1); printf(deque copy vector sort:%d\n, end2 - begin2); }release下结果这表明vector下标访问的效率比deque访问下标的效率高。优先级队列官方文档优先级队列六优先级队列priority_queue1优先级队列的介绍和特征优先级队列是CSTL中的容器适配器不遵循“先进先出”的原则。而是优先级最高的元素先出队。默认值的大小作为优先级。1使用时需要包含头文件#include queue2默认底层容器是vector默认使用大堆维护元素顺序。3无迭代器不支持遍历不支持随机访问只能访问堆顶元素。4时间复杂度插入和删除均为O(logN)取堆顶元素为O(1)5对底层容器的要求_1是序列容器 _2迭代器是随机访问容器 _3提供以下成员函数front()back()push_back()pop_back()size()empty()begin()/end()因此标准库当中一般只有deque和vector能够支持。图中参数的第一个部分是元素的类型第二个部分是容器第三个部分是比较器比较器部分决定了“谁先出队”的排序规则默认是less也就是大堆(最大的元素优先级最高。typename Container::value_type是容器中的元素类型也就是T优先级队列支持的功能如何调整为一个小堆呢只需要将容器中比较器中的less改成greater即可。这里的比较器部分就是一个仿函数实际上是一个类。这个类当中写了元素的比较规则。2模拟实现一个优先级队列#pragma once //模拟实现优先级队列 template class T class Less { public: bool operator()(const T x, const T y) { return x y; } }; template class T class Greater { public: bool operator()(const T x, const T y) { return x y; } }; namespace att { templateclass T,class Container vectorT ,class Compare LessT class priority_queue { public: //向上调整-大堆 void AdjustUp(int child) { Compare com; int parent (child - 1) / 2; while (child 0) { if (com(con[parent], con[child]))//通过仿函数 { swap(con[parent], con[child]); child parent; parent (child - 1) / 2; } else { break; } } } //向下调整-大堆 void Adjustdown(int parent) { Compare com; int child parent * 2 1;//假设左孩子大 while (child con.size())// { //先找到大的那个孩子 if (child 1 con.size() com(con[child], con[child 1])) { child; } if (com(con[parent], con[child])) { swap(con[parent], con[child]); parent child; child parent * 2 1; } else { break; } } } //插入元素 void push(const T x) { con.push_back(x); AdjustUp(con.size() - 1); } //删除元素 void pop() { swap(con[0], con[con.size() - 1]); con.pop_back(); Adjustdown(0); } size_t size()const { return con.size(); } const T top() { return con[0]; } bool empty()const { return con.empty(); } private: Container con; }; }运行结果3优先级队列的作用1解决TOP-K问题leetcode题目数组当中的第k个最大元素解法class Solution { public: int findKthLargest(vectorint nums, int k) { priority_queueint q(nums.begin(),nums.end()); for(int i 0;ik-1;i) { q.pop(); //取出前k-1个元素 } return q.top(); } };七仿函数1仿函数的介绍仿函数又称为函数对象本质上是一个重载了operator()的类他的对象可以像普通函数那样进行调用对象名(函数参数。对比普通函数使用仿函数的好处可以携带状态仿函数是一个类可以有成员变量。普通函数只能靠全局变量或静态变量来记录状态而仿函数每次实例化都可以有不同的状态。性能更高作为类编译器在编译时就能确定调用逻辑容易内联Inline没有函数指针跳转的开销。可以作为类型普通函数是函数指针运行时才能确定而仿函数是一个类型可以作为模板参数。上面使用的Less和Greater就是仿函数。如上面所示许多的仿函数都是一个空类大小都是12仿函数的使用下面看一个仿函数的使用案例排序//仿函数控制升序和降序 template class Compare void Buffsort(int* a, size_t n, Compare com) { //控制趟数 for (int i 0;i n;i) { //单趟 int flag 0; for (int j 1;j n - i;j) { if (com(a[j], a[j - 1]))//less升序grather降序 { swap(a[j], a[j - 1]); flag 1; } } if (flag 0) { break;//提前返回 } } }运行展示这里通过仿函数直接实现了升序和降序。有点类似模版不过模版是自定义类型而仿函数可以控制函数内部的规则。使用案例2日期类的比较class Date { friend ostream operator(ostream _cout, const Date d); public: Date(int year 1980, int month 1, int day 1) : _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); } private: int _year; int _month; int _day; }; ostream operator(ostream _cout, const Date d) { _cout d._year - d._month - d._day; return _cout; }上面的日期类自己实现了比较的逻辑。测试1测试2由于生成的地址大小是随机的所以排列的顺序也是随机的。此时就需要仿函数来控制排序的逻辑class DateLess { public: bool operator()(Date* p1, Date* p2) { return *p1 *p2; } };本篇文章中所涉及到的代码gitee链接容器适配器与仿函数以上就是本文《泛型世界的两块拼图容器适配器与仿函数》的全部内容了如果对你有所帮助的话请大佬不妨给博主来个“一键三连”这对我是大大的支持也能让博主产出更优质的内容。结尾往期回顾一条双向链的诞生手写 list 模拟实现总结本文系统讲解C中stack与queue的容器适配器实现对比vector与list在栈、队列模拟中的优劣并深入剖析deque双端队列的结构与性能特点。指出deque兼顾头尾高效操作与随机访问成为stack和queue的默认底层容器。同时介绍priority_queue的原理与应用结合仿函数实现自定义比较逻辑。⚡把上面的内容吃透就休息一下吧⚡

C++ 泛型世界的两块拼图：容器适配器与仿函数

相关推荐

【minio】#4 | MinIO API 文件操作

（论文速读）LogSAD：无需训练的结构异常与逻辑异常统一检测

Psychol Med：有抑郁症状的老年人中结构-功能连接耦合的改变

更多资讯

HTTP/2与HTTP/3核心机制对比及部署实战指南

二叉树随机漫步：用蒙特卡洛思想探测树结构深度

中转API网关与Token机制实战：从JWT签发到限流计费全解析

轻量级Verilog仿真环境搭建：VSCode + iverilog + GTKWave 指南

大数运算课程设计：十进制与二进制高精度算法实现与避坑指南

用Verilog设计MIPS32单周期CPU：从数据通路到指令执行的完整实战

今日更新

Multisim仿真NE555 PWM控制器：从搭电路到调占空比全流程

S32K312 AUTOSAR BSW开发实战：从配置踩坑到烧录交付

双目视觉三维人脸重建：从视差图到点云粗配准全流程解析

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？