abrahams@mediaone.net (Dave Abrahams) wrote:
> > Similarly the STL list<> requires that size() be O(1) which means the
> > length must be stored rather than calculated as needed. This doubles
> > the memory overhead for a zero-length list and means splice cannot be
> > O(1). Again these are highly specific, and controversial, choices.
>
> Actually, the exact opposite is the case.

Really? You mean std::list<>::size() is not O(1) and splice is? If so my
chagrin at being caught in a mistake is only out-weighed by my joy that
the standard got it right :-)

Still, my main point - that these were specific, controversial choices
which constrain implementations - remains.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Dave Harris wrote:
>
> Really? You mean std::list<>::size() is not O(1) and splice is? If so my
> chagrin at being caught in a mistake is only out-weighed by my joy that
> the standard got it right :-)

The standard requires list::splice() to be constant time (i.e. O(1)). As
far as I can tell, it places no constraints on size() for *any* of the
standard containers. It says (in the "Container requirements" table)
that size() in general *should* be constant time, but that's not a
binding requirement, and none of the individual containers document any
additional constraints on size(). It seems that any container's size()
function could take arbitrary time without affecting conformance
(although it's difficult to imagine any kind of container for which it
could be worse than linear).

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
The good news, according to the FCC, is that television viewing won't be
interrupted by the Y2K problem. The bad news, according to the rest of
us, is that television viewing won't be interrupted by the Y2K problem.
                               -- Jonathan Erickson in Dr Dobb's Journal



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 2 Aug 1999 23:31:57 GMT, Ross Smith <ross.s@ihug.co.nz> wrote:

:
: Dave Harris wrote:
: >
: > Really? You mean std::list<>::size() is not O(1) and splice is? If so my
: > chagrin at being caught in a mistake is only out-weighed by my joy that
: > the standard got it right :-)
:
: The standard requires list::splice() to be constant time (i.e. O(1)).

That depends on which splice you are looking at and what the second
list is.  When splicing an iterator range from one list to another
list, the time is linear.  The time required to count the items
being moved so that the two sizes may be adjusted?

: far as I can tell, it places no constraints on size() for *any* of the
: standard containers. It says (in the "Container requirements" table)
: that size() in general *should* be constant time, but that's not a
: binding requirement, and none of the individual containers document any
: additional constraints on size(). It seems that any container's size()
: function could take arbitrary time without affecting conformance
: (although it's difficult to imagine any kind of container for which it
: could be worse than linear).

Right about *should*.  I wonder about that and what other reason
could require the above linear time.

John


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]