C++ STL - 为什么forward_list没有size()方法？

Question

我一直在使用C++ 11 forward_list作为快速插入的容器,没有太多的内存开销,因为它是一个单链表.

在意识到forward_list没有size()方法之后,我对这背后的推理感到有点困惑.它是否只能维护一个私有字段来跟踪插入和删除的节点,从而实现O(1)size()操作？

Answer 1

N2543是提案,它有详细的讨论size().

备选方案3 [未提供size()]和备选方案2 [提供O(1)size()]之间的选择更多的是判断问题.我选择Option 3的原因与我选择insert-after而不是insert-before相比:与手写的C风格链表相比,Option 3更符合零开销的目标.维护计数会使forward_list对象的大小加倍(列表头的一个字和计数的一个字),并且会减慢每个更改节点数的操作.在大多数情况下,这不是渐近复杂度的变化(渐近复杂度的一个变化是其中一种形式的splice),但它是非零开销.这是一个所有用户都需要付费的成本,无论他们是否需要这个功能,而且,对于那些关心维护计数的用户来说,通过每次插入和每次插入增加计数,就可以轻松地将其维护在列表之外.每次擦除都会减少它,因为它是在列表中保持计数.

Answer 2

STL 容器传统上/智能地删除了在时间和空间方面表现不佳的数据结构的特征。

添加来自 Nicolai M. Josuttis 的“C++ 标准库 - 教程和参考”的引用。

Astd::forward_list不提供size()成员函数。这是由于省略了相对于手写单链表产生时间或空间开销的特征的结果。