[C++] Should the complexity of std::list::size() be O(n) or O(1)?

[Peter Dimov]

Gabriel Dos Reis wrote:
> Howard Hinnant <hhinnant@apple.com> writes:
>
> [...]
>
>> Conclusion:  Yes, you can store the size externally.  But you loose
>> performance and/or functionality in the above members that will also
>> have to be recoded.
>
> I think I'm still unconvinced that we have to change list::size, here.
>
> Since it was a mistake to put it there in the first place, why shall
> we penalize proper list operations by trying to make an error run
> faster?

The current status quo is the worst of both worlds. You can't rely on O(1) 
size, and you can't rely on O(1) splice (or the size being absent, 
presumably for footprint reasons.) It needs to be specified one way or the 
other, and when you have to commit to a choice, O(1) is a clear winner, IMO.