代码仓库shanchuann/CPP-Learninng

容器适配器是 C++标准模板库（ STL ）中的接口封装型容器组件，并非具备独立存储结构的底层容器，其核心机制是依托 deque 、 vector 、 list 等基础序列容器作为底层存储载体，通过封装与约束底层容器的开放接口，实现栈、队列、优先队列三类经典数据结构的专属存取逻辑，屏蔽底层容器的复杂实现细节，仅对外提供适配特定应用场景的标准化操作接口。该类组件聚焦固定存取规则的场景化应用，使用者无需关注底层容器的实现原理，仅需调用封装后的接口即可完成数据操作，具备较高的易用性与场景针对性。

STL 标准库提供三类标准化容器适配器，分别对应不同的存取约束规则： stack 适配后进先出（ Last In First Out, LIFO ）的栈结构， queue 适配先进先出（ First In First Out, FIFO ）的普通队列结构， priority_queue 适配基于优先级排序的优先队列结构。三类适配器均不具备独立数据存储能力，完全依赖底层序列容器完成数据的实际存储，自身仅承担存取规则约束与接口封装的功能。

栈（ stack ）

stack 是遵循后进先出（ LIFO ）存取规则的容器适配器，数据元素仅允许从容器的单一端口完成入栈与出栈操作，最后入栈的元素将优先完成出栈，该适配器不支持随机访问、中间插入与中间删除等非栈式操作，仅开放栈顶元素的操作权限，接口设计简洁且规则严谨，适用于需逆序处理或临时缓存的应用场景。

底层实现逻辑

stack 作为容器适配器，不实现独立的存储逻辑，其底层存储完全依托第三方序列容器完成，标准库默认选用 std::deque 作为底层存储载体，使用者亦可手动指定 std::vector 或 std::list 作为底层容器，前提是底层容器需支持 push_back 、 pop_back 、 back 等基础尾部操作接口。该适配器通过封装底层容器的对应接口，实现栈结构的专属操作约束，其标准模板定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<class _Ty,class _C=deque<_Ty>> 
class stack {
public:
    typedef _C::size_type size_type;
    typedef _C::value_type value_type;
    // 判断栈是否为空
    bool empty() const { return c.empty(); }
    // 获取栈内元素数量
    size_type size() const { return c.size(); }
    // 获取栈顶元素
    value_type& top() { return c.back(); }
    const value_type& top() const { return c.back(); }
    // 压入元素
    void push(const value_type& _x) { c.push_back(_x); }
    // 弹出栈顶元素
    void pop() { c.pop_back(); }
protected:
    // 底层容器对象
    _C c;
};

性能特点

stack 的时间复杂度与空间复杂度完全由底层容器的实现机理决定，适配器自身无任何额外计算开销与内存开销，属于纯接口封装的零损耗适配，以下从均摊时间复杂度、最坏时间复杂度、空间复杂度三维度做学术化细化分析，同时对比不同底层容器的复杂度差异：

  1. 时间复杂度细分： stack 核心操作包括 empty()、 size()、 top()、 push()、 pop()，均直接调用底层容器对应接口，无二次遍历或计算。

  2. 默认底层容器 std::deque ： deque 采用分块连续内存结构，无整体扩容机制，尾部插入（ push_back ）、尾部删除（ pop_back ）、尾部访问（ back ）操作的平均时间复杂度与最坏时间复杂度均为常数阶 O(1)，无例外场景，属于严格 O(1)操作； empty()与 size()为成员变量读取操作，时间复杂度恒为 O(1)。

  3. 底层容器为 std::vector ： vector 为连续内存数组， push()操作对应 vector 的 push_back ，其均摊时间复杂度为 O(1)，最坏时间复杂度为 O(n)，最坏场景触发于内存容量不足时的整体扩容，需完成原有 n 个元素的批量内存迁移； pop()操作对应 pop_back ，无内存迁移，时间复杂度恒为 O(1)； top()为尾部随机访问，时间复杂度 O(1)。

  4. 底层容器为 std::list ： list 为双向链表， push_back 、 pop_back 、 back 操作均为链表节点的指针调整，无内存扩容与元素迁移，平均与最坏时间复杂度均为 O(1)，但链表节点离散存储， CPU 缓存局部性差，实际运行效率低于 deque 与 vector 。

  5. 空间复杂度： stack 的空间复杂度为线性阶 O(n)， n 为栈内有效元素数量，空间占用完全等价于底层容器的存储开销，适配器自身仅存储底层容器实例，无额外辅助空间，空间利用率由底层容器决定， deque 与 vector 的空间利用率较高， list 因节点指针开销存在少量空间冗余。

大小与容量说明

stack 的大小（ size ）表征当前适配器内存储的有效元素总量，可通过 size()接口直接获取；容量（ capacity ）指代底层容器在不触发内存重分配的前提下可容纳的最大元素数量， stack 未对外开放容量查询接口，工程实践中亦不建议直接访问底层容器获取容量参数，避免破坏适配器的封装性。 stack 的内存管理由底层容器自动完成，元素数量增加时底层容器自动扩容，元素数量减少时按需释放闲置内存，无需使用者手动干预内存分配与回收。

使用规范与注意事项

stack 的接口设计遵循严格的栈操作规范，使用过程中需遵守特定约束，其中禁止引用绑定栈顶元素是易被忽视的关键规范。弹栈操作（ pop ）会直接销毁栈顶元素，若提前通过引用绑定栈顶元素，弹栈后该引用将变为悬空引用，后续访问会触发内存访问异常；当存储元素为自定义类型时，该问题还可能引发内存泄漏等资源管理风险，需重点规避。

基础使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <stack>
#include <vector>
#include <list>
using namespace std;

int main() {
    // 默认底层容器：deque
    stack<int> sta_deque;
    // 指定底层容器为vector
    stack<int, vector<int>> sta_vec;
    // 指定底层容器为list
    stack<int, list<int>> sta_list;

    // 压入元素
    sta_deque.push(12);
    sta_deque.push(23);
    sta_deque.push(34);

    // 遍历栈（只能依次弹栈获取）
    while (!sta_deque.empty()) {
        // 获取栈顶元素
        int val = sta_deque.top();
        cout << val << " ";
        // 弹出栈顶元素
        sta_deque.pop();
    }
    return 0;
}

适用场景

stack 的应用场景严格契合后进先出的存取逻辑，典型应用场景包括：函数调用栈与递归过程模拟、算术表达式求值与括号匹配校验、深度优先搜索（ DFS ）算法实现、文本编辑器撤销与重做功能、编译器语法分析模块、 UI 界面导航历史记录管理、游戏状态回溯以及汉诺塔、二叉树非递归遍历等经典算法场景。

队列（ queue ）

queue 是遵循先进先出（ FIFO ）存取规则的容器适配器，数据元素从队列尾部完成入队操作，从队列头部完成出队操作，先入队的元素将优先完成出队，该适配器不支持随机访问与中间元素操作，仅开放队首与队尾元素的操作权限，适用于需顺序处理、公平调度的应用场景。

底层实现逻辑

queue 同属接口封装型容器适配器，标准库默认选用 std::deque 作为底层存储载体，亦可指定 std::list 作为底层容器，但不支持 std::vector 作为底层容器，原因在于 vector 未提供 pop_front 接口，头部删除操作的时间复杂度为线性阶 O(n)，无法满足队列高效操作的核心需求。该适配器通过封装底层容器的头尾操作接口，实现先进先出的规则约束，核心接口围绕队首与队尾操作设计。

性能特点

queue 的复杂度分析逻辑与 stack 同源，核心差异在于队列操作涉及头部删除与尾部插入，结合底层容器的接口特性，做学术化复杂度细分，同时明确 vector 不适用的复杂度核心原因：

  1. 时间复杂度细分： queue 核心操作包括 empty()、 size()、 front()、 back()、 push()、 pop()， push()对应底层容器尾部插入， pop()对应底层容器头部删除。

（ 1 ）默认底层容器 std::deque ： deque 支持头部与尾部的常数阶操作， push()（ push_back ）、 pop()（ pop_front ）、 front()、 back()的平均与最坏时间复杂度均为 O(1)，无扩容开销，无元素迁移，是队列的最优底层载体。

（ 2 ）底层容器为 std::list ： list 的 push_back 与 pop_front 均为指针调整操作，平均与最坏时间复杂度均为 O(1)，但同样存在缓存局部性差的问题，实际效率劣于 deque 。

（ 3 ） vector 禁用原因： vector 无原生 pop_front 接口，若模拟头部删除，需将后续 n-1 个元素整体前移，时间复杂度为线性阶 O(n)，无法满足队列高效操作的复杂度要求，因此标准库禁止 vector 作为 queue 底层容器。

  1. 空间复杂度： queue 的空间复杂度为线性阶 O(n)， n 为队列有效元素数量，无额外辅助空间开销，空间利用率与底层容器完全一致， deque 空间利用率最优， list 次之。

使用规范与注意事项

与 stack 的使用规范一致， queue 禁止通过引用绑定队首元素，出队操作会销毁队首元素，提前绑定的引用将转化为悬空引用，后续访问会触发内存访问异常，存储自定义类型元素时，该问题引发的程序崩溃风险更为显著，需严格遵守该使用规范。

基础使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <queue>
#include <list>
using namespace std;

int main() {
    // 默认底层容器：deque
    queue<int> que_deque;
    // 指定底层容器为list
    queue<int, list<int>> que_list;

    // 入队操作
    que_deque.push(10);
    que_deque.push(20);
    que_deque.push(30);

    // 遍历队列
    while (!que_deque.empty()) {
        // 获取队首元素
        int val = que_deque.front();
        cout << val << " ";
        // 出队操作
        que_deque.pop();
    }
    return 0;
}

适用场景

queue 适用于需顺序执行、公平调度的场景，典型应用包括：基础消息队列、任务顺序调度模块、广度优先搜索（ BFS ）算法实现、多线程数据交互缓冲区、事件驱动系统的事件队列、数据缓存与流式处理、任务排队等待机制等。

优先队列（ priority_queue ）

priority_queue 是具备优先级调度能力的特殊队列适配器，突破了普通队列先进先出的存取规则，元素出队顺序由自身优先级决定，优先级较高的元素优先出队。标准库默认构建大顶堆结构，数值较大的元素优先级更高，使用者可通过自定义比较函数将其调整为小顶堆，适用于需按优先级分级处理的应用场景。

底层实现逻辑

priority_queue 底层基于堆（ heap ）数据结构实现，标准库默认选用 std::vector 作为底层存储载体，堆属于完全二叉树结构，大顶堆满足父节点数值大于等于子节点的堆序性，堆顶位置始终存储优先级最高的元素。该适配器模板支持自定义比较函数，默认采用 std::less 实现大顶堆，替换为 std::greater 即可构建小顶堆，核心操作依托堆的上浮与下沉调整实现，保障堆序性的持续稳定，其标准模板定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class _Ty,class _Container=vector<_Ty>,class _Pr=less<typename _Container::value_type>>
class priority_queue {
public:
    typedef _Container::size_type size_type;
    typedef _Container::value_type value_type;

    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    // 获取堆顶（优先级最高）元素
    const value_type& top() const { return c.front(); }
    // 入队并调整堆结构
    void push(const value_type& _val) {
        c.push_back(_val);
        push_heap(c.begin(), c.end(), comp);
    }
    // 堆顶出队，调整堆结构
    void pop() {
        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }
protected:
    _Container c;
    _Pr comp;
};

堆结构与操作原理

优先队列基于完全二叉堆实现，堆的结构特性是复杂度分析的核心学术依据，完全二叉堆可通过数组顺序存储，无需额外指针开销，且满足堆序性（大顶堆：父节点值≥子节点值；小顶堆：父节点值≤子节点值），堆顶始终为优先级极值元素。以下结合堆的结构特性，做复杂度数学推导与操作机理细化：

  1. 完全二叉堆的高度推导：对于包含 n 个元素的完全二叉堆，其树高 h 满足数学关系：$$h = \lfloor \log_2 n \rfloor + 1$$，树高与元素数量呈对数关系，这是堆操作复杂度为 O(logn)的核心数学基础。
  2. 插入操作（ push ）与上浮（ sift up ）机理：元素插入时，先将元素置于数组尾部（对应完全二叉堆的最后一个叶子节点），随后执行上浮调整：从当前节点出发，逐层与父节点比较，若违反堆序性则交换节点位置，直至满足堆序性或到达堆顶。上浮操作的逐层比较次数等价于堆的高度 h ，因此时间复杂度为 O(logn)，无最坏场景退化，全程为对数阶。
  3. 堆顶删除操作（ pop ）与下沉（ sift down ）机理：堆顶元素删除时，先将堆顶与数组尾部元素交换，删除尾部元素（原堆顶），随后对新堆顶执行下沉调整：从堆顶出发，逐层与子节点比较，选择极值子节点交换位置，直至满足堆序性。下沉操作的比较次数同样等价于堆高 h ，时间复杂度恒为 O(logn)。
  4. 堆顶访问（ top ）机理：堆顶元素对应数组首元素，为直接随机访问，时间复杂度恒为 O(1)，无任何计算开销。

性能分析

priority_queue 的复杂度分析需结合时间复杂度（平均/最坏）、空间复杂度、辅助空间开销做学术化完整界定，同时区分底层容器与堆操作的复合开销：

  1. 时间复杂度细分：

  2. 查询操作： empty()、 size()、 top()均为底层 vector 成员读取或首元素访问，时间复杂度恒为 O(1)；

  3. 插入操作（ push ）：复合 vector 的 push_back 与堆上浮操作， vector push_back均摊 O(1)，堆上浮O(logn)，整体操作的均摊与最坏时间复杂度均为 O(logn)，对数阶开销由堆调整主导；

  4. 删除操作（ pop ）：复合堆下沉与 vector pop_back ，堆下沉O(logn)， vector pop_backO(1)，整体时间复杂度恒为 O(logn)；

  5. 无中间访问与遍历操作，符合优先队列的接口约束。

  6. 空间复杂度： priority_queue 的空间复杂度为 O(n)， n 为队列有效元素数量，底层 vector 存储所有元素，堆操作仅使用常数阶 O(1)辅助空间（临时交换变量），无额外递归栈或动态数组开销，空间利用率极高，属于原地堆调整（ in-place heapify ）。

  7. 复杂度对比与工程意义：相较于普通队列的 O(1)操作，优先队列以对数阶开销换取优先级调度能力，在海量数据场景下， logn 的增长速率远低于线性阶，仍具备优异的性能表现，是优先级调度场景的最优复杂度方案。

基础使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // 默认大顶堆，数值大的优先出队
    priority_queue<int> pri_que;
    // 插入随机数据
    pri_que.push(56);
    pri_que.push(23);
    pri_que.push(78);
    pri_que.push(12);

    // 按优先级遍历
    while (!pri_que.empty()) {
        int val = pri_que.top();
        cout << val << " ";
        pri_que.pop();
    }
    cout << endl;

    // 自定义小顶堆，数值小的优先出队
    priority_queue<int, vector<int>, greater<int>> small_heap;
    small_heap.push(56);
    small_heap.push(23);
    small_heap.push(78);
    small_heap.push(12);
    while (!small_heap.empty()) {
        int val = small_heap.top();
        cout << val << " ";
        small_heap.pop();
    }
    return 0;
}

适用场景

priority_queue 适用于优先级调度场景，典型应用包括：任务优先级调度模块、操作系统进程调度、图论最短路径算法（ Dijkstra ）、事件优先级处理、数据 TopN 问题求解、批量数据排序等场景。

三类容器适配器的工程应用需遵循统一规范，规避内存异常与性能损耗问题：其一，自定义类型作为存储元素时，需保证拷贝构造函数、析构函数逻辑严谨，妥善管理动态内存，避免资源泄漏；其二，大型自定义元素频繁拷贝会降低运行效率，建议采用智能指针替代直接值存储；其三，适配器接口仅开放特定操作权限，禁止执行中间元素修改、删除等违规操作，避免破坏数据结构规则；其四，优先队列自定义优先级时，需保证比较函数逻辑合规，防止堆序性紊乱导致调度失效。

容器适配器是 C++ STL 中针对特定存取场景设计的轻量化接口封装组件，通过依托基础序列容器实现经典数据结构的专属逻辑，具备易用性高、规则清晰、场景针对性强的特点。 stack 适配后进先出的逆序操作场景， queue 适配先进先出的顺序处理场景， priority_queue 适配优先级调度场景，三类适配器的性能均由底层容器决定，接口设计符合数据结构的标准规范。工程实践中，可根据业务存取规则选择适配的容器组件，无需关注底层实现细节，即可高效完成数据操作，同时严格遵守使用规范，规避悬空引用、内存泄漏等常见问题，保障程序的稳定性与高效性。