why should the SGI set provide the following function

[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?

 

[Alf P. Steinbach]

* 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.


Cheers & hth.,

- Alf

 

[Alf P. Steinbach]

* James Kanze:

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.)

Thanks.

Learned smth new!


Cheers,

- Alf

 

[Michael DOUBEZ]

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.)

From an algorithmic point of view it also allows reusing previous
results. Having read Alexander Stepanov's papers, it wouldn't be surprising.

 

[coal]

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.)

I believe Boost Multi-index uses the hinted version in it's
internal serialization code. However, Boost Serialization
(1.38) doesn't take advantage of the function when dealing
with (multi)set or (multi)map.
http://webEbenezer.net/comparison.html -- see the section
on loading/receiving data.

If someone wanted to marshall a non-sorted
boost::intrusive::list<int> to a std::set<int> it would
probably be better to not use the function that takes
a hint. So I think it makes sense for users to be to
specifiy if they don't want to use the hinted insert
function with these containers.

Brian Wood
Ebenezer Enterprises
www.webEbenezer.net

 

[coal]

I believe Boost Multi-index uses the hinted version in it's
internal serialization code.  However, Boost Serialization
(1.38) doesn't take advantage of the function when dealing
with (multi)set or (multi)map.http://webEbenezer.net/comparison.html-- see the section
on loading/receiving data.

If someone wanted to marshall a non-sorted
boost::intrusive::list<int>  to a std::set<int> it would

Oops. I should say:

class abc : public list_base_hook<>
{
int a_;

};

and then boost::intrusive::list<abc>.


Brian Wood
Ebenezer Enterprises
www.webEbenezer.net