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

[Gabriel Dos Reis <gdr at integrable-solutions dot net>]

Jonathan Wakely <jwakely.gcc@gmail.com> writes:

| On 11/29/05, Peter Dimov <pdimov@mmltd.net> wrote:
| > Jonathan Wakely wrote:
| > std::list is often the right choice when either:
| >
| > - the element size is sufficiently large so that deque degenerates into a
| > (much) less efficient or capable list;
| 
| All those are good points, but I've quoted that one as it's also a
| good argument for not having an O(N) size() ... if you use list
| because it copes with very large N, you definitely don't want O(N)
| size!

Indeed.  The observation is not that size() is never needed -- I'm
pretty sure one can come up quickly with such uses in real codes.  On
of the point, as you're making, is one doesn't just use "size()"
because it is cool. Using size() must require the same attention as
choosing the right containers given reference/invalidation constraints
and algorithmic complexities.  Therefore, arguments that XXX do it
that way is rarely convincing; otherwise following that principle we
would just have to remove the reference/invalidation constraints stuff
(and we would be even more popular :-))
Maybe it is time for std::linked_list_with_constant_time_size or
std::llwcts :-)

-- Gaby