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

[Howard Hinnant]

On Nov 23, 2005, at 7:11 AM, Paolo Carlini wrote:

> chris jefferson wrote:
>
>> This question comes up every so often, in "offical standard  
>> speak", the
>> word "should" has a specific meaning, which is that an  
>> implementation is
>> supposed to do something unless there is a good reason not to.
>>
>> The reason that size() is O(n) is to allow some of the splice  
>> functions
>> to be more efficient. Basically it's a tradeoff between fast  
>> splicing or
>> fast size.
>>
>> Note that empty() is O(1), as required by the standard, so if  
>> thats what
>> you want, you should use that.
>>
>>
> 100% agreed. I want to add that this issue was recently debated  
> again in
> the LWG reflector: thread starting from c++std-lib-15781 (*).
>
> Paolo.
>
> (*) Everyone can fetch archived messaged sending queries to
> c++std-ping@accu.org (an empty one to learn about the whole thing).

Here is an extremely biased summary of my personal opinion on the  
subject.  It includes a just-completed survey of how the boost  
library is using list::size and the affected variant of list::splice  
(motivation is to survey actual use cases as opposed to contrived  
code).  It also includes a proposal for a new list::splice overload  
that subsumes the functionality of the problem child and yet remains O 
(1).

http://home.twcny.rr.com/hinnant/cpp_extensions/On_list_size.html

I would be very interested in the results of similar surveys done on  
other C++ projects.

-Howard