This is the mail archive of the
mailing list for the libstdc++ project.
Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
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
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".
", 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);
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!!!