为什么std::forward_list没有size()成员函数？

Question

我一直使用 C++11 的

forward_list

作为快速插入的容器，没有太多内存开销，因为它是一个单链表。

在意识到

forward_list

没有

size()

方法之后，我对其背后的推理有点困惑。难道它不能只维护一个私有字段来跟踪插入和删除的节点，从而实现 O(1) size() 操作吗？

Answer 1

N2543是提案，里面有关于

size()

的详细讨论。

选项 3 [不提供

size()

] 和选项 2 [提供 O(1)

size()

] 之间的选择更多的是一个判断问题。 我选择选项 3 的原因与选择 insert-after 的原因相同 而不是 insert-before：选项 3 更符合目标 与手写的 C 风格链表相比，零开销。 保持计数会使

forward_list

对象的大小加倍（一个 单词代表列表头，一个单词代表计数），并且它会减慢每个 改变节点数量的操作。在大多数情况下，这不是 渐近复杂度的变化（渐近复杂度的一个变化 复杂度采用

splice

) 的形式之一，但它不为零 高架。这是所有用户都必须付出的成本，无论 他们是否需要此功能，并且对于关心的用户 维护计数，在外部维护它也同样容易 列表，通过每次插入增加计数并减少计数 每次擦除，因为它是为了维护列表中的计数。

Answer 2

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

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

A

std::forward_list

不提供

size()

成员函数。这是省略的结果 相对于手写单链表会产生时间或空间开销的功能。

Answer 3

我想知道标准委员会是否考虑将混合作为模板参数，可以将可选大小成员的维护添加到列表类中？这将允许类有一个可选的元素计数，而不失一般性。

像这样

class HasSize
{ 
public:
   HasSize() : size_(0) { } 

   void addSize(size_t add) { size_ += add; }

   bool has_size() { return true; }

   size_t size() { return size_; }

   size_t size_;
};

class NoSize
{ 
public:
   void addSize(size_t add) { }

   bool has_size() { return false; }

   size_t size() { return 0; }
};

template<type T, type Allocator, type Sz = HasSize>
class forward_list
{

    void push_back( T &arg )
    {
         ...
         opt_.addSize( 1 );
    }

    size_t size()
    {
       if (opt_.has_size())
          return opt_.size();
       else
          return std::distance(begin(), end()); 
    }

    Sz opt_;
};

/这个问题被标记为重复，所以在这里添加/