Size of std::forward_list

I'm reading The C++ Standard Library (2nd Edition) (Nicolai M. Josuttis).
Arcording to the book content, forward_list does not support function or method to compute its size. The reason is that it is not possible to store or compute the current number of elements in constant time.
I don't really understand it.
I think it can support a kind of size() member function that returns a field (maybe, private int size). When we add or remove element, this field change its value.
Somebody help me to explain this. Thank you!
The proposal by which it was added to C++ was http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2543.htm

from their rationale,

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.

fast splice in particular has always been the strongest point against fast size (even though it has been almost always losing)
Last edited on
Topic archived. No new replies allowed.