forward_list _生活百科

forward_list【forward_list】forward_list是一种序列容器.它允许对任何位置的常量时间的插入和删除操作.
基本介绍中文名：前向(单向)鍊表
外文名：forward list
forward_list是一种序列容器，它允许对任何位置的常量时间的插入和删除操作。forward_list实现为单向鍊表.鍊表中的每一个元素都存在于位置无关的存储空间里，他们的顺序由每个元素的next指针决定。forward_list和list在设计上的主要区别在于前者在内部只有一个指向下一个元素的指针；而对于后者，每个元素都有2个指针：一个指向下一个元素，一个指向前一个元素。list可以高效地在两个方向进行叠代,但是这样的话每个元素会消耗更多的存储空间，并且插入和删除的时间开销会稍微大一些。因此，儘管只能进行前向叠代，forward_list对象比list对象更高效。和其他的标準序列容器(array,vector,deque)相比较的话，forware_list在任何位置的插入，删除和移动操作会更快。因此在诸如sorting算法中会更倾向于使用它。forward_list和list的一个最主要的缺点是无法直接通过位置访问元素。例如为了访问forward_list中的第六个元素，必须从第一个元素一个一个叠代到第六个元素。这个操作是线性複杂度的。位置距离起始点越长，就会消耗越多的时间。另外,forward_list也会消耗额外的记忆体来记录每一个元素之间的指针信息。对于非常小的对象，这个消耗就会非常明显。forward_list类模板被设计得非常高效。它被设计得如同C语言的单向鍊表一样，为了效率考虑，有意不提供size成员函式。因为如果要实现size成员函式的话，为了常量时间的考虑，就必须保持一个内部计数器记录forward_list的大小。这会消耗额外的存储空间，并且会让插入，删除操作变得更慢。为了获得一个forward_list对象的大小，可以使用distance算法来计算begin和end之间的距离，这个操作是线性时间複杂度的。