C ++ STL-为什么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的原因与选择插入后的原因相同而不是之前插入：选项3与目标更加一致与手写的C样式链表相比，开销为零。保持计数将forward_list对象的大小加倍（一个单词代表列表头，一个代表计数），并且会减慢每个更改节点数的操作。在大多数情况下，这不是渐进复杂性的变化（渐近复杂性的一种变化复杂度为splice的一种形式，但非零高架。这是所有用户都必须支付的费用，无论是否他们是否需要此功能，对于关心的用户保持计数，将其保持在外部很容易列表，通过在每次插入时增加计数并减少计数每次擦除都将保持计数在列表中。

Answer 2

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

从“ C ++标准库添加引文-教程和参考”

A std::forward_list不提供size()成员函数。这是省略的结果相对于手写单链表会产生时间或空间开销的功能。

Answer 3

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

喜欢这样

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_;
};

/这个问题被标记为重复，因此在这里添加它/