C++ 容器适配器基于现有容器构建，隐藏底层细节。主要包括 stack（栈）、queue（队列）和 priority_queue（优先队列）。stack 默认使用 deque，支持 push/pop/top 操作；queue 同样基于 deque，提供先进先出接口；priority_queue 默认基于 vector 和大根堆，通过仿函数控制排序顺序。文章详细分析了三大适配器的接口特性，并通过模拟实现展示了底层逻辑，包括向上调整和向下调整建堆算法。仿函数作为模板参数实现了灵活的比较策略。
在 C++ 标准库中，容器适配器（Container Adapters） 是一种基于现有容器实现的特殊容器，它们提供了更特定的接口和功能，隐藏了底层容器的部分特性，仅暴露适配后的操作方式。
⭐️容器适配器不直接存储数据，而是通过封装底层容器（如 vector、deque、list 等）来实现功能，底层容器可以通过模板参数指定（通常有默认值）。
C++ 中最常用的容器适配器有三种：
std::stack（栈）；std::queue（队列)；std::priority_queue（优先队列）。
容器适配器的特点 接口简化：仅提供适配场景所需的操作（如 stack 没有迭代器，无法遍历内部元素）。 底层可配置：通过模板参数指定底层容器（需满足适配器的操作要求，如 stack 需要
push_back、pop_back等接口）。 无迭代器：适配器不提供迭代器，无法像普通容器那样遍历元素，只能通过其特定接口操作。
栈和队列的接口比较简单，具体接口可以通过官方文档查看。下面我们直接模拟实现，来加深我们对这种特殊结构的理解。
**由于适配器的底层结构为其他容器（vector，list，deque...），像插入删除执行操作，其实是由底层的容器实现，所以，我们只需要运用底层容器的函数接口。**同样我们创建一个自己的命名空间，在自己的命名空间中写代码。
// 将 deque 作为默认容器
template<class T, class Container = deque<T>>
class stack {
public:
// ...
private:
Container _con; // 成员变量
};
成员变量其实就是我们通过底层容器实例化出的一个对象，我们只需要用这个对象来找到相应的函数接口。
void push(const T& x) { _con.push_back(x); }
size_t size() const { return _con.size(); }
const T& top() const { return _con.back(); }
void pop() { _con.pop_back(); }
bool empty() { return _con.empty(); }
// 将 deque 作为默认容器
template<class T, class Container = deque<T>>
class queue {
public:
// ...
private:
Container _con; // 成员变量
};
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_front(); }
size_t size() const { return _con.size(); }
const T& front() const { return _con.front(); }
const T& back() const { return _con.back(); }
bool empty() { return _con.empty(); }
priority_queue 底层选择用 vector 作为默认容器，它基于底层容器实现，能保证每次从顶部取出走的元素都是'优先级最高'的（默认是最大值）。其核心特性是通过 堆（heap）算法 维护优先级（通常是大根堆，即最大值在顶部），插入元素后会自动调整结构以满足优先级规则。
即 priority_queue 的底层支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用 算法函数建堆（make_heap）、堆尾插入（push_heap）和堆顶删除（pop_heap）来自动完成此操作。
相关接口：
empty()：检测容器是否为空size()：返回容器中有效元素个数top()：返回容器中第一个元素的引用push()：在队尾插入元素pop()：删除队头元素插入 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();
}
}
这里需要注意：当我们建大堆时——降序；建小堆——升序。
/*第二个参数：默认适配容器为 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; }
};
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(); }
在上面测试 priority_queue 以及实现 priority_queue 的 push 和 pop 时就使用了仿函数，因为，当我们想要让一组数升序排序或者降序排序时，我们不可能说去实现两个 priority_queue 的类，一个默认建大堆，降序排序；一个默认建小堆，升序排序。所以，C++ 引入了仿函数的概念，在实现类模板时，可以将仿函数作为模板参数，这样在我们使用时调用对应的仿函数，就能达到我们想要的效果。
仿函数（Functor）：也称为函数对象（Function Object），是一种在 C++ 中通过类或结构体实现的可调用实体，其实就是一个类。
仿函数的核心特点是 重载了 operator() 运算符，使得类的对象可以像普通函数一样被调用。 仿函数是 C++ 中'以类模拟函数'的重要机制，这种机制结合了面向对象的封装性和函数的灵活性，在 STL 和算法中有着广泛应用。
仿函数的核心特点：
- 重载 operator()
使用：
Add add; // 创建仿函数对象
int result = add(2, 3); // 像函数一样调用，结果为 5
通过在类中定义 operator() 运算符，使得该类的对象可以像函数一样被调用：
class Add {
public:
int operator()(int a, int b) // 重载 () 运算符
{
return a + b;
}
};
让冒泡排序既可以升序又可以降序排序：
#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 ((a[j], a[j - ]))
{
(a[j - ], a[j]);
flag = ;
}
(flag)
;
}
}
}
{
Less<> less;
Greater<> greater;
a[] = {, , , , , , , , };
n = (a) / (a[]);
(a, n, less);
( i = ; i < n; i++) {
cout << a[i] << ;
}
cout << endl;
(a, n, greater);
( i = ; i < n; i++) {
cout << a[i] << ;
}
cout << endl;
(a, n, <>());
( i = ; i < n; i++) {
cout << a[i] << ;
}
cout << endl;
(a, n, <>());
( i = ; i < n; i++) {
cout << a[i] << ;
}
cout << endl;
;
}
#include <iostream>
#include <vector>
#include <list>
#include <deque>
using namespace std;
namespace hds {
template<class T, class Container = deque<T>>
class stack {
public:
stack() {}
// 获取有效数据个数
size_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 <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() {}
// 获取有效数据个数
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.(x); }
{ _con.(); }
{ _con.(); }
:
Container _con;
};
}
#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 () { _con.(); }
{ _con.(); }
{
Compare com;
parent = (child - ) / ;
(child > ) {
((_con[parent], _con[child])) {
(_con[parent], _con[child]);
child = parent;
parent = (child - ) / ;
}
;
}
}
{
_con.(x);
(_con.() - );
}
{
Compare com;
child = * parent + ;
(child < _con.()) {
((child + ) < _con.() && (_con[child], _con[child + ])) {
child++;
}
((_con[parent], _con[child])) {
(_con[parent], _con[child]);
parent = child;
child = * parent + ;
}
;
}
}
{
(_con[], _con[_con.() - ]);
_con.();
();
}
{ _con.(); }
:
Container _con;
};
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online