why should the SGI set provide the following function
hpsoar
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
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
--
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
to it is even better! Thanks in advance!
Martin Eisenberg
It's called insert with a hint and is among the standard's
requirements on associative containers. You use it when you know that
the hint's target value and the value(s) you're about to insert will
all be consecutive in the sequence. See table 7 in
http://std.dkuug.dk/jtc1/sc22/wg21/docs/wp/html/nov97-2/lib-containers.html#lib.associative.reqmts .
Martin
--
Quidquid latine scriptum est, altum videtur.
James Kanze
> * 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.)
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Alf P. Steinbach
> 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.)
Thanks.
Learned smth new! :)
Cheers,
Pete Becker
The iterator provides a hint to the implementation as to where the item
might go. If the hint is right, the implementation doesn't have to do
as large a search to find where to insert the item.
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)
Michael DOUBEZ
From an algorithmic point of view it also allows reusing previous
results. Having read Alexander Stepanov's papers, it wouldn't be surprising.
--
Michael
co...@mailvault.com
> 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
co...@mailvault.com
> On Mar 31, 5:33 am, James Kanze <james.ka...@gmail.com> wrote:
>
> > 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
> 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>.