Re: std::set: gratuitous comparisons?
On 14 mar, 23:00, 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" == true, then "B" < "A" *must* be false. And secondly, "B"
< "A" was already tested before.
Since you've got g++, it's pretty simple to look at the g++
source code and see what is happening. (In the libstdc++ tree,
the actual code is in _M_insert_unique in bits/stl_tree.h.)
Basically, when insert is called, the tree consists of a single
node, with A1 in it. The first comparison tells the code that
the new node goes to the right (or is equal---you can't forget
that). The algorithm then checks the right node, and finds that
it is null. It then does the reverse comparision, to check for
equality---if both return false, then no insertion takes place.
It then calls the function which does the actual insertion,
which does an extra check to determine whether the insertion is
to the left or to the right. (Given the way we arrive here, we
know that it can only be to the right, but the function which
does the insertion may be called from other places as well. But
it's true that it probably could have been spared, at the cost
of some additional code complexity. Or I've possibly misread
the code.)
C3
lt:C3 vs. A1:0
lt:C3 vs. B2:0
lt:B2 vs. C3:1
lt:C3 vs. B2:0
Same weirdness.
B4
lt:B4 vs. B2:0
lt:B4 vs. C3:1
lt:B2 vs. B4:0
This makes sense.
Here, the first two checks find the potential position---the
third tells us that we are equal, so no insertion takes place.
A5
lt:A5 vs. B2:1
lt:A5 vs. A1:0
lt:A1 vs. A5:0
This makes sense too.
So what happened in the first two cases? The only explanation
I can come up with is that some tree balancing (AVL or
red/black?) code kicked in...
The standard requires the tree to be balanced (since it requires
logrithmic complexity), but once you've found the exact postion
of insertion, there's no need for any additional comparisons for
the balancing (and in fact, the balancing code doesn't seem to
be present in the template sources---which makes me think that
it isn't even a template).
There does seem to be one extra comparison in there, that
possibly could be avoided. But don't forget that you do have to
check for equality, and not insert in such cases.
--
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