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

[chris jefferson <caj at cs dot york dot ac dot uk>]

Howard Hinnant wrote:
> 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.
Not another C++ project, but I recently happened to mark a university 
C++ project which involved a list of tasks which were handled FIFO and 
also had to check if the list of tasks to do ever got too large. This 
doesn't seem an unreasonable thing to do.

The obvious way to solve this, and the way everyone did, was to use a 
std::list to hold the tasks. To check for too many tasks, about 3/4 of 
people used list::size, and about 1/4 kept the size counter themselves 
(out of a group of 25ish).

I am in the crowd of people who say that list::size simply shouldn't 
exist at all, but if it has to exist (and being honest, it can't be 
removed now), it should be O(1). The idea of being "O(1) most of the 
time, except after a splice" might be OK, except it could very quickly 
end up looking like "string iterators are invalidated when..", which is 
the (in my opinion) single worst part of the standard.

Chris