pls help to explain stl multiset's behavior for user-defined objec

[parvtb]

Thanks for your patience to read the entire post to understand my
confusion I have the user-defined class "tools":

class tools{
  public:
    tools( ......) {}
    friend bool operator< (const tools& lhs, const tools& rhs)  {
       cout<<"lhs="<<lhs.company<<"."<<lhs.name
              <<" rhs="<<rhs.company<<"."<<rhs.name<<endl;
       return lhs.company < rhs.company;
   }
    friend bool operator== (const tools& lhs, const tools& rhs) {
       cout<<" in op=="<<endl;
       return lhs.company == rhs.company ;
   //note, without &&lhs.name==rhs.name; // line 1
   }
  private:
    string company;
    string name;
};

in main(),I want to use multiset on user-defined objects:

tools toolArr[] = {tools("MS", "VC"),
    tools("SUN", "Java"),
    tools("MS", "Word") ,
    tools("Apple", "Mac")
  };
  int Size = sizeof(toolArr)/sizeof(tools);
  multiset<tools> toolSet(toolArr, toolArr+Size);
  string cmpy("MS");
  cout << "There are " <<toolSet.count(tools(cmpy, "SQL"))
    << " " << cmpy << " tools in the set" << endl << endl;
   }

What bothers me is that the above program generates the following output:

lhs=SUN.Java rhs=MS.VC
lhs=SUN.Java rhs=MS.VC
lhs=MS.Word rhs=SUN.Java
lhs=MS.Word rhs=MS.VC
lhs=MS.Word rhs=SUN.Java
lhs=MS.Word rhs=SUN.Java
lhs=Apple.Mac rhs=SUN.Java
lhs=Apple.Mac rhs=MS.Word
lhs=Apple.Mac rhs=MS.VC
lhs=Apple.Mac rhs=MS.VC


lhs=MS.SQL rhs=MS.Word
lhs=MS.SQL rhs=SUN.Java
lhs=MS.Word rhs=MS.SQL
lhs=MS.VC rhs=MS.SQL
lhs=Apple.Mac rhs=MS.SQL

There are 2 MS tools in the set

First of all, how come the operator== is not called at all? How could it be
possible that object tools("MS","SQL ") is considered equal to tools("MS","VC" )?
Please take a look at "line 1", I intentionally did not compare their names to
make them different. But it did not matter. I thought count() should return 0,
but apparently it returns 2.

Second, why is the operator< called so many times? For instance,
lhs=SUN.Java rhs=MS.VC
lhs=SUN.Java rhs=MS.VC
is printed twice in a row which indicates operator< was called twice.
What's actually happening behind STL's multiset?

Is search tree the underlying data structure of multiset?

Struggled on this for quite a while.
Really appreciate your explanation of what's going on here.

[Laharl]

Multiset, like set, uses a red-black tree, which is a faster variation on the binary search tree we all know and love. This would be an n-ary tree rather than a binary tree, but the idea is similar.

[parvtb]

yeah, I figured out it uses RB-tree.
But my main doubt is how the == operator works.
In my case, each Key inserted into the multiset is an object.
I've defined my own == operator to compare two objects.
Well, it is not used by the program obviously.
So it boils down to why the == operator comes with multiset
decides the two objects, tools("MS", "SQL") and tools("MS", "VC"),
equal to each other.