经过这段时间的学习整理，大部分C++中常用到的语法点都通过文章做了基本的介绍。后续学习过程中如果碰到了新的知识点，会再继续补充

接下来一段时间我会把学习重点放在STL上，毕竟这个是C++标准库的核心，不管是日常开发还是面试时都是会必然碰到的，在这一块多花些功夫进行深入研究也是值得的

这次继之前的vector和array容器之后，再来学习一下list和forward_list这两个容器。如果想了解之前的内容，可以看看这篇文章

C++ STL入门：从array到vector，领略模版编程的优势https://mp.weixin.qq.com/s?__biz=MzE5ODI1NDEzNA==&mid=2247483807&idx=1&sn=db141d0fb421cdcb1ff203bf5207cb57&scene=21#wechat_redirect

list 容器：双向链表的 “全能选手”

list 容器的底层实现是双向链表，这意味着它的每个节点都包含三个部分：前驱节点的指针、节点存储的数据和后继节点的指针。就像一串首尾相连的珠子，我们既可以从第一个珠子依次摸到最后一个，也能从最后一个倒着摸回第一个。

这种结构带来了两个核心优势：

• 插入删除效率高

    在链表的任意位置插入或删除元素时，只需要修改相邻节点的指针，时间复杂度是 O (1)（前提是已经找到目标位置），不需要像 vector 那样移动大量元素。

• 内存不连续

      list 的元素在内存中是分散存储的，这意味着它不会像 vector 那样因为扩容导致内存浪费，也不会因为内存不足而频繁迁移数据。

但凡事有利有弊，list 的缺点也很明显：

• 随机访问效率低

    要访问第 n 个元素，必须从表头或表尾开始逐个遍历，时间复杂度是 O (n)，无法像 vector 那样通过下标直接访问。

• 内存开销大

      每个节点除了存储数据，还需要额外存储两个指针（前驱和后继），当存储的数据量很小时，指针的内存开销会显得比较突出。

list 的定义与初始化

在使用 list 之前，需要包含头文件<list>，并使用std命名空间（或显式指定std::list）。下面我们通过代码示例，看看 list 有哪些常见的初始化方式。

方式 1：默认初始化，创建空 list

#include <list>#include <iostream>int main(){    std::list<int> lst;  // 创建一个存储int类型的空list    std::cout << "空list的大小：" << lst.size() << std::endl;  // 输出0    return 0;}

方式 2：指定元素个数和初始值

int main(){    std::list<int> lst(5, 10);  // 创建包含5个int元素的list，每个元素值都是10    for (auto it = lst.begin(); it != lst.end(); ++it)    {        std::cout << *it << " ";  // 输出：10 10 10 10 10    }    std::cout << std::endl;    return 0;}

方式 3：通过迭代器范围初始化（拷贝其他容器的元素）

#include <vector>int main(){    std::vector<int> vec = {1, 2, 3, 4, 5};    std::list<int> lst(vec.begin(), vec.end());  // 拷贝vector的[begin(), end())范围元素到list    for (auto num : lst)    {        std::cout << num << " ";  // 输出：1 2 3 4 5    }    std::cout << std::endl;    return 0;}

方式 4：使用初始化列表直接赋值（C++11 及以后支持）

int main(){    std::list<int> lst = {10, 20, 30, 40};  // =可省略    for (auto num : lst)    {        std::cout << num << " ";  // 输出：10 20 30 40    }    std::cout << std::endl;    return 0;}

方式 5：拷贝构造，创建已有 list 的副本

int main(){    std::list<int> lst1 = {1, 2, 3};    std::list<int> lst2(lst1);  // 拷贝lst1创建lst2    for (auto num : lst2)    {        std::cout << num << " ";  // 输出：1 2 3    }    std::cout << std::endl;    return 0;}

list 的常用成员函数

list 提供了丰富的成员函数来实现元素的插入、删除、遍历等操作，下面我们介绍几个最常用的函数。

（1）元素插入：push_back、push_front、insert

• push_back(x)：在链表尾部插入元素 x；在c++11以后可用emplace_back代替，效率更高

• push_front(x)：在链表头部插入元素 x；同样可用emplace_front代替，效率更高

• insert(pos, x)：在迭代器 pos 指向的位置插入元素 x，返回指向新插入元素的迭代器。

int main(){    std::list<int> lst = {2, 3};
    lst.push_back(4);  // 尾部插入4，此时lst：2 3 4    lst.push_front(1);  // 头部插入1，此时lst：1 2 3 4
    // 在第二个元素（值为2）的位置插入5    auto it = lst.begin();    ++it;  // it指向第二个元素（2）    lst.insert(it, 5);  // 插入后lst：1 5 2 3 4
    for (auto num : lst)    {        std::cout << num << " ";  // 输出：1 5 2 3 4    }    std::cout << std::endl;    return 0;}

（2）元素删除：pop_back、pop_front、erase、clear

• pop_back()：删除链表尾部的元素，无返回值；

• pop_front()：删除链表头部的元素，无返回值；

• erase(pos)：删除迭代器 pos 指向的元素，返回指向删除元素下一个元素的迭代器；

• clear()：删除链表中所有元素，使链表变为空。

int main(){    std::list<int> lst = {1, 2, 3, 4, 5};
    lst.pop_back();  // 删除尾部元素5，此时lst：1 2 3 4    lst.pop_front();  // 删除头部元素1，此时lst：2 3 4
    // 删除第三个元素（值为4）    auto it = lst.begin();    ++it;    ++it;  // it指向第三个元素（4）    lst.erase(it);  // 删除后lst：2 3
    // 清空链表    lst.clear();    std::cout << "清空后list的大小：" << lst.size() << std::endl;  // 输出0    return 0;}

（3）其他常用函数：size、empty、front、back

• size()：返回链表中元素的个数；

• empty()：判断链表是否为空，为空返回 true，否则返回 false；

• front()：返回链表头部元素的引用；

• back()：返回链表尾部元素的引用。

int main(){    std::list<int> lst = {10, 20, 30};
    if (!lst.empty())    {        std::cout << "list的大小：" << lst.size() << std::endl;  // 输出3        std::cout << "头部元素：" << lst.front() << std::endl;  // 输出10        std::cout << "尾部元素：" << lst.back() << std::endl;  // 输出30    }    return 0;}

forward_list 容器：单向链表的 “轻量选手”

forward_list 是 C++11 标准新增的容器，它的底层实现是单向链表—— 每个节点只包含两个部分：节点存储的数据和后继节点的指针（没有前驱指针）。就像一串只能从第一个珠子摸到最后一个，却不能倒着摸的珠子。

这种结构决定了 forward_list 的特点：

• 内存开销更小

相比 list 的每个节点需要两个指针，forward_list 每个节点只需要一个指针，在存储大量小数据时，内存利用率更高。

• 单向遍历

只能从表头往表尾方向遍历，无法反向遍历，因此没有rbegin()、rend()等反向迭代器，也没有back()、pop_back()等操作尾部的函数（因为要找到尾部需要遍历整个链表，效率太低）。

• 插入删除效率高（头部和中间）

和 list 类似，在已知位置的前面插入或删除元素时，时间复杂度是 O (1)，但操作尾部元素效率很低。

forward_list 的缺点和 list 类似：随机访问效率低，必须通过遍历才能找到目标元素。

forward_list 的定义与初始化

使用 forward_list 需要包含头文件<forward_list>，它的初始化方式和 list 基本一致，只是因为是单向链表，没有size()成员函数（要获取大小需要遍历整个链表，时间复杂度 O (n)，所以标准库没有提供）。

方式 1：默认初始化，创建空 forward_list

#include <forward_list>#include <iostream>int main(){    std::forward_list<int> flst;  // 创建空的forward_list    std::cout << "forward_list是否为空：" << (flst.empty() ? "是" : "否") << std::endl;  // 输出“是”    return 0;}

方式 2：指定元素个数和初始值

int main(){    std::forward_list<int> flst(3, 5);  // 创建包含3个5的forward_list    for (auto num : flst)    {        std::cout << num << " ";  // 输出：5 5 5    }    std::cout << std::endl;    return 0;}

方式 3：通过迭代器范围初始化

#include <array>int main(){    std::array<int, 4> arr = {1, 3, 5, 7};    std::forward_list<int> flst(arr.begin(), arr.end());  // 拷贝array的元素    for (auto num : flst)    {        std::cout << num << " ";  // 输出：1 3 5 7    }    std::cout << std::endl;    return 0;}

方式 4：使用初始化列表赋值

int main(){    std::forward_list<int> flst = {2, 4, 6, 8};  // =可省略    for (auto num : flst)    {        std::cout << num << " ";  // 输出：2 4 6 8    }    std::cout << std::endl;    return 0;}

forward_list 的常用成员函数

由于 forward_list 是单向链表，它的成员函数和 list 有一些区别，比如没有push_back()、pop_back()、back()、size()等函数，但新增了before_begin()函数（指向链表头节点之前的位置）。

（1）元素插入：push_front、insert_after

• push_front(x)：在链表头部插入元素 x，时间复杂度 O (1)；c++11后可用emplace_front代替，效率更高

• insert_after(pos, x)：在迭代器 pos 指向的位置后面插入元素 x，返回指向新插入元素的迭代器（因为单向链表无法直接在某个位置前面插入，只能在后面插入）。可用emplace_after代替，效率更高

#include <forward_list>#include <iostream>
int main(){    std::forward_list<int> flst = {2, 3};
    flst.push_front(1);  // 头部插入1，此时flst：1 2 3
    // 在第一个元素（值为1）后面插入4    auto it = flst.begin();  // it指向1    flst.insert_after(it, 4);  // 插入后flst：1 4 2 3
    // 在链表开头之前的位置（before_begin）后面插入0（相当于头部插入）    auto before_it = flst.before_begin();    flst.insert_after(before_it, 0);  // 插入后flst：0 1 4 2 3
    for (auto num : flst)    {        std::cout << num << " ";  // 输出：0 1 4 2 3    }    std::cout << std::endl;    return 0;}

（2）元素删除：pop_front、erase_after、clear

• pop_front()：删除链表头部的元素，时间复杂度 O (1)；

• erase_after(pos)：删除迭代器 pos 指向的位置后面的元素，返回指向删除元素下一个元素的迭代器；

• clear()：删除所有元素，使链表为空。

int main(){    std::forward_list<int> flst = {0, 1, 4, 2, 3};
    flst.pop_front();  // 删除头部元素0，此时flst：1 4 2 3
    // 删除第一个元素（1）后面的元素（4）    auto it = flst.begin();  // it指向1    flst.erase_after(it);  // 删除后flst：1 2 3
    // 清空链表    flst.clear();    std::cout << "清空后forward_list是否为空：" << (flst.empty() ? "是" : "否") << std::endl;  // 输出“是”    return 0;}

（3）其他常用函数：empty、front、before_begin

• empty()：判断链表是否为空；

• front()：返回头部元素的引用；

• before_begin()：返回指向链表头节点之前的迭代器（不能解引用，只能用于insert_after或erase_after）。

int main(){    std::forward_list<int> flst = {5, 6, 7};
    if (!flst.empty())    {        std::cout << "头部元素：" << flst.front() << std::endl;  // 输出5
        // 利用before_begin()在头部插入元素4        flst.insert_after(flst.before_begin(), 4);        for (auto num : flst)        {            std::cout << num << " ";  // 输出：4 5 6 7        }        std::cout << std::endl;    }    return 0;}

list 与 forward_list 的区别

list 与 forward_list 的核心区别就是单向和双向链表的区别，如下表所示

特性	list（双向链表）	forward_list（单向链表）
节点结构	数据 + 前驱指针 + 后继指针	数据 + 后继指针
遍历方向	支持双向遍历（正向、反向）	只支持正向遍历
迭代器类型	有begin()/end()、rbegin()/rend()	只有begin()/end()，无反向迭代器
尾部操作效率	支持back()/push_back()/pop_back()（O(1)）	不支持尾部操作（需遍历，O (n)）

成员函数的差异

两者的成员函数差异主要源于底层结构的不同，下面列出一些关键的差异点：

成员函数	list 支持	forward_list 支持	原因分析
size()	是	否	forward_list 需遍历才能获大小，效率低
back()	是	否	forward_list 无法快速访问尾部
push_back()	是	否	同上
pop_back()	是	否	同上
rbegin()	是	否	单向链表无法反向遍历
rend()	是	否	同上
before_begin()	否	是	用于在头部前插入 / 删除元素
insert_after()	否	是	单向链表只能在指定位置后插入

这两个容器各有一个容易混淆的成员函数 insert 与 insert_after 

通过下面代码示例了解各自的用法

#include <list>#include <forward_list>#include <iostream>int main(){    // 1. list的insert：在迭代器指向位置的“前面”插入元素    std::list<int> lst = {10, 20, 30};    auto lst_it = lst.begin();  // 指向10    ++lst_it;                   // 指向20    lst.insert(lst_it, 100);    // 在20前面插入100    // 此时lst：10 100 20 30       // 2. forward_list的insert_after：在迭代器指向位置的“后面”插入元素    std::forward_list<int> flst = {10, 20, 30};    auto flst_it = flst.begin();// 指向10    ++flst_it;                  // 指向20    flst.insert_after(flst_it, 200);  // 在20后面插入200    // 此时flst：10 20 200 30        return 0;}

list 与 forward_list 如何选择

了解了两种容器的基本用法后，如何在实际应用中选择适当的容器？下面列举几个典型场景，

• list 的适用场景

list 的核心优势是 “双向操作” 和 “高效的中间插入删除”，适合以下场景：

场景 1：双向链表实现的 “双端队列”

比如实现 “任务调度队列”，需要支持：

• 从队头取出紧急任务（pop_front ()）；

• 从队尾添加普通任务（push_back ()）；

• 删除队列中间的过期任务（erase ()）。

此时 list 的 push_front ()、push_back ()、erase () 均为 O (1)，而 vector 的中间删除是 O (n)，forward_list 无 push_back ()，因此 list 是最优选择。

实例代码

#include <list>#include <string>#include <iostream>// 任务结构体struct Task{    std::string name; // 任务名    int priority;     // 优先级（1-5，5最高）    bool is_expired;  // 是否过期};int main(){    std::list<Task> task_queue;    // 添加任务（队尾加普通任务，队头加紧急任务）    task_queue.push_back({"备份数据", 2, false});    task_queue.push_front({"修复漏洞", 5, false});    task_queue.push_back({"生成报表", 1, false});    task_queue.push_front({"拦截攻击", 5, false});    // 删除过期任务（假设“生成报表”任务过期）    for (auto it = task_queue.begin(); it != task_queue.end();)    {        if (it->name == "生成报表")        {            it->is_expired = true;            it = task_queue.erase(it); // 删除并获取下一个迭代器        }        else        {            ++it;        }    }    // 执行任务（从队头开始）    std::cout << "执行任务顺序：" << std::endl;    while (!task_queue.empty())    {        Task t = task_queue.front();        task_queue.pop_front();        std::cout << "执行：" << t.name << "（优先级：" << t.priority << "）" << std::endl;    }    return 0;}

执行结果

场景 2：需要前后遍历的 “历史记录”

比如实现 “文本编辑器的撤销记录”，需要支持：

• 向前遍历（撤销上一步操作）；

• 向后遍历（恢复上一步操作）；

• 删除最早的记录（当记录数超过上限时）。

list 的 rbegin ()/rend () 支持反向遍历，erase () 可高效删除头部记录，而 forward_list 无法反向遍历，因此 list 更合适。

• forward_list 的适用场景

forward_list 的核心优势是 “内存开销小” 和 “单向操作高效”，适合以下场景：

场景 1：内存受限的 “单向消息队列”

比如嵌入式设备（如智能手表）的 “通知消息队列”，特点是：

• 仅需从队头读取消息（pop_front ()）；

• 仅需从队头插入紧急消息（push_front ()）；

• 设备内存极小（如仅有几 MB 内存）。

forward_list 的节点比 list 少一个指针（节省 4 字节或 8 字节，取决于系统位数），在海量消息场景下内存优势明显，且单向操作效率与 list 相当。

场景 2：无需反向遍历的 “链表结构”

比如实现 “链表式哈希表的桶”，哈希表的每个桶需要存储冲突的键值对，特点是：

• 仅需从桶头遍历查找元素；

• 插入元素时仅需在桶头添加；

• 无需反向遍历或尾部操作。

此时 forward_list 足够满足需求，且比 list 更节省内存，适合哈希表这种需要大量桶的结构。

总结：链表容器的区别与选型

核心区别

• list 是双向循环链表（节点有 prev/next 指针），forward_list 是单向链表（仅 next 指针）；

• list 支持反向遍历、尾部操作（push_back/pop_back），forward_list 不支持；

• forward_list 节点内存开销更小（少一个指针），list 查询大小更高效（size () 是 O (1)）。

实际开发中，先明确业务场景的核心操作（是插入删除还是随机访问？是单向还是双向？），再选型。

vector适用场景：

• 需要随机访问元素（通过下标访问）

• 元素数量相对稳定，插入删除主要在尾部

• 对遍历性能要求高

list适用场景：

• 需要在任意位置频繁插入删除元素

• 需要双向遍历

• 元素数量不确定，频繁动态变化

• 不需要随机访问

forward_list适用场景：

• 内存资源受限，需要最小化内存占用

• 只需要单向遍历

• 在头部频繁插入删除

• 不需要获取容器大小

另外要注意一点，对于小型元素和不频繁的中间插入删除，vector往往表现更好，因为其缓存优势可以抵消元素移动的开销。比如小数据量时 vector 的中间插入可能比 list 快（因为链表有节点分配开销）

往期文章