Which is more Efficient in STL ------ SET / MAP ?

[Pallav singh]

Hi All ,

Which is more Efficient in STL ------ SET / MAP ?

as in SET we can use insert( ) function which allow to insert at a
given Iterator position ( if Element is passed by comparator
function )........I have a Doubt that does not it harm Search time
Complexity in SET???

How are These Both Differ in their Internal Implementation using
Different Type Tree's ??

Thanks

 

[Ian Collins]

Hi All ,

Which is more Efficient in STL ------ SET / MAP ?

Each has its own advantages, so there isn't a simple answer (otherwise,
why have both?). Pick the one that best suits you application and
measure if required.

 

[Jeff Schwab]

Hi All ,

Which is more Efficient in STL ------ SET / MAP ?

as in SET we can use insert( ) function which allow to insert at a
given Iterator position

The position is just a hint.

( if Element is passed by comparator
function )........

How would the comparator ever reject an element? By throwing an exception?

I have a Doubt that does not it harm Search time
Complexity in SET???

The complexity of insertions should be amortized log(N) with the size of
the set. If you consistently give the worst possible hint (e.g. using
set_.begin() to insert elements that belong at the end of the set), I
suppose the complexity might be affected in an implementation-specific
manner. (Or not.)

How are These Both Differ in their Internal Implementation using
Different Type Tree's ??

The implementations are typically identical. In the version of gcc I
have handy at the moment, they are slightly different instantiations of
the same red/black tree template. A std::map<K, V> is very close to
being a std::set<std:air<K, V> >.

The time to worry about performance is once you have working code. At
the very least, you'll want some brutally simple code to use as a golden
model for testing your even-more-brutally sophisticated production code.

 

[Erik Wikström]

Hi All ,

Which is more Efficient in STL ------ SET / MAP ?

Most probably they are equally efficient.

as in SET we can use insert( ) function which allow to insert at a
given Iterator position ( if Element is passed by comparator
function )........I have a Doubt that does not it harm Search time
Complexity in SET???

Why would it? The only difference between inserting using an iterator
and not using it is that if you do you might save some time that would
otherwise been used searching for the position to insert. Notice though
that I said might, there is no guarantee that you save anything,
especially if the iterator points to the wrong place.

How are These Both Differ in their Internal Implementation using
Different Type Tree's ??

I would imagine that on most implementations there is some kind of red-
black tree which is used to store the elements in the set. For map the
same tree is used but instead of storing elements of type T it stores
elements of type std:air, by using another comparator for the map this
becomes invisible for the tree implementation.

 

[James Kanze]

The position is just a hint.

How would the comparator ever reject an element? By throwing
an exception?

The complexity of insertions should be amortized log(N) with
the size of the set. If you consistently give the worst
possible hint (e.g. using set_.begin() to insert elements that
belong at the end of the set), I suppose the complexity might
be affected in an implementation-specific manner. (Or not.)

It shouldn't be. Concerning the complexity of this function,
the standard says "logrithmic in general, but amortized constant
if t is inserted right before p" (t is the element being
inserted, p is the hint). Roughly speaking, the function checks
whether t should be inserted immediately before p, and if not,
simply ignores the hint, and calls the insert without the hint.

 

[James Kanze]

On 2008-02-13 08:30, Pallav singh wrote:

Most probably they are equally efficient.

Why would it? The only difference between inserting using an
iterator and not using it is that if you do you might save
some time that would otherwise been used searching for the
position to insert. Notice though that I said might, there is
no guarantee that you save anything, especially if the
iterator points to the wrong place.

There is a guarantee if the hint is good, i.e. if the insertion
is immediately preceding the hint.

A good example of where this can make a difference is if you
have pre-sorted data. If you have pre-sorted data, and always
pass container.end() as a hint, you fill the collection in O(N),
rather than in O(N ln N).

Of course, unless the collection contains a lot of elements (at
least a couple of thousand), this probably isn't measurable.

 

[Hans Bos]

"James Kanze" <[email protected]> schreef in bericht
....

It shouldn't be. Concerning the complexity of this function,
the standard says "logrithmic in general, but amortized constant
if t is inserted right before p" (t is the element being
inserted, p is the hint). Roughly speaking, the function checks
whether t should be inserted immediately before p, and if not,
simply ignores the hint, and calls the insert without the hint.

That is if t is inserted right after p, not before p.

 

[Jeff Schwab]

It shouldn't be. Concerning the complexity of this function,
the standard says "logrithmic in general, but amortized constant
if t is inserted right before p" (t is the element being
inserted, p is the hint). Roughly speaking, the function checks
whether t should be inserted immediately before p, and if not,
simply ignores the hint, and calls the insert without the hint.

Of course! That makes perfect sense.

 

[Erik Wikström]

There is a guarantee if the hint is good, i.e. if the insertion
is immediately preceding the hint.

A good example of where this can make a difference is if you
have pre-sorted data. If you have pre-sorted data, and always
pass container.end() as a hint, you fill the collection in O(N),
rather than in O(N ln N).

I'll admit that it was some time ago since I last looked at red-black
trees but should they not have to be rebalanced (or something like that)
every once in a while? Or is this where the amortised constant time
comes from (as opposed to constant)?

 

[Kai-Uwe Bux]

I'll admit that it was some time ago since I last looked at red-black
trees but should they not have to be rebalanced (or something like that)
every once in a while? Or is this where the amortised constant time
comes from (as opposed to constant)?

It might be that the O(N) vs O(N ln N) comes from counting different things.
With the hint, you are saving on comparisons. You are not saving on
rebalancing operations (pointer shuffling). If I recall correctly, the
complexity guarantees of the standard refer to the operations incurred on
the value_type of the container (e.g., copy-constructor calls, assignments,
comparisons); but there are no bounds on the number of internal operations
(like pointer assignments to rebalance a tree).


Best

Kai-Uwe Bux

 

[James Kanze]

I'll admit that it was some time ago since I last looked at
red-black trees but should they not have to be rebalanced (or
something like that) every once in a while? Or is this where
the amortised constant time comes from (as opposed to
constant)?

Well, a red-black tree is always more or less balanced, but
you're right that you do occasionally have to do some pointer
swapping on insertion. As Kai-Uwe pointed out, the complexity
requirement in the standard is expressed in terms of operations
on the object, and pretty much ignores such internal
housekeeping.