Re: The design and evolution of STL containers, the case of std::map.size()

From:

Carl Barron <cbarron413@adelphia.net>

Newsgroups:

comp.lang.c++.moderated

Date:

Tue, 11 Mar 2008 01:45:24 CST

Message-ID:

<100320082050063559%cbarron413@adelphia.net>

In article
<62ac54c7-5390-48ac-bc8f-74d6305b1c22@d4g2000prg.googlegroups.com>,
Greg Herlihy <greghe@mac.com> wrote:

while the third must provide constant-time
complexity - save for one, linear-time exception. (The one,
pathological exception is made when a program splices a range of list
elements into the same list in which the elements already reside. In
this bizarre case, an implementation of splice() would have to iterate
the range of elements being inserted in order to determine whether the
insertion point lies within the range of items being inserted.

   No this case requiires no change in size so its const time , The
standard [list.ops] states in 2521.pdf
<quote>
void splice(const_iterator position, list<T,Allocator>&& x, iterator
first,
iterator last);
[snip]
Requires: [first, last) is a valid range in x. The result is undefined
if position is an iterator in the range
[first,last).
</quote>
    If the insertion pt is in the moved range then the result is
undefined, no need to check. Complexity is const. time unless
a range is spliced from one list to another list and then it depends on
the complexity of size(). [one of these, this case of splice() or
size() is linear time,]

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]