C++漫游记 (2)：C++比较两个map是否相同

需求：
比较两个同类型的std::map变量是否相同。

实现：
对比流程：
1.size不同，则map不相同。
2.size相同，遍历map1，查找map2中是否存在相同key，不存在则map不相同。
3.存在相同key，比较value是否相同，不同则map不相同。

这里采用模板函数，以支持value的不同类型。如果value是单一类型，可以直接将模板函数具体化。
代码如下：

template
bool CompareMap(const std::map& map1, const std::map& map2)
{
    if (map1.size() != map2.size())
    {
        return false;
    }

    for (auto iter1 : map1)
    {
        auto iter2 = map2.find(iter1.first);
        if (iter2 == map2.end())
        {
            return false;
        }
        else
        {
            if (iter1.second != iter2->second)
            {
                return false;
            }
        }
    }

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

OK，比较两个map容器是否相同的函数已完成，好像也没啥毛病。再次回顾流程时，忽然发现有个地方被忽略：经过第1步判断后，两个map的size是相同的，因此我们可以直接使用迭代器同时遍历两个map，并比较这两个迭代器所指向的key和value是否相同。为什么可以这样？因为map容器是有序的，按key值从小到大排列。

调整对比流程：
1.size不同，则map不相同。
2.size相同，同时遍历map1、map2，比较迭代器指向元素的key和value是否相同，只要有一个不同，则map不相同。

代码如下：

template
bool CompareMap(const std::map& map1, const std::map& map2)
{
    if (map1.size() != map2.size())
    {
        return false;
    }

    auto iter1 = map1.begin();
    auto iter2 = map2.begin();
    for (; iter1 != map1.end(); ++iter1, ++iter2)
    {
        if (iter1->first != iter2->first || iter1->second != iter2->second)
        {
            return false;
        }
    }

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这样就可以了。从代码结构看，第二种效率是优于第一种的（最后的完整代码包含时间测试）。

上面完成了map的比较函数，还剩下value的比较，即上面代码中的iter1.second != iter2->second、iter1->second != iter2->second。如果value的类型是int、std::string、结构体、类等，只要支持 != 运算（另外还有 == 运算，一般同时实现，不过上面没用到），就可以直接使用。如果不支持，则需要重载 != 运算。

下面以结构体为例（类也是一样）。

struct MapValue
{
    int n;
    std::string s;

    bool operator==(const MapValue& _Value) const
    {
        return n == _Value.n && s == _Value.s;
    }

    bool operator!=(const MapValue& _Value) const
    {
        return n != _Value.n || s != _Value.s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

上面定义了结构体MapValue，同时重载了实现了 == 和 != 运算。如果重载运算符放在结构体外，则为：

struct MapValue
{
    int n;
    std::string s;
};

bool operator==(const MapValue& _Value1, const MapValue& _Value2)
{
    return _Value1.n == _Value2.n && _Value1.s == _Value2.s;
}

bool operator!=(const MapValue& _Value1, const MapValue& _Value2)
{
    return _Value1.n != _Value2.n || _Value1.s != _Value2.s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

关于结构体，还有一种比较方式，就是使用memcmp（不推荐，仅作了解）。这时比较value就可以写为：if (0 != memcmp(&it1.second, &it2->second, sizeof(V)))。使用memcmp有些限制：数据成员是基本类型或简单复合类型（char[n]），并且结构体要1字节对齐。如果不是1字节对齐，结构体中被填充的字节部分可能是随机或无效的内容。另外数据成员也不能是自带内存管理类型（如std::string）。以上情况使用memcmp会得到意外的结果。

下面给出完整代码（带时间测试）：

// CompareMap.cpp
//

#include 
#include 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96