N2543 is the proposal, and it has a detailed discussion about 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 aforward_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 ofsplice
), 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.