Re: std::set: gratuitous comparisons?
On Mar 14, 3:00 pm, Paul Brettschneider <paul.brettschnei...@yahoo.fr>
wrote:
I wrote a little code snippet (see end of posting) to see what kind of
comparisons are made when inserting into a std::set container. The members=
are a class wrapped around std::string with an internal counter to
differentiate between multiple instantiations of the class (but only the
string value is compared). For the insertion
sequence "A", "B", "C", "B", "A" I get the following comparisons (on g++
4.1):
A1
B2
lt:B2 vs. A1:0
lt:A1 vs. B2:1
lt:B2 vs. A1:0
Huh? This is strange for two reasons: first of all, if "A" < "B" == tr=
ue,
then "B" < "A" *must* be false. And secondly, "B" < "A" was already tested=
before.
The set's insertion routine performs a binary search of the set's
contents in order to find the proper insertion point for the item
being inserted. So the comparisons observed above - match the
comparisons performed by a binary search. In particular, the results
of the last two comparisons (true and false) are exactly the results
expected when the search has found the two elements (one higher, one
lower) between which the item will be inserted. Naturally, when
performing a binary search in a set with only one or two elements, it
is quite likely that same object will be involved in more than one of
the search's comparisons.
So, when performing a binary search in a set that contains only one or
two objects, it would in fact be possible to eliminate one of these
redundant comparisons. But there would be little point in doing so -
because this optimization is so small and so infrequent - that merely
testing for small sets would add more overhead (and complexity) to the
set's insertion routine in all cases - than could possibly be
recouped by applying the optimization in the two special cases.
Greg