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

Question

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

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

Answer 1

N2543是proposal，里面有关于size()的详细讨论。

The choice between Option 3 [not providing size()] and Option 2 [providing a O(1) size()] is more a matter of judgment. I have chosen Option 3 for the same reason that I chose insert-after instead of insert-before: Option 3 is more consistent with the goal of zero overhead compared to a hand-written C-style linked list. Maintaining a count doubles the size of a forward_list object (one word for the list head and one for the count), and it slows down every operation that changes the number of nodes. In most cases this isn't a change in asymptotic complexity (the one change in asymptotic complexity is in one of the forms of splice), but it is nonzero overhead. It's a cost that all users would have to pay for, whether they need this feature or not, and, for users who care about maintaining a count, it's just as easy to maintain it outside the list, by incrementing the count with every insert and decrementing it with every erase, as it is to maintain the count within the list.

Answer 2

STL 容器 traditionally/intelligently 删除了在时间和 space 方面表现不佳的数据结构特征。

添加 Nicolai M. Josuttis 的 "The C++ standard library - a Tutorial and Reference" 引述。

A std::forward_list does not provide a size() member function. This is a consequence of omitting features that create time or space overhead relative to a handwritten singly linked list.

Answer 3

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

像这样

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

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

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

C++ STL - Why std::forward_list has no size() method?

c++

stl

c++11

forward-list