2.16、list 和 forward_list 的区别？

• • 数据结构类型
  • • std::list：基于 双向链表（doubly linked list） 实现，每个节点包含指向前后两个节点的指针。
  • • std::forward_list：基于 单向链表（singly linked list） 实现，每个节点只包含指向下一个节点的指针。

设计与性能差异

• • 内存占用
  • • std::forward_list：每个节点仅维护一个指针，节省指针开销，内存使用更紧凑，缓存局部性更优，适合对内存敏感的场景。
  • • std::list：因维护双向指针，单个节点内存开销更大，且指针数量多可能导致缓存未命中率上升，性能稍逊于 forward_list。
• • 遍历方向
  • • std::list：支持 双向遍历，可通过双向迭代器（bidirectional_iterator）进行前向和后向迭代（如 rbegin()/rend()）。
  • • std::forward_list：仅支持 单向遍历，只能通过单向迭代器（forward_iterator）从头到尾顺序访问，无法逆向遍历。
• • 插入和删除操作
  • • 两者均支持常数时间的节点插入/删除，但操作方式存在差异：
    • • std::forward_list：插入/删除需通过“前一个节点”的迭代器完成（单向链表无法直接访问前驱节点），例如使用 insert_after()/erase_after()。
    • • std::list：可直接通过任意节点的迭代器进行插入/删除（双向链表可访问前驱节点），接口更灵活（如 insert()/erase()）。
• • 大小信息维护
  • • std::list：内部维护节点数量，size() 操作时间复杂度为 O(1)。
  • • std::forward_list：不维护大小，调用 size() 需遍历全表，时间复杂度为 O(n)。

接口和使用差异

• • 头部操作
  • • std::forward_list：提供 push_front() 和 emplace_front()，头部插入效率高，推荐使用 emplace_front() 避免不必要的拷贝/移动；不支持尾部插入（无尾指针）。
  • • std::list：支持头部插入（push_front()/emplace_front()）和尾部插入（push_back()/emplace_back()）。
• • 插入位置
  • • std::forward_list：通过 insert_after() 和 emplace_after() 在指定节点之后插入元素。
  • • std::list：通过 insert() 在指定位置之前插入元素，接口更直观（支持双向操作）。
• • 迭代器类型
  • • std::list：提供 双向迭代器（bidirectional_iterator），支持 ++ 和 -- 操作，可逆向遍历。
  • • std::forward_list：仅提供 单向迭代器（forward_iterator），只支持 ++ 操作，不支持逆向迭代。

选择建议与应用场景

• • 优先选择 std::list 的场景
  • • 需要双向遍历（如逆序迭代）。
  • • 频繁在序列中间位置进行插入/删除操作（如链表队列、关联容器辅助结构）。
  • • 对内存占用敏感度较低，更关注接口灵活性。
• • 优先选择 std::forward_list 的场景
  • • 仅需单向遍历（如流式数据处理、一次性顺序访问）。
  • • 对内存和缓存效率要求高（如嵌入式系统、高性能内存敏感型应用）。
  • • 主要操作集中在头部插入/删除，且不需要尾部操作。
• • 工程实践建议
  除非必须利用链表的插入/删除特性（如常数时间复杂度的中间操作），否则优先考虑 std::vector 等连续存储容器，因链表的非连续内存布局缓存友好度差，随机访问性能低下。

总结对比表

本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）