[C++] 容器适配器：深入理解Stack与Queue的底层原理

容器适配器简介

适配器（Adapter）是一种设计模式，其主要作用是将一个类的接口转换为另一个客户希望的接口。在STL（Standard Template Library）中，适配器用来封装底层容器，提供特定的接口和行为。这种封装可以使得不同的底层容器在接口上保持一致，从而简化代码的使用和维护。

本文所涉及的stack、queue和priority_queue都是容器适配器，在底层都可以通过在接口传入的容器类型来进行底层的容器实现。

以上官方接口图示中，Container就是适配器初始化时容器类型的指定，Compare是仿函数，也可以实现相关的适配。

deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

为什么使用deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的
   元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。

关于deque的详细讲解：
[C++] vector对比list & deque的引出-CSDN博客

stack和queue的简单讲解

Stack（栈）

栈的操作图示

栈的相关接口

栈是一种后进先出（LIFO, Last In First Out）的数据结构，通常用于存储临时数据或实现递归。其基本操作包括：

接口函数	说明
push(x)	将元素x压入栈顶
pop()	移除并返回栈顶元素
top()	返回栈顶元素
empty()	判断栈是否为空
size()	返回栈中元素个数

Queue（队列）

队列是一种先进先出（FIFO, First In First Out）的数据结构，适用于需要顺序处理数据的场景。其基本操作包括：

接口函数	说明
push(x)	将元素x加入队尾
pop()	移除并返回队头元素
front()	返回队头元素
back()	返回队尾元素
empty()	判断队列是否为空
size()	返回队列中元素个数

Stack和Queue的模拟实现

Stack（栈）

作为容器适配器的特性

1. 后进先出（LIFO）：栈是一种遵循 LIFO 原则的数据结构，这意味着最后被添加到栈中的元素将是第一个被移除的元素。
2. 受限的接口：与完整的容器不同，栈的接口限制了用户只能通过栈顶进行操作，不允许直接访问栈中的其他元素。
3. 主要操作：
   • push：向栈顶添加一个元素。
   • pop：移除栈顶的元素。
   • top：访问栈顶的元素（不移除它）。
4. 空栈检查：可以检查栈是否为空，以便在尝试访问或移除元素之前确保栈不为空。
5. 大小限制：可以查询栈中元素的数量，但不允许直接通过索引访问元素。
6. 迭代器：虽然栈的迭代器功能有限，但栈仍然提供了迭代器，允许遍历栈中的元素，尽管只能从栈顶开始。
7. 异常中立性：栈的操作（如 push 和 pop）保证不抛出异常，除非是底层容器的操作抛出异常。
8. 底层容器：栈通常使用 deque 或 vector 作为底层容器来存储元素。选择哪种容器取决于具体的实现和性能要求。
9. 模板类：栈是一个模板类，可以存储任意类型的元素。
10. 不提供排序：栈不提供元素排序功能，它只提供了基本的 LIFO 操作。
11. 不提供元素删除：除了 pop 操作外，栈不提供从栈中删除任意位置元素的功能。
12. 不提供直接访问：不能直接访问或修改栈中的元素，除了栈顶元素。

模拟实现

template<class T, class Container = std::deque<T>>
class stack {
public:// 向栈顶添加一个元素void push(const T& x) {_con.push_back(x); // 使用底层容器的 push_back 方法}// 移除栈顶元素void pop() {if (empty()) {throw std::out_of_range("Stack<>::pop: empty stack");}_con.pop_back(); // 使用底层容器的 pop_back 方法}// 获取栈顶元素的引用const T& top() const {if (empty()) {throw std::out_of_range("Stack<>::top: empty stack");}return _con.back(); // 使用底层容器的 back 方法}// 获取栈中元素的数量size_t size() const {return _con.size();}// 检查栈是否为空bool empty() const {return _con.empty();}private:Container _con; // 底层容器
};

Queue（队列）

作为容器适配器的特性

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
   1. empty：检测队列是否为空
   2. size：返回队列中有效元素的个数
   3. front：返回队头元素的引用
   4. back：返回队尾元素的引用
   5. push_back：在队列尾部入队列
   6. pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器
   类，则使用标准容器deque

模拟实现

template<class T, class Container = std::deque<T>>
class queue {
public:// 向队列尾部添加一个元素void push(const T& x) {_con.push_back(x); // 使用底层容器的 push_back 方法}// 移除队列头部的元素void pop() {if (empty()) {throw std::out_of_range("Queue<>::pop: empty queue");}_con.pop_front(); // 使用底层容器的 pop_front 方法}// 获取队列头部元素的引用const T& front() const {if (empty()) {throw std::out_of_range("Queue<>::front: empty queue");}return _con.front(); // 使用底层容器的 front 方法}// 获取队列尾部元素的引用const T& back() const {if (empty()) {throw std::out_of_range("Queue<>::back: empty queue");}return _con.back(); // 使用底层容器的 back 方法}// 获取队列中元素的数量size_t size() const {return _con.size();}// 检查队列是否为空bool empty() const {return _con.empty();}private:Container _con; // 底层容器，默认为 deque
};

PriorityQueue（优先级队列）

优先级队列是一种特殊的队列，元素按照优先级排列。其基本操作类似于堆，主要用于调度算法、路径搜索等需要频繁获取最高优先级元素的场景。

优先级队列的特性

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
   1. empty()：检测容器是否为空
   2. size()：返回容器中有效元素个数
   3. front()：返回容器中第一个元素的引用
   4. push_back()：在容器尾部插入元素
   5. pop_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue
   类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用
   算法函数make_heap、push_heap和pop_heap来自动完成此操作。

priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使priority_queue。

注意：默认情况下priority_queue是大堆。

常用接口

接口函数	说明
push(x)	插入元素x
pop()	移除并返回最大（或最小）元素
top()	返回最大（或最小）元素但不移除
empty()	判断队列是否为空
size()	返回队列中元素个数
emplace(x)	就地构造元素x并插入队列
swap(q)	交换当前优先级队列与q中的元素
std::less<T>	默认仿函数，构建最大堆
std::greater<T>	自定义仿函数，构建最小堆（需自定义仿函数参数）

传入自定义类型的注意事项

当你使用 std::priority_queue 时，它默认使用 < 运算符来确定元素之间的优先级关系，即默认情况下，较小的元素会被认为是具有较高优先级的。然而，std::priority_queue 也允许用户指定一个自定义的比较函数，这使得你可以定义自己的优先级规则。

所以：如果在priority_queue中放自定义类型的数据，需要在自定义类型中提供>或者< 的重载。

如果你要将自定义类型的对象放入 std::priority_queue 中，并且希望使用不同于默认的优先级规则（例如，你可能希望较大的元素具有较高的优先级），你需要提供一个自定义的比较函数。这个比较函数可以是：

• 一个函数对象（functor）。
• 一个普通的函数。
• 一个 lambda 表达式。

这就是仿函数的基本用法。当使用自定义类型时，传入std::greater<T>或std::less<T>会自动调用自定义类型重载的<和>来构建优先级队列。

使用自定义类型传入应用示例

class Date {
public:// 构造函数，初始化日期Date(int year = 1900, 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);}// 友元函数，重载输出流运算符，用于输出日期friend std::ostream& operator<<(std::ostream& os, const Date& d) {os << d._year << "-" << d._month << "-" << d._day;return os;}private:int _year;int _month;int _day;
};void TestPriorityQueue() {// 使用默认的 priority_queue 创建最大堆std::priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));std::cout << "Max heap top: " << q1.top() << std::endl;// 使用自定义比较对象 greater<Date> 创建最小堆std::priority_queue<Date, std::vector<Date>, std::greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));std::cout << "Min heap top: " << q2.top() << std::endl;
}int main() {TestPriorityQueue();return 0;
}

TestPriorityQueue 函数展示了如何使用 std::priority_queue 来创建最大堆和最小堆。最大堆 q1 使用 Date 类的 < 运算符来确定元素的优先级，而最小堆 q2 使用 std::greater<Date> 来实现，它将 Date 类型的 > 运算符作为比较函数。函数最后输出了两个堆的顶部元素。

priority_queue的模拟实现

template<class T>
class Less {
public:bool operator()(const T& x, const T& y) const { return x < y;}
};template<class T>
class Greater {
public:bool operator()(const T& x, const T& y) const { return x > y;}
};namespace bee {template<class T, class Container = std::vector<T>, class Compare = Less<T>>class priority_queue {public:void adjustUp(int child) {while (child > 0) {int parent = (child - 1) / 2;if (_compare(_con[child], _con[parent])) {std::swap(_con[child], _con[parent]);child = parent;} else {break;}}}void push(const T& x) {_con.push_back(x);adjustUp(static_cast<int>(_con.size()) - 1);}void adjustDown(int parent) {int child = parent * 2 + 1;while (child < _con.size()) {int right_child = child + 1;if (right_child < _con.size() && _compare(_con[child], _con[right_child])) {child = right_child;}if (_compare(_con[child], _con[parent])) {std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;} else {break;}}}void pop() {std::swap(_con[0], _con.back());_con.pop_back();adjustDown(0);}T top() const { // 添加 const 并移除 return 关键字return _con[0];}size_t size() const {return _con.size();}bool empty() const {return _con.empty();}private:Container _con;Compare _compare; // 存储比较函数对象};
}

在底层使用堆进行维护，符合了deque的逻辑。

deque的实际应用

struct Task {int priority;std::string name;// 重载运算符，用于比较任务的优先级（priority），越小优先级越高bool operator<(const Task& other) const {return priority > other.priority; // priority值越小优先级越高}
};int main() {std::priority_queue<Task> taskQueue;// 添加任务到队列taskQueue.push(Task{3, "Task A"});taskQueue.push(Task{1, "Task B"});taskQueue.push(Task{2, "Task C"});// 处理任务while (!taskQueue.empty()) {Task currentTask = taskQueue.top();std::cout << "Processing " << currentTask.name << " with priority " << currentTask.priority << std::endl;taskQueue.pop();}

在这个例子中，我们定义了一个Task结构体，每个任务有一个优先级和名称。我们使用std::priority_queue来管理这些任务，并通过重载operator<来定义任务的优先级比较规则。优先级最高的任务（priority值最小）会首先被处理。

仿函数（Functor）

什么是仿函数？

仿函数（Functor）是指实现了operator()的对象。在C++中，仿函数是一种能够像普通函数一样被调用的对象。它们通过重载函数调用运算符operator()来实现这一点，因此可以像函数一样使用。
通过重载operator()，仿函数可以模拟函数的行为，使得对象不仅可以保存状态，还可以执行操作。这种机制在C++中非常有用，特别是在STL（标准模板库）中，它允许用户自定义排序准则、筛选条件等。

仿函数的定义

仿函数是一个类或者结构体，通过重载operator()来实现。基本形式如下：

class Functor {
public:void operator()(/* 参数列表 */) {// 函数体}
};

仿函数的特性

状态保存

仿函数可以有成员变量，这允许它们在调用时保存状态。这是与普通函数的一个重要区别，因为普通函数没有状态。仿函数可以应用在需要保留上下文信息的场景。例如，计数器仿函数可以记录被调用的次数：

class Counter {
public:Counter() : count(0) {}void operator()() {++count;std::cout << "Called " << count << " times" << std::endl;}private:int count;
};int main() {Counter countCalls;countCalls(); // 输出 "Called 1 times"countCalls(); // 输出 "Called 2 times"return 0;
}

在这个例子中，Counter仿函数保存了调用次数，并在每次调用时输出当前的调用次数。

参数化

仿函数可以通过构造函数参数传递数据，使得调用operator()时可以使用这些数据进行操作，也就是在上文适配器中关于仿函数的使用方式。

灵活性

仿函数可以重载operator()来实现不同的功能，比如比较、操作等，提供了很大的灵活性。结合灵活性与参数化，可以灵活的控制相关容器的底层存储。

template<class T, class Container = std::vector<T>, class Compare = Less<T>>

通过传递仿函数，用户可以自定义优先级队列的元素排列规则

例如在上文实现优先级队列的模拟实现代码中，就使用的仿函数作为模板参数：

在priority_queue中，仿函数Compare决定了元素的优先级顺序。默认情况下，Less<T>会将较小的元素放在堆顶，形成最小堆。如果使用Greater<T>，则会形成最大堆。仿函数的灵活性允许用户根据需要自定义优先级队列的行为。仿函数的使用使得priority_queue能够支持多种排列规则，而不需要修改底层容器的实现。

仿函数的使用场景

• 排序：在STL算法（如std::sort）中，可以使用仿函数自定义排序准则。
• 筛选：在STL算法（如std::remove_if）中，可以使用仿函数定义筛选条件。
• 优先级队列：在std::priority_queue中，仿函数用于定义元素的优先级排序。
• 延迟计算：通过在仿函数中保存状态，用户可以实现延迟计算的逻辑。

具体的应用请通过上文优先级队列理解。