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

parv · 02-19-2008, 08:58 PM

Thanks for your patience to read the entire post to understand my
confusion

I have the user-defined class "tools":

Code:

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:

Code:

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:

Code:

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.

ntubski · 02-19-2008, 09:53 PM

The multiset sorts the elements that you put into it. See http://www.sgi.com/tech/stl/multiset.html, in particular note that the default for Compare is less<Key>, and that it should have a Strict Weak Ordering. I think your operator< does not since (tool1 < tool2) would compare a different set of strings than (tool2 < tool1).

parv · 02-19-2008, 10:48 PM

Quote:

Originally Posted by ntubski

The multiset sorts the elements that you put into it. See http://www.sgi.com/tech/stl/multiset.html, in particular note that the default for Compare is less<Key>, and that it should have a Strict Weak Ordering. I think your operator< does not since (tool1 < tool2) would compare a different set of strings than (tool2 < tool1).

Thanks. But can you elaborate what you meant by 'I think your operator< does not since (tool1 < tool2) would compare a different set of strings than (tool2 < tool1)"?

In addition, what about operator==? what does count() actually do?
It should take Key which an object of tools and then look it up in the underlying
RB-tree, right? I just cannot understand why tools("MS", "SQL") and tools("MS", "VC")
are considered equal to each other. My plain thinking is equality should be involved in count().
Maybe I am dead wrong.

parv · 02-20-2008, 03:54 PM

Got it. It was due to strict weak ordering used by multiset
which is defined by operator<.
The current operator< used by class tools is saying as long as
two objects have the same "company" string, they are equal.
So by changing operator<, I could see the difference.

ntubski · 02-20-2008, 03:57 PM

edit: Oh, I see you've figured it out already.

Quote:

Originally Posted by parv

Thanks. But can you elaborate what you meant by 'I think your operator< does not since (tool1 < tool2) would compare a different set of strings than (tool2 < tool1)"?

Consider

Code:

tools tool1("aa", "bb"), tool2("ab", "ab");
tool1 < tool2 //does ("aa" < "ab") result is true
tool2 < tool1 //does ("ab" < "bb") result is true

As you can see according to your operator< tool1 is less than tool2 and tool2 is less than tool1, kind of like an M.C. Escher painting...

Quote:

In addition, what about operator==? what does count() actually do?
It should take Key which an object of tools and then look it up in the underlying
RB-tree, right? I just cannot understand why tools("MS", "SQL") and tools("MS", "VC")
are considered equal to each other. My plain thinking is equality should be involved in count().
Maybe I am dead wrong.

The multiset makes the minimum assumptions about your type, so it only uses operator< not operator==. Since your operator< behaves strangely, functions like count() don't work right.

parv · 02-20-2008, 07:12 PM

Quote:

Originally Posted by ntubski

edit: Oh, I see you've figured it out already.

Consider

Code:

tools tool1("aa", "bb"), tool2("ab", "ab");
tool1 < tool2 //does ("aa" < "ab") result is true
tool2 < tool1 //does ("ab" < "bb") result is true

As you can see according to your operator< tool1 is less than tool2 and tool2 is less than tool1, kind of like an M.C. Escher painting...

The multiset makes the minimum assumptions about your type, so it only uses operator< not operator==. Since your operator< behaves strangely, functions like count() don't work right.

I cannot quite get why tool2 < tool1 also returns true because I think what happens
is: return string("ab") < string("aa"). I don't know why it should do "ab" < "bb", assuming
you meant they are actually strings, not char[]. In the function operator<, the second field,
i.e., name, is not used at all.

I changed function operator< to this and it seems work the way I preferred:

Code:

return lhs.company < rhs.company || (lhs.company == rhs.company && lhs.name < rhs.name) ;

ntubski · 02-20-2008, 10:19 PM

Quote:

Originally Posted by parv

I cannot quite get why tool2 < tool1 also returns true ...

Sorry, I misread the code, got confused with which part was printing, and which was comparing (everything uses <'s). You are right about how it works.