Re: [boost] [intrusive] New version uploaded. Review Request.

From: me22 (me22.ca_at_[hidden])
Date: 2006-12-09 13:46:53

On 12/9/06, Mathias Gaunard <mathias.gaunard_at_[hidden]> wrote:
> I thought containers were only supposed to provide operations if those
> were efficient.
> If std::list::size is linear, then it shouldn't have been provided and
> std::count should have been used instead.
>
std::distance, but yeah.

I believe that std::list::size should not be provided so that it's
obviously linear, allowing std::list::splice to be constant-time
because you can cache size yourself but you can't make an O(N) splice
O(1).

> I do not have the time to check the spec though, so I'll believe you if
> you say it's not guaranteed to be O(1).
>
It seems to have its compexity specified as "(Note A)" which is
"should be constant", but should != must.

A quick google search found
http://gcc.gnu.org/ml/libstdc++/2005-11/msg00219.html :
"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."

~ Scott