【C++】《三种容器适配器没你想的那么复杂：从 stack到queue再到 priority_queue，顺便聊聊仿函数》
一.stack 的介绍和使用
1.stack 的介绍
https://cplusplus.com/reference/stack/stack/?kw=stack#google_vignette
1.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 的尾部当作栈顶
template<class T, class Container = deque<T>>
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(); // 尾部删除 → 出栈
}
// 交换两个栈的内容（C++11）
void swap(stack<T, Container>& st)
{
std::swap(_con, st._con);
}
private:
Container _con; // 底层容器，所有操作都转发给它
};
void test()
{
// 可以用 vector 做底层容器
// stack<int, vector<int>> st;
// 可以用 list 做底层容器
// stack<int, list<int>> st;
// 默认用 deque 做底层容器
stack<int> 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 默认会使用 dequ
2.queue 的使用
queue 是没有迭代器的，因为有了迭代器就可以随意访问元素了，就无法保证先进先出的性质了。
3.queue的模拟实现
因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实现queue，具体如下：
#pragma once
#include <deque> // deque 是默认底层容器
#include <iostream>
using namespace std;
namespace hjq
{
// queue 容器适配器
// T：队列中存储的数据类型
// Container：底层容器类型，默认为 deque
// 特点：尾部当作队尾（入队），头部当作队头（出队）
template<class T, class Container = deque<T>>
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 做底层容器
// queue<int, list<int>> q;
// 默认用 deque 做底层容器
queue<int> 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()
{
// 默认情况下，创建的是大堆，其底层按照小于符号(<)比较
vector<int> v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5};
priority_queue<int> q1;
for (auto& e : v)
{
q1.push(e);
}
cout << q1.top() << endl;
// 如果要创建小堆，将第三个模板参数换成greater比较方式即可
priority_queue<int, vector<int>, greater<int>> 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_queue<Date> 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_queue<Date, vector<Date>, greater<Date>> 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_queue<Date, vector<Date>, 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
template<class T>
struct less
{
bool operator()(const T& left, const T& right)
{
return left < right;
}
};
// 仿函数 greater：用于建小堆
// 判断 left 是否大于 right
template<class T>
struct greater
{
bool operator()(const T& left, const T& right)
{
return left > right;
}
};
// priority_queue 类模板
// T：存储的数据类型
// Container：底层容器，默认 vector
// Compare：比较方式，默认 less（建大堆）
template<class T, class Container = vector<T>, class Compare = std::less<T>>
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_queue<int> 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;
// 小堆测试
vector<int> v{5, 1, 4, 2, 3, 6};
hjq::priority_queue<int, vector<int>, hjq::greater<int>> 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
template<class T>
struct Less
{
bool operator()(const T& x, const T& y)
{
return x < y; // 调用类型自身的 < 运算符
}
};
//大于比较仿函数
// 功能：判断 x 是否大于 y
template<class T>
struct Greater
{
bool operator()(const T& x, const T& y)
{
return x > y; // 调用类型自身的 > 运算符
}
};
void test_functor()
{
// 使用 Less 仿函数
Less<int> less; // 实例化对象
cout << less(1, 2) << endl; // 1 < 2 → true --> 输出 1
// 使用 Greater 仿函数
Greater<int> 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_function<T, 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_function<T, 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 = vector<T>,
class Compare = less<typename Container::value_type>> class priority_queue;
void test()
{
// 建小堆
priority_queue<int, vector<int>, greater<int>> pq; // 传仿函数greater<int>类型
}函数模板是隐式实例化，编译器根据实参推演模板参数，所以传的是对象。比如 sort：
// 第1个模板参数：迭代器的类型
// 第2个模板参数是：仿函数的类型
template <class RandomAccessIterator, class Compare>
// 函数的第1,2个参数是：迭代器对象
// 函数的第3个参数是：仿函数类的对象
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
void test()
{
vector<int> v { 5,3,2,4,1 };
// 排降序(>)
sort (v.begin(), b.end(), greater<int>()); // 传仿函数类greater<int>的匿名对象
for (const auto& x : v)
cout << x << " ";
cout << endl;
}给大家小结一下就是：类模板用类型造对象，函数模板拿对象推类型。给 priority_queue 的是类型 greater<int>，给 sort 的是对象 greater<int>()。
四.容器适配器
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和list，deque的应用并不多，而目前能看到的一个应用就是，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的优点，而完美的避开了其缺陷。
更多推荐
20
0- 0
已为社区贡献15条内容
所有评论(0)