Bradd W. Szonye wrote:
>
> Valentin Bonnard wrote in message <34CF792D.2C52@pratique.fr>...
> >The CD2 says in table 7 of Containners that a.insert(i,j)
> >is linear if [i, j) is ordered. It seems impossible to
> >implement to me, as it means that if [i, j) = [x], insert
> >in an associative containner is O(1) !
>
> Well, it's possible for some trees. For example, any in-order iteration
> over a splay tree is guaranteed O(N), whether for access, insert, or
> delete. And it's not a special-case algorithm; that's just the way they
> work.

In order iteration yes, but you still need to find where you
insert the range [i, j). And if the range is small, or even
has only one element, you get O(1) insertion !

That's my understanding of 'linear', but I have been told that
linear here refer to the size of the containner after the
insertion. That's why I think we shouldn't use 'linear' in a
std but O(size()) or O(size()+N) instead.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

The CD2 says in table 7 of Containners that a.insert(i,j)
is linear if [i, j) is ordered. It seems impossible to
implement to me, as it means that if [i, j) = [x], insert
in an associative containner is O(1) !

IMO it should be

 N+log (size()) if [i,j) is sorted according to value_comp()

FYI: the FDIS says the same thing as CD2,
whereas SGI STL is silent on this special case.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Valentin Bonnard wrote in message <34CF792D.2C52@pratique.fr>...
>The CD2 says in table 7 of Containners that a.insert(i,j)
>is linear if [i, j) is ordered. It seems impossible to
>implement to me, as it means that if [i, j) = [x], insert
>in an associative containner is O(1) !

Well, it's possible for some trees. For example, any in-order iteration
over a splay tree is guaranteed O(N), whether for access, insert, or
delete. And it's not a special-case algorithm; that's just the way they
work.

However, a splay tree does not meet other requirements, such as
guaranteed O(log N) random access. It is only amortized O(log N). I do
wonder whether a standard library would be non-conforming for using a
splay tree to implement the associative containers; they are in the
spirit if not the letter of the requirements.

There's another requirement for associative containers which says
approximately that insert is O(1) if you insert relative to an iterator
immediately before the insertion point in order. The range insert method
apparently takes advantage of this. I'm not sure whether either
requirement is actually feasible for a given tree algorithm; algorithmic
analysis was never my strong point, I'm afraid, beyond the basics. I
just barely get the "telescoping sums" thing.

Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]