std::set: gratuitous comparisons?

Hi,

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):


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.
 


Same weirdness.


This makes sense.


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...

Thanks,
Paul

Testcode:
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>

class Item {
        friend std::ostream &operator<<(std::ostream &out, const Item &i);
protected:
        std::string s;
        int num;
public:
        Item(const char *s_) : s(s_) {
                static int count = 0;
                num = ++count;
                std::cout << s << num << '\n';
        };
        bool operator<(const Item &i) const {
                std::cout << "lt:"
                          << *this << " vs. " << i << ":"
                          << (s < i.s) << '\n';
                return s < i.s;
        };
};

std::ostream &operator<<(std::ostream &out, const Item &i)
{
        return out << i.s << i.num;
}

int main()
{
        std::set<Item> set;
        set.insert(Item("A"));
        set.insert(Item("B"));
        set.insert(Item("C"));
        set.insert(Item("B"));
        set.insert(Item("A"));
        std::cout << "------\n";
        std::copy(set.begin(), set.end(),
                  std::ostream_iterator<const Item>(std::cout, "\n"));
        return 0;
}