C++算法
C++ STL 容器适配器详解：stack、queue 与 priority_queue 原理
C++ 容器适配器基于现有容器实现，隐藏底层细节。主要包括 stack、queue 和 priority_queue。stack 默认用 deque，支持 LIFO；queue 默认用 deque，支持 FIFO；priority_queue 默认用 vector 配合堆算法维护优先级。文章通过源码模拟展示了其接口实现及仿函数在自定义排序中的应用。
C++ 容器适配器基于现有容器实现，隐藏底层细节。主要包括 stack、queue 和 priority_queue。stack 默认用 deque，支持 LIFO；queue 默认用 deque，支持 FIFO；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...），像插入删除执行操作，其实是由底层的容器实现，所以，我们只需要运用底层容器的函数接口。**同样我们创建一个自己的命名空间，在自己的命名空间中写代码
文档：栈（stack）
// 将 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(); }
文档：队列（queue）
// 将 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(); }
const 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）来自动完成此操作。
相关接口：
插入 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>, Greater<int>> pq; // Greater：建小堆
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 Greater {
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(); }
:
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() {}
// 获取有效数据个数
const size_t size()const { return _con.size(); }
// 获取队头数据
const T& front()const { return _con.front(); }
// 获取队尾数据
const T& back()const { return _con.back(); }
// 再队尾插入数据（先进先出）
void push { _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 Greater {
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:
() { _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