c++ - 如何为包含映射的结构编写比较运算符？

Question

我有这样的结构:

   struct MyStruct
    {

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

我有另一张 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;
        }
    }

那么我应该如何为 mymap 编写比较？

这基本上就是我想要的:

如果

两个映射相等

1. 名称相同

2. 他们的 map 大小相等

3. 那么 map 的内容应该相等，即它们的键和值。

Answer 1

您可以通过多种方式订购 map 。必须考虑三件事:映射的大小、键和值。由于映射本身已经按键排序，因此比较键后的值是很自然的。因此，给定两个相同大小的 map ，只有键才是重要的。我将使用整数键和值作为一个更简单的示例:

 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

现在，比较 map1 和 map2 很容易:map1 的第一个键低于 map2 的第一个键，因此 map1 应该在前。
比较 map1 和 map3 在第一个条目中给出相同的键，但是 map1 对应的值较低，因此 map1 再次排在第一位。
比较 map1 和 map4 发现第一个键值对完全相同，但是比较第二对发现 map1 排在第一位，因为它的值又低了。

按大小排序又是微不足道的。尺寸较小的 map 排在尺寸较大的 map 之前。

现在完全取决于您，是先按大小排序还是先按键/值排序。 考虑一张额外的 map :

map5: 5->16
      7-> 3

map5 的大小是 2，map1 的大小是 3。所以如果你先按大小排序，map5 在 map1 之前。如果先比较元素，则 map1 在 map5 之前，因为第一个元素较低。

此比较已在 C++ 中可用:std::pair提供一个 operator<首先比较键，然后比较值。一般来说，元素集合的逐元素比较是通过 std::lexicographical_compare 完成的。 .此外，std::map提供一个 operator<为你做字典比较。它首先比较元素，其次比较大小。

但是，在您的情况下，因为您使用的是 char* s 而不是 C++ 的 string s，你必须为 pair<char*, char*> 编写自己的比较器这是你的 map 的元素。我建议一起使用字符串，它变得非常简单，因为 std::string提供一个 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); 
  }
};