【C++】【STL】别再混淆！C++容器适配器不是“容器”，这篇讲清它的本质
🔥拾Ծ光：个人主页
👏👏👏欢迎来到我的专栏：《C++》，《C++类和对象》，《数据结构》，《C语言》
📌文档：栈（stack），队列（queue），双端队列（deque），priority_queue
与本文相关博客：《容器进阶：deque的“双端优势” vs list的“链式灵活” vs vector的“连续高效”》
在前面的一篇文章我们讲解了deque容器，其非常适合作为适配器stack和queue的底层数据结构，下面我就来带大家看看这两个适配器是如何与deque结合的！
一、什么是容器适配器？
在 C++ 标准库中，容器适配器（Container Adapters） 是一种基于现有容器实现的特殊容器，它们提供了更特定的接口和功能，隐藏了底层容器的部分特性，仅暴露适配后的操作方式。
⭐️容器适配器不直接存储数据，而是通过封装底层容器（如 vector、deque、list 等）来实现功能，底层容器可以通过模板参数指定（通常有默认值）。
C++中最常用的容器适配器有三种：std::stack（栈）；std::queue（队列)；std::priority_queue（优先队列）。
容器适配器的特点接口简化：仅提供适配场景所需的操作（如 stack 没有迭代器，无法遍历内部元素）。底层可配置：通过模板参数指定底层容器（需满足适配器的操作要求，如 stack 需要push_back、pop_back等接口）。无迭代器：适配器不提供迭代器，无法像普通容器那样遍历元素，只能通过其特定接口操作。
栈和队列的接口比较简单，所以我们不再作介绍，具体接口可以通过上面的文档查看。下面我们直接模拟实现，来加深我们对这种特殊结构的理解！！！
由于适配器的底层结构为其他容器（vector，list，deque...），像插入删除执行操作，其实是由底层的容器实现，所以，我们只需要运用底层容器的函数接口。同样我们创建一个自己的命名空间，在自己的命名空间中写代码
二、3大容器适配器
1、栈——stack
文档：栈（stack）
// 将deque作为默认容器 template<class T, class Container = deque<T>> class stack { public: // ... private: Container _con; // 成员变量 };
成员变量其实就是我们通过底层容器实例化出的一个对象，我们只需要用这个对象来找到相应的函数接口。
2.1、在栈顶插入——push
void push(const T& x) { _con.push_back(x); }2.2、获取有效数据个数——size
const T& size()const { return _con.size(); }2.3、获取栈顶数据——top
const T& top()const { return _con.back(); }2.4、删除栈顶数据——pop
void pop() { _con.pop_back(); }2.5、判空——empty
bool empty() { return _con.empty(); }2、队列——queue
文档：队列（queue）
// 将deque作为默认容器 template<class T, class Container = deque<T>> class queue { public: // ... private: Container _con; // 成员变量 };
3.1、在队尾插入——push
void push(const T& x) { _con.push_back(x); }3.2、删除队头数据——pop
void pop() { _con.pop_front(); }3.3、获取有效数据个数——size
const size_t size()const { return _con.size(); }3.4、获取队头数据——front
const T& front()const { return _con.front(); }3.5、获取队尾数据——back
const T& back()const { return _con.back(); }3.6、判空——empty
bool empty() { return _con.empty(); }3、优先级队列——priority_queue
1、priority_queue介绍
priority_queue底层选择用vector作为默认容器，它基于底层容器实现，能保证每次从顶部取出走的元素都是 “优先级最高” 的（默认是最大值）。其核心特性是通过堆（heap）算法维护优先级（通常是大根堆，即最大值在顶部），插入元素后会自动调整结构以满足优先级规则。
即priority_queue的底层支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用 算法函数建堆（make_heap）、堆尾插入（push_heap）和堆顶删除（pop_heap）来自动完成此操作。
相关接口：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
top()：返回容器中第一个元素的引用
push()：在队尾插入元素
pop()：删除队头元素
2、特性测试
插入5个没有排好序的数进行排序：
void test01() { priority_queue<int> pq; pq.push(5); pq.push(2); pq.push(4); pq.push(3); pq.push(1); while (!pq.empty()) { cout << pq.top() << endl; pq.pop(); } }priority_queue底层默认建大堆，即输出结果为降序
void test02() { priority_queue<int, vector<int>,Great<int>> pq; // Great：建小堆 pq.push(5); pq.push(2); pq.push(4); pq.push(3); pq.push(1); while (!pq.empty()) { cout << pq.top() << endl; pq.pop(); } }
这里需要注意：当我们建大堆时——降序；建小堆——升序。
3、模拟实现
/*第二个参数：默认适配容器为vector数组容器 第三个参数：采用仿函数，默认建大堆*/ template<class T,class Container = vector<T>,class Compare = Less<T>> class priority_queue { public: // ... private: Container _con; // 成员变量 };⭐️我们要用一个类实现建大堆和建小堆的功能，这里就需要仿函数（也就是类模板的第三个参数）来实现
/*为了能够满足priority_queue实现升序（建小堆）和降序（建大堆）的功能，我们实现两个仿函数的类作为priority_queue类模板的第三个参数 用于随时满足priority_queue实现升序和降序的效果*/ template<class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> class Great { public: bool operator()(const T& x, const T& y) { return x > y; } };
3.1、获取有效数据个数
size_t size()const { return _con.size(); }3.2、获取队头数据
const T& top() { return _con.front(); }3.3、队尾插入
在队尾插入数据后，堆的结构就可能被破坏，所以我们要向上调整建堆来维持数据的优先级。
// 向上调整建堆 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 push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1); }3.4、队头删除
删除队头数据后，堆的结构被破坏，我们需要将最后一个数据放到原来第一个数据的位置，保证堆的剩余结构不被破坏，然后通过向下调整建堆的方式，维持数据的优先级。
// 向下调整建堆 void AdjustDown(int parent) { Compare com; // 实例化一个仿函数类的对象 int child = 2 * parent + 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 = 2 * parent + 1; } else break; } }void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); }3.5、判空
bool empty()const { return _con.empty(); }三、仿函数
在上面测试priority_queue以及实现priority_queue的push和pop时就使用了仿函数，因为，当我们想要让一组数升序排序或者降序排序时，我们不可能说去实现两个priority_queue的类，一个默认建大堆，降序排序；一个默认建小堆，升序排序。所以，C++引入了仿函数的概念，在实现类模板时，可以将仿函数作为模板参数，这样在我们使用时调用对应的仿函数，就能达到我们想要的效果。
1、什么是仿函数？
仿函数（Functor）：也称为函数对象（Function Object），是一种在 C++ 中通过类或结构体实现的可调用实体，其实就是一个类。
仿函数的核心特点是 重载了 operator() 运算符，使得类的对象可以像普通函数一样被调用。
仿函数是 C++ 中 “以类模拟函数” 的重要机制，这种机制结合了面向对象的封装性和函数的灵活性，在 STL和算法中有着广泛应用。
仿函数的核心特点：
1. 重载 operator()
使用：
Add add; //创建仿函数对象 int result = add(2, 3); //像函数一样调用，结果为5 通过在类中定义 operator() 运算符，使得该类的对象可以像函数一样被调用：
class Add { public: int operator()(int a, int b) // 重载()运算符 { return a + b; } }; 2、仿函数的使用⭐️
让冒泡排序既可以升序又可以降序排序：
#include <iostream> using namespace std; /*-----------------------第一部分：实现比较仿函数（类模板）-----------------------*/ template<class T> class Less { public: bool operator()(const T& x, const T& y) const //注意：加const提高通用性 { return x < y; } }; template<class T> class Greater { public: bool operator()(const T& x, const T& y) const { return x > y; } }; /*-----------------------第二部分：实现冒泡排序（函数模板）-----------------------*/ template<class Compare> void BubbleSort(int* a, int n, Compare com) { for (int i = 1; i <= n - 1; i++) { int flag = 1; for (int j = 1; j <= n - i; j++) { if (com(a[j], a[j - 1])) //用仿函数来比较a[j]和a[j-1]的大小 { swap(a[j - 1], a[j]); flag = 0; } if (flag) break; //如果某一趟排序没有进行交换，说明当前数组中的元素已经有序了，直接退出 } } int main() { // 创建仿函数对象 Less<int> less; //实例化仿函数对象 Greater<int> greater; // 冒泡排序结合仿函数进行排序 int a[] = { 9,1,2,8,5,7,4,6,3 }; int n = sizeof(a) / sizeof(a[0]); //1.使用仿函数进行冒泡排序（升序/降序） BubbleSort(a, n, less); //仿函数Less<int> less”进行升序排序 for (int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl; BubbleSort(a, n, greaterFunc); // 仿函数Greater<int>进行降序排序 for (int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl; // 也可直接传递匿名对象（临时对象） BubbleSort(a, n, Less<int>()); // 升序 for (int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl; BubbleSort(a, n, Greater<int>()); // 降序 for (int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl; return 0; } 四、模拟实现完整代码
#include<stack.h>
#include<iostream> #include<vector> #include<list> #include<deque> using namespace std; namespace hds { template<class T, class Container = deque<T>> class stack { public: stack() { } // 获取有效数据个数 const T& size()const { return _con.size(); } // 获取栈顶数据 const T& top()const { return _con.back(); } // 向栈顶插入数据 void push(const T& x) { _con.push_back(x); } // 删除栈顶数据 void pop() { _con.pop_back(); } // 判空 bool empty() { return _con.empty(); } private: Container _con; }; }#include<queue.h>
#include<iostream> #include<vector> #include<list> #include<deque> using namespace std; // deque是vector和list的混合 // deque的头插和尾插，以及头删和尾删效率很高，更甚于vector和list // deque的下标访问效率还行，略逊于vector // deque在中间位置插入数据，效率极低 // 而栈和队列一般不会中间插入数据，所以deque作为栈和队列的默认容器非常合适 namespace hds { template<class T, class Container = deque<T>> class queue { public: queue() { } // 获取有效数据个数 const size_t size()const { return _con.size(); } // 获取队头数据 const T& front()const { return _con.front(); } // 获取队尾数据 const T& back()const { return _con.back(); } // 再队尾插入数据（先进先出） void push(const T& x) { _con.push_back(x); } // 删除队头数据（先进先出） void pop() { _con.pop_front(); } // 判空 bool empty() { return _con.empty(); } private: Container _con; }; }#include<priority_queue>
#include<iostream> #include<queue> #include<list> #include<vector> using namespace std; // 仿函数：本质是一个类，这个类重载operator(), 他的对象可以像函数一样使用 /*为了能够满足priority_queue实现升序（建小堆）和降序（建大堆）的功能，我们实现两个仿函数的类作为priority_queue类模板的第三个参数 用于随时满足priority_queue实现升序和降序的效果*/ template<class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> class Great { public: bool operator()(const T& x, const T& y) { return x > y; } }; namespace hds { /*第二个参数：默认适配容器为vector数组容器 第三个参数：采用仿函数，默认建大堆*/ template<class T,class Container = vector<T>,class Compare = Less<T>> class priority_queue { public: size_t size()const { return _con.size(); } const T& top() { return _con.front(); } 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 push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1); } void AdjustDown(int parent) { Compare com; // 实例化一个仿函数类的对象 int child = 2 * parent + 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 = 2 * parent + 1; } else break; } } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } bool empty()const { return _con.empty(); } private: Container _con; }; }今天的分享到此结束！！！
