This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: list<>.size()
From: "Joe Buck" <jbuck@possibly.synopsys.com>
>
> It does not appear to be possible to make list<...>::size O(1) without
> violating the requirements of some of the other STL functions.
I used to think so too, but a careful reading of the standard shows that
this isn't true. The splice() operation is only required to be constant
time when elements are being spliced between locations in the same list
(so size() doesn't change); when the splice is from one list to another,
it may be linear (23.2.2.4 para 14). An implementation like Dinkumware's
(used by MSVC) that keeps an internal size variable, and updates it by
counting elements on splice(), is conforming.
That said, though, an implementation like SGI's (used by GCC) that
doesn't keep such a count, and gives constant-time splice() and linear
size(), is also conforming, and I'm inclined to agree with Alexander
Stepanov that it's preferable. After all, if you're using a list rather
than one of the other containers, presumably it's because you need some
of the specialised list operations (such as splice), so it seems
reasonable to give those operations precedence in efficiency over
operations common to all containers.
--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
"So that's 2 T-1s and a newsfeed ... would you like clues with that?"
-- Peter Da Silva