list 与 forward_list

定义与作用

std::list（双向链表）和 std::forward_list（单向链表，C++11）是节点式容器，元素分散存储，通过指针串联。核心优势：任意位置 O(1) 插入/删除，且不使其他迭代器失效。

#include <list>
std::list<int> lst{1, 2, 3};
lst.push_front(0);        // O(1)
lst.insert(lst.begin(), -1);  // O(1)

#include <forward_list>
std::forward_list<int> fl{1, 2, 3};
fl.push_front(0);         // O(1)，只支持前端操作

特性	list	forward_list
节点结构	双向（prev + next）	单向（next only）
内存开销	2 指针/节点	1 指针/节点
遍历方向	双向	仅正向
push_back	O(1)	不支持（需 O(n) 找尾）
size()	O(1)（C++11 起要求）	不支持（设计取舍）
splice	完整支持	splice_after

核心原理

节点结构对比

splice 操作

完整示例

示例一：飞翔科技事件时间线

场景说明：黄俪用 list 管理飞翔科技产品迭代的事件时间线，支持在任意位置插入新事件和合并两个时间线。

#include <iostream>
#include <list>
#include <string>
#include <algorithm>

struct Event {
    std::string date;
    std::string description;

    Event(std::string d, std::string desc)
        : date(std::move(d)), description(std::move(desc)) {}
};

void printTimeline(const std::string& title, const std::list<Event>& tl) {
    std::cout << title << ":\n";
    for (const auto& e : tl)
        std::cout << "  " << e.date << " | " << e.description << "\n";
}

int main() {
    // 2026年主版本时间线
    std::list<Event> mainTimeline;
    mainTimeline.emplace_back("2026-01-15", "飞翔科技 v3.0 需求评审（孔蓝）");
    mainTimeline.emplace_back("2026-03-01", "飞翔科技 v3.0 架构设计（白歌）");
    mainTimeline.emplace_back("2026-05-20", "飞翔科技 v3.0 灰度发布");

    // 紧急修复时间线
    std::list<Event> hotfixTimeline;
    hotfixTimeline.emplace_back("2026-05-10", "紧急修复：支付回调超时（小崔）");
    hotfixTimeline.emplace_back("2026-05-12", "紧急修复：缓存击穿（白歌）");

    printTimeline("主版本时间线", mainTimeline);
    printTimeline("热修复时间线", hotfixTimeline);

    // splice：将热修复时间线合并到主时间线灰度发布之前
    auto grayPos = std::find_if(mainTimeline.begin(), mainTimeline.end(),
        [](const Event& e) { return e.description.find("灰度") != std::string::npos; });

    mainTimeline.splice(grayPos, hotfixTimeline);

    std::cout << "\n";
    printTimeline("合并后时间线", mainTimeline);
    std::cout << "热修复时间线是否为空: " << hotfixTimeline.empty() << "\n";
}

预期输出：

主版本时间线:
  2026-01-15 | 飞翔科技 v3.0 需求评审（孔蓝）
  2026-03-01 | 飞翔科技 v3.0 架构设计（白歌）
  2026-05-20 | 飞翔科技 v3.0 灰度发布
热修复时间线:
  2026-05-10 | 紧急修复：支付回调超时（小崔）
  2026-05-12 | 紧急修复：缓存击穿（白歌）

合并后时间线:
  2026-01-15 | 飞翔科技 v3.0 需求评审（孔蓝）
  2026-03-01 | 飞翔科技 v3.0 架构设计（白歌）
  2026-05-10 | 紧急修复：支付回调超时（小崔）
  2026-05-12 | 紧急修复：缓存击穿（白歌）
  2026-05-20 | 飞翔科技 v3.0 灰度发布
热修复时间线是否为空: 1

逐段分析：

splice 将 hotfixTimeline 的全部节点直接"挂接"到目标位置，无拷贝无移动，O(1)
splice 后源 list 为空，所有迭代器依然有效（指向原节点，现属于新 list）
与 insert 拷贝元素相比，splice 是真正的零开销重组

示例二：forward_list 消息过滤链

场景说明：李眉用 forward_list 实现一个消息过滤链，动态插入/移除过滤器。

#include <iostream>
#include <forward_list>
#include <string>
#include <functional>

using FilterFunc = std::function<bool(const std::string&)>;

class MessageFilter {
public:
    // 在头部添加过滤器
    void prepend(FilterFunc fn) {
        filters_.push_front(std::move(fn));
    }

    // 移除特定条件过滤器
    void removeByKeyword(const std::string& keyword) {
        filters_.remove_if([&](const FilterFunc& fn) {
            // 简化为判断函数是否涉及关键词（实际应为更精确的匹配）
            return true;  // 示例：移除所有
        });
    }

    // 在某个过滤器之后插入
    template<typename Pred>
    void insertAfter(Pred pred, FilterFunc fn) {
        auto it = std::find_if(filters_.begin(), filters_.end(), pred);
        if (it != filters_.end())
            filters_.insert_after(it, std::move(fn));
    }

    bool apply(const std::string& msg) const {
        for (const auto& filter : filters_)
            if (!filter(msg)) return false;
        return true;
    }

private:
    std::forward_list<FilterFunc> filters_;
};

int main() {
    MessageFilter chain;

    // 添加过滤器
    chain.prepend([](const std::string& s) -> bool {
        return !s.empty();  // 非空检查
    });
    chain.prepend([](const std::string& s) -> bool {
        return s.size() <= 1024;  // 长度检查
    });

    std::cout << std::boolalpha;
    std::cout << "飞翔科技-日志消息: "
              << chain.apply("飞翔科技-服务器正常") << "\n";
    std::cout << "空消息: " << chain.apply("") << "\n";
}

预期输出：

飞翔科技-日志消息: true
空消息: false

逐段分析：

forward_list 仅支持 insert_after 和 erase_after（需要访问前驱节点）
内存开销更小：每个节点仅 1 个指针（vs list 的 2 个）
适合：只需正向遍历、内存敏感的简单链表场景

易错场景与面试考点

易错场景

1. forward_list 没有 size()

std::forward_list<int> fl{1, 2, 3};
// fl.size();     // ❌ 编译错误！forward_list 不提供 size()
auto n = std::distance(fl.begin(), fl.end());  // O(n)

2. list 的 sort 是成员函数

std::list<int> lst{3, 1, 2};
lst.sort();                    // ✅ 成员函数，O(n log n)
// std::sort(lst.begin(), lst.end());  // ❌ list 迭代器非随机访问

3. splice 后源 list 元素被移走

std::list<int> a{1, 2}, b{3, 4};
auto it = b.begin();
a.splice(a.end(), b);
// *it 仍然有效，但 it 现在属于 a，不属于 b

面试考点

考点	要点
list vs forward_list	双向 2 指针 vs 单向 1 指针
splice 复杂度	O(1)，仅修改指针
迭代器失效	插入/删除不使其他迭代器失效
list::sort	成员函数，使用归并排序
list::remove/remove_if	成员函数，真正删除元素（vs 算法 remove 只是移动）
何时用 list	频繁中间插入删除、需要 splice、迭代器稳定