吃透C++ STL四大容器：Vector、List、Stack、Queue核心原理与实战用法

API	功能描述	时间复杂度
push_back(elem)	尾部插入元素	O(1)（无扩容）/ O(n)（扩容）
pop_back()	删除尾部元素	O(1)
insert(pos, elem)	指定位置插入元素	O(n)（元素后移）
erase(pos)	删除指定位置元素	O(n)（元素前移）
size()	获取实际元素个数	O(1)
capacity()	获取容器总容量	O(1)
empty()	判断容器是否为空	O(1)
clear()	清空所有元素（不释放内存）	O(n)
[] / at()	下标随机访问元素	O(1)

2.5 实战代码示例

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 1. 初始化vector
    vector<int> vec;
    vector<int> vec2(3, 10); // 3个元素，初始值10

    // 2. 尾部插入
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    // 3. 随机访问
    cout << "下标访问：" << vec[0] << endl;

    // 4. 指定位置插入
    vec.insert(vec.begin() + 1, 99);

    // 5. 删除元素
    vec.pop_back(); // 删除尾部
    vec.erase(vec.begin()); // 删除头部

    // 6. 遍历
    for (int x : vec) {
        cout << x << " ";
    }
    cout << endl;

    // 7. 容量与大小
    cout << "元素个数size：" << vec.size() << endl;
    cout << "容器容量capacity：" << vec.capacity() << endl;

    return 0;
}

2.6 优缺点与适用场景

优点：

内存连续，缓存命中率高，访问速度极快
支持随机访问，下标查询效率O(1)
尾部增删效率极高（无扩容时）

缺点：

头部/中间插入、删除效率低，需要移动大量元素
扩容会产生内存拷贝，损耗性能
存在内存冗余（capacity > size）

适用场景：频繁查询、尾部增删，极少中间/头部修改的场景（数据列表、数组存储、遍历统计）。

三、List 双向链表

3.1 核心概念

List 是STL双向循环链表，底层内存离散不连续，每个元素是独立节点，节点存储「数据+前驱指针+后继指针」，通过指针串联所有节点。

List 同样是序列容器，元素有序可重复，不支持随机访问，仅支持前后双向遍历。

3.2 底层存储结构

每个list节点结构：

struct Node {
    T data;       // 存储数据
    Node* prev;   // 指向前一个节点
    Node* next;   // 指向后一个节点
};

所有节点分散在内存各处，无需连续空间，通过指针关联，天然无内存冗余，也无需扩容。

3.3 核心特性与执行流程

增删原理：插入/删除节点时，仅需修改相邻节点的指针指向，无需移动任何元素，这是list最大的性能优势。

3.4 常用API大全

API	功能描述	时间复杂度
push_back()/push_front()	尾部/头部插入元素	O(1)
pop_back()/pop_front()	尾部/头部删除元素	O(1)
insert(pos, elem)	指定位置插入	O(1)（已知迭代器位置）
erase(pos)	删除指定位置元素	O(1)（已知迭代器位置）
size()/empty()/clear()	基础属性操作	O(1)/O(1)/O(n)
sort()	链表专属排序（优化版）	O(nlogn)
reverse()	反转链表	O(n)

3.5 实战代码示例

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst;

    // 头尾插入
    lst.push_back(10);
    lst.push_front(20);
    lst.push_back(30);

    // 指定位置插入
    auto it = lst.begin();
    it++;
    lst.insert(it, 99);

    // 删除元素
    lst.pop_front();
    lst.erase(it);

    // 遍历（仅支持迭代器遍历，不支持下标）
    for (int x : lst) {
        cout << x << " ";
    }
    cout << endl;

    // 排序、反转
    lst.sort();
    lst.reverse();

    return 0;
}

3.6 优缺点与适用场景

优点：

任意位置增删元素效率极高（O(1)），无需移动数据
无内存冗余，按需分配节点内存
迭代器增删后不失效（仅删除节点迭代器失效）

缺点：

不支持随机访问，查询指定位置元素需遍历（O(n)）
内存离散，缓存命中率低，遍历速度慢于vector
每个节点额外存储指针，内存开销大

适用场景：频繁在任意位置增删元素、极少随机查询的场景（任务链表、动态节点管理）。

四、Stack 栈（容器适配器）

4.1 核心概念

Stack 是后进先出（LIFO, Last In First Out）的容器适配器，无独立底层内存，默认基于 deque 实现，也可手动指定 vector/list 作为底层容器。

栈的核心规则：仅允许在栈顶插入、删除、访问元素，栈底完全封闭，不支持中间操作、遍历、随机访问。

4.2 执行流程（LIFO规则）

4.3 常用API大全

API	功能描述	时间复杂度
push(elem)	栈顶插入元素（入栈）	O(1)
pop()	删除栈顶元素（出栈，无返回值）	O(1)
top()	获取栈顶元素（不删除）	O(1)
empty()	判断栈是否为空	O(1)
size()	获取栈中元素个数	O(1)

4.4 实战代码示例

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> st;

    // 入栈
    st.push(1);
    st.push(2);
    st.push(3);

    // 循环出栈
    while (!st.empty()) {
        cout << "栈顶元素：" << st.top() << endl;
        st.pop(); // 弹出栈顶
    }

    return 0;
}

输出结果：3 → 2 → 1，完美印证后进先出规则。

4.5 适用场景

函数递归调用、程序方法调用栈
表达式求值、括号匹配、进制转换
撤销/回退操作（编辑器撤销、浏览器回退）

五、Queue 队列（容器适配器）

5.1 核心概念

Queue 是先进先出（FIFO, First In First Out）的容器适配器，默认基于 deque 实现，无独立底层存储。

队列核心规则：队尾入队、队头出队，仅能访问队头、队尾元素，不支持中间操作、随机访问、遍历。

5.2 执行流程（FIFO规则）

5.3 常用API大全

API	功能描述	时间复杂度
push(elem)	队尾插入元素（入队）	O(1)
pop()	删除队头元素（出队，无返回值）	O(1)
front()	获取队头元素	O(1)
back()	获取队尾元素	O(1)
empty()/size()	判空、获取元素个数	O(1)

5.4 实战代码示例

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;

    // 入队
    q.push(1);
    q.push(2);
    q.push(3);

    // 循环出队
    while (!q.empty()) {
        cout << "队头元素：" << q.front() << endl;
        q.pop();
    }

    return 0;
}

输出结果：1 → 2 → 3，符合先进先出规则。

5.5 适用场景

任务排队、消息队列、线程池任务调度
广度优先搜索（BFS）算法
缓冲区数据处理、请求排队机制

六、四大容器终极对比（面试必背）

容器	存储结构	访问特性	增删效率	核心规则	适用场景
Vector	连续动态数组	支持随机访问，遍历快	尾插快，头尾插删慢	有序可重复	多查询、少中间修改
List	离散双向链表	不支持随机访问，遍历慢	任意位置增删极快	有序可重复	多增删、少查询
Stack	容器适配器（默认deque）	仅访问栈顶	栈顶增删O(1)	后进先出LIFO	回溯、撤销、递归
Queue	容器适配器（默认deque）	仅访问头尾	头尾增删O(1)	先进先出FIFO	任务排队、BFS

七、高频面试总结

vector和list的核心区别：内存连续vs离散、支持随机访问vs不支持、查询快增删慢vs增删快查询慢、有内存冗余vs无冗余。
stack/queue为什么是适配器：无独立底层结构，依赖其他容器实现功能，仅封装专属操作规则。
vector迭代器失效场景：扩容、中间插入/删除元素，list仅删除节点迭代器失效。
使用优先级：默认优先用vector，频繁中间增删用list，栈逻辑用stack，排队逻辑用queue。

八、总结

1. Vector：动态数组，内存连续，查询遍历王者，适合静态数据存储；

2. List：双向链表，内存离散，增删操作王者，适合动态频繁修改的数据；

3. Stack：LIFO后进先出，单向栈顶操作，用于回溯、递归、撤销场景；

4. Queue：FIFO先进先出，头尾操作，用于排队、任务调度、广度搜索。

https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

ChatGPT Plus续费前先查这4项：账号、套餐、日期和扣款渠道

AI编程社区

保姆级！CodeX 与 CodeX CLI / IDE客户端安装及环境搭建 | 纯小白指南

进入->Plugins-> 搜索。安装完成后，在Tools->中：设置为。填入私有安全网关地址。勾选(开启多文件全局符号关联解析)。在 AI 范式深度演化与 Vibe Coding 普遍落地的当下，掌握 CodeX 的全套安装、配置、沙箱隔离与流水线自动化构建，是每一位极客开发者迈向智能化研发的必备功课。先搞定底层 Python/TypeScript SDK，确保 API 接入与代理链路畅通；全面