I wrote, On 12/09/03 02:35:
> i think the list::splice complexity in 23.2.2.4 para 14 is wrong.
> surely it should be always constant time?
>
> this is the "third" splice:
> splice(iterator pos, list& x, iterator first, iterator kast)
> complexity is listed as:
> "Constant time if &x == this; otherwise linear time."
>
> i think it should be: "Constant time."
>
> this will ensure that DR 250 (list::splice shouldn't invalidate
> iterators) is correctly implemented for this version of splice too.
>
> (btw. Sun ONE Studio 8 CC (5.5) incorrectly has linear time
> splice(iterator, list& x) (and also invalidates the iterators in x).  i
> have submitted a bug report to Sun)

i think i can answer my own question, and no, the standard is not wrong.
 the standard is allowing for list::size() to be constant time.

if list::size() is constant time, then all insertions/deletions to a
list have to update the list's size.  the first two list::splice()'s
(all of a list x, or one item) have a known size (x.size() or 1) so
updates to both *this and x can be constant time.  the third
list::splice() has an unknown range, so distance(first, last) must be
used to update the size of *this and x, so it has linear time (unless
this == &x) --- however, copy and erase shouldn't be used to do the
splice (which means Sun's library has a bug).

if list::size() is not constant time (as all the libraries i've looked
at are) then the third list::splice() can be constant time.

cheers,
/lib

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

llib+news@computer.org (Bill Clarke) wrote in message news:<3f5fe101$1@clarion.carno.net.au>...
> i think the list::splice complexity in 23.2.2.4 para 14 is wrong.
> surely it should be always constant time?
>
> this is the "third" splice:
> splice(iterator pos, list& x, iterator first, iterator kast)
> complexity is listed as:
> "Constant time if &x == this; otherwise linear time."
>
> i think it should be: "Constant time."

The splice itself may be constant time, but any implementation
that has O(1) size() must update the cached size duing a splice.
You can't determine the size change in constant time, because
std::distance(first,last) is O(n).

Implementations often prefer O(1) size, O(N) splice over O(N) size,
O(1) splice because this splicing is not as common as taking the
size of a container. The standard therefore allows both to be O(N).

If you want absolute guarantees, roll your own. A list class is
basic enough to do so, and the design of the STL is such that
your list class only needs proper iterators to fit in.

Regards,
--
Michiel Salters

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

i think the list::splice complexity in 23.2.2.4 para 14 is wrong.
surely it should be always constant time?

this is the "third" splice:
splice(iterator pos, list& x, iterator first, iterator kast)
complexity is listed as:
"Constant time if &x == this; otherwise linear time."

i think it should be: "Constant time."

this will ensure that DR 250 (list::splice shouldn't invalidate
iterators) is correctly implemented for this version of splice too.

(btw. Sun ONE Studio 8 CC (5.5) incorrectly has linear time
splice(iterator, list& x) (and also invalidates the iterators in x).  i
have submitted a bug report to Sun)

cheers,
/lib

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

Bill Clarke wrote:
>
> i think the list::splice complexity in 23.2.2.4 para 14 is wrong.
> surely it should be always constant time?

Only if you don't mind size() being linear. At some point you have to
figure out how many elements you inserted, and that's a linear operation
in general.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]