std::forward_list 内存更省但功能受限:节点仅含一个指针,节省约50%内存,但不支持反向遍历、无size()、迭代器仅为前向,插入删除需谨慎维护前置节点。
内存开销和节点结构差异
双向链表(std::list)每个节点必须存两个指针:前驱和后继;单向链表(std::forward_list)只存一个指向下一节点的指针。这意味着在同等元素数量下,forward_list 节点更小,内存占用更低——尤其在存储小型对象(如 int、char*)时,节省可能达 50%。
但代价是:无法反向遍历,也不能在常数时间内获取前一个元素。如果你需要频繁调用 prev() 或从尾部开始迭代,list 是唯一选择。
-
list节点典型布局:prev_ptr → data → next_ptr -
forward_list节点布局:next_ptr → data(C++11 标准要求首节点不存数据,即“哨兵头节点”) - 插入/删除操作本身不因指针数量变慢,但
forward_list的erase_after()接口强制你提供「前一节点」,容易写错
迭代器行为与接口设计不同
std::list 迭代器是双向的(BidirectionalIterator),支持 --it 和 std::prev(it);std::forward_list 迭代器只是前向的(ForwardIterator),只能 ++,不能 –。
这直接影响算法使用:std::reverse、std::sort(需随机访问以外的排序)可直接用于 list,但对 forward_list 不可用——它甚至没有 size() 成员函数(C++11),得用 std::distance(begin(), end()),O(n) 时间。
立即学习“C++免费学习笔记(深入)”;