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

[Howard Hinnant <hhinnant at apple dot com>]

On Nov 23, 2005, at 8:44 PM, Paolo Carlini wrote:

> 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
>
> Thanks! By the way, I'm very puzzled by the words: "... snap shot of
> boost, just after the release of version 1.33, on Nov. 23, 2005".  
> Maybe
> ", just after the release of version 1.33" should go?

<nod>  Yeah, it definitely isn't formal (or precise) wording.  I was  
just trying to get something up quick (just on my personal website).   
I might massage it into something readable if I find some cycles.

It would also be most interesting if it surveyed something more than  
boost, or if it at least did a more complete survey of boost.   
Finding all of the uses of list::size() in generic code is a real  
problem.  Searching boost sources for size() turns up nearly 2000  
hits, most of which won't be related to list, but I wouldn't be  
surprised if a few percent of them were inappropriate calls to  
list::size() (or could be, depending on template parameters).  But I  
can't make a career out of manually picking through 2000 calls to size 
() and figuring out which are which. :-)

I realize I've got an uphill (almost sure to loose) battle here.  gcc  
has had an O(N) list::size for forever.  And the supporters of that  
decision are numerous, adamant and smart.  When I considered gcc's  
libstdc++ a competitor, I actually took comfort in that fact, secure  
in the knowledge that gcc would never come around and challenge me in  
that department.  If gcc's customer base mysteriously saw significant  
performance gains when migrating to my product, that was a good  
thing! ;-)  Now, ironically, I find myself in a position of trying to  
argue for the very change that I took comfort in believing would  
never happen. :-)

My position isn't that a doubly-linked list should have an O(1)  
size.  It is that if a container, any container, has a size(), then  
that member should be O(1) (same for operator[], at, swap, max_size,  
capacity, begin, end, front, back, push/pop_front, push/pop_back,  
empty, default ctor,  -- perhaps amortized O(1) on some of those).   
It would be incredibly easy to give std::list an operator[].  It  
would also be an incredibly bad idea.

std::list has a size().  We should either get rid of it, or make it O 
(1).  Having it there, and (maybe) be O(N) is nothing but a bear trap  
waiting to spring on the next person that comes to C++ and hasn't yet  
memorized Scott's Effective STL (btw I haven't memorized that  
valuable book either).  I think getting rid of list::size is too big  
of a backwards compatibility hit.

Yes, I'm aware of the size-cache compromise solution (size() is O(1)  
until splice invalidates it).  I worry about:

for (int i = 0; i < list.size(); ++i)
{
    ...
    list.splice(list.end(), other_list, ol1, ol2);
    ...
}

I think

    void splice(iterator position, list& x, iterator first, iterator  
last, size_type n);  // must be O(1)

is a better compromise.  I also realize that it *is* a compromise,  
and not a 100% solution.

An additional compromise would be to get slist into the std::tool  
box, and without a member size() - a real minimum-overhead linked  
list (ok, so it wouldn't be a "sequence", or even a "container", is  
that important?).  Maybe even guarantee that its default ctor does  
not ask the allocator for memory.  I'm pretty much thinking  
__gnu_cxx::slist but without the size() member! :-) (and maybe  
without the traditional insert/erase/splice members too - you don't  
want to call these by accident in generic code).

I'm uncertain if a dlist (a std::list without size) would also be  
valuable.  dlist strikes me as a little gratuitous given that  
std::list already exists.

Btw, I've lost track of which individuals were responsible for taking  
the dummy end nodes out of the node-based containers.  But imho that  
was such a major advance in the fundamental design of these  
containers that the old HP and SGI copyrights hardly even apply any  
more.  Not that I'm suggesting taking the copyrights out (I'm not).   
Just that these are now fundamentally different, and much improved  
containers.  You just can't underestimate the value of a fast and  
nothrow default ctor.  Nice job!!!

-Howard