By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,423 Members | 1,327 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,423 IT Pros & Developers. It's quick & easy.

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

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

Expand|Select|Wrap|Line Numbers
  1. class tools{
  2.   public:
  3.     tools( ......) {}
  4.     friend bool operator< (const tools& lhs, const tools& rhs)  {
  5.        cout<<"lhs="<<lhs.company<<"."<<lhs.name
  6.               <<" rhs="<<rhs.company<<"."<<rhs.name<<endl;
  7.        return lhs.company < rhs.company;
  8.    }
  9.     friend bool operator== (const tools& lhs, const tools& rhs) {
  10.        cout<<" in op=="<<endl;
  11.        return lhs.company == rhs.company ;
  12.    //note, without &&lhs.name==rhs.name; // line 1
  13.    }
  14.   private:
  15.     string company;
  16.     string name;
  17. };
  18.  
  19.  
in main(),I want to use multiset on user-defined objects:
Expand|Select|Wrap|Line Numbers
  1. tools toolArr[] = {tools("MS", "VC"),
  2.     tools("SUN", "Java"),
  3.     tools("MS", "Word") ,
  4.     tools("Apple", "Mac")
  5.   };
  6.   int Size = sizeof(toolArr)/sizeof(tools);
  7.   multiset<tools> toolSet(toolArr, toolArr+Size);
  8.   string cmpy("MS");
  9.   cout << "There are " <<toolSet.count(tools(cmpy, "SQL"))
  10.     << " " << cmpy << " tools in the set" << endl << endl;
  11.    }
  12.  
What bothers me is that the above program generates the following output:
Expand|Select|Wrap|Line Numbers
  1. lhs=SUN.Java rhs=MS.VC
  2. lhs=SUN.Java rhs=MS.VC
  3. lhs=MS.Word rhs=SUN.Java
  4. lhs=MS.Word rhs=MS.VC
  5. lhs=MS.Word rhs=SUN.Java
  6. lhs=MS.Word rhs=SUN.Java
  7. lhs=Apple.Mac rhs=SUN.Java
  8. lhs=Apple.Mac rhs=MS.Word
  9. lhs=Apple.Mac rhs=MS.VC
  10. lhs=Apple.Mac rhs=MS.VC
  11.  
  12.  
  13. lhs=MS.SQL rhs=MS.Word
  14. lhs=MS.SQL rhs=SUN.Java
  15. lhs=MS.Word rhs=MS.SQL
  16. lhs=MS.VC rhs=MS.SQL
  17. lhs=Apple.Mac rhs=MS.SQL
  18.  
  19. There are 2 MS tools in the set
  20.  
  21.  
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.
Feb 20 '08 #1
Share this Question
Share on Google+
2 Replies


Expert 100+
P: 849
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.
Feb 20 '08 #2

P: 5
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.
Feb 20 '08 #3

Post your reply

Sign in to post your reply or Sign up for a free account.