On Mar 31, 7:40 am, "Alf P. Steinbach" <al...@start.no> wrote:
* hpsoar:
I'm reading a book on STL, It provides many source codes of
STL's SGI implementation. I found the following function in
class set: iterator
insert(iterator position, const value_type& x);
As I know, the position of a value inserted to is determined
by the red-black tree, which is used when implementing class
set. So why should it provide this function here?
This looks like an internal implementation detail.
At some level of implementation an item has to be inserted at
some specific position in the internal data structure
(whatever that structure is), and naturally there must be some
code for that -- used internally.
It's not something that you should be concerned with as a user.
It's specified in the standard as part of the interface.
Basically, it guarantees amortised constant time if the new
element is inserted immediately after the element designated by
the first parameter, rather than the logrithmic time for other
inserts. I suspect that it's major use is when initializing a
set with already sorted data; using this version of insert, the
initialization is O(n), rather than O(n lg n). (And I suppose
that somewhere, there are even applications where this makes a
difference. Even if I've never seen one.)
Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
No ads, and there is some C++ stuff! :-) Just going there is good. Linking