how to write a comparison operator for struct containing map?

Question

I have structure like :

   struct MyStruct
    {

    char *name;
    map<char*,char*> mymap;//assume that this map insert data in increasing order
    };

I have another map :

    map<MyStruct,int,Compare> mTest;

    //compare function for less then operator
    struct Compare
    : public std::binary_function<MyStruct, MyStruct, bool>
    {
        bool operator()(const MyStruct &a, const MyStruct&b)
        {
            if(strcmp(a.name,b.name)< 0)
                return true;
            else if(strcmp(a.name,b.name)==0)
            {
                //How should I compare map `mymap` ??
            }
            return false;
        }
    }

So How should I write compare for mymap ?

This is what basically I want :

Two maps are equal if

1. there name are equal

2. Their maps size are equal

3. then content of map should be equal i.e both their key and value.

Answer 1

There are several ways you can order maps. Three things have to be taken into account: size of the maps, the keys, and the values. Since a map itself ordered by the keys already, it's only natural to compare values after keys. So, given two maps of the same size, only the keys will matter. I will use integer keys and values for an easier example:

 map1: 1->42       map2: 5->16     map3: 1->44   map4: 1->42
       2-> 5             6->16           2->67         2-> 7
       7-> 8             7-> 8           3->10         7-> 8

Now, comparing map1 and map2 is easy: the first key of map1 is lower than the first key of map2, so map1 should come first.
Comparing map1 and map3 gives the same key in the first entry, but the corresponding value is lower for map1, so map1 comes first again.
Comparing map1 and map4 shows that the first key-value pair is entirely the same, but comparing the second pair shows that map1 comes first, because its value is lower again.

The order by size is trivial again. A map with smaller size comes before one with bigger size.

Now it is completely up to you, if you want to sort by size first or by key/values first. Consider an additional map:

map5: 5->16
      7-> 3

The size of map5 is 2, the size of map1 is 3. So if you order by size first, map5 comes before map1. If you compare the elements first, map1 comes before map5, because the first element is lower.

This comparison is already available in C++: std::pair provides an operator< that compares keys first and values after. The element-wise comparison of a collection of elements in general is done vía std::lexicographical_compare. In addition, std::map provides an operator< that does the lexicographical comparison for you. It compares elements first, sizes second.

However, in your case, since you are using char*s instead of C++'s strings, you'd have to write your own comparator for the pair<char*, char*> which are the elements of your map. I'd advice using strings alltogether, the it becomes very straightforward, because std::string provides an operator<:

struct MyStruct
{
  string name;
  map<string, string> mymap;
};


map<MyStruct,int,Compare> mTest;

//compare function for less then operator
struct Compare
{
  bool operator()(const MyStruct &a, const MyStruct&b)
  {
    return a.name < b.name //name first
      || (a.name == b.name && cmp(a.mymap, b.mymap));
  }

  bool cmp(map<string, string> const& lhs, map<string, string> const& rhs)
  {
    return lhs.size() < rhs.size() //size first
      || (lhs.size() == rhs.size() && lhs < rhs); 
  }
};

Answer 2

Your use of char* is frankly horrible and outdated. Use std::string, your class becomes:

struct MyStruct
{
  std::string name;
  map<std::string, std::string> mymap;
};

Now, for a map, you need to provide the less-than operator, for example:

struct MyStruct
{
  std::string name;
  map<std::string, std::string> mymap;

  friend bool operator<(MyStruct const& lhs, MyStruct const& rhs)
  {
    // Now the comparison is easier - use the defaults!
    if (lhs.name < rhs.name)
      return true;
    return lhs.mymap < rhs.mymap; // this does a lexicographical comparison of all values.
  }
};

Then your map of structures becomes:

std::map<MyStruct, int> mTest;

No need for cumbersome code.

EDIT: Just noticed your update, you can implement the other operators for MyStruct and compose them as I've done above from calling the logical operators of name and mymap, you don't need to implement any custom hacks yourself.