On Feb 13, 7:17 pm, Erik Wikstr??m <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).