This is the mail archive of the mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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 remains O

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!!!


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]