Re: Which is more Efficient in STL ------ SET / MAP ?
On Feb 14, 6:58 pm, Erik Wikstr=F6m <Erik-wikst...@telia.com> wrote:
On 2008-02-14 11:08, James Kanze wrote:
On Feb 13, 7:17 pm, Erik Wikstr=F6m <Erik-wikst...@telia.com> wrote:
On 2008-02-13 08:30, Pallav singh wrote:
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.
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)?
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.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34