需求: 比较两个同类型的std::map<key, value>变量是否相同。
实现: 对比流程: 1.size不同,则map不相同。 2.size相同,遍历map1,查找map2中是否存在相同key,不存在则map不相同。 3.存在相同key,比较value是否相同,不同则map不相同。
这里采用模板函数,以支持value的不同类型。如果value是单一类型,可以直接将模板函数具体化。 代码如下:
template<typename K, typename V>
bool CompareMap(const std::map<K, V>& map1, const std::map<K, V>& 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;
}
OK,比较两个map容器是否相同的函数已完成,好像也没啥毛病。再次回顾流程时,忽然发现有个地方被忽略:经过第1步判断后,两个map的size是相同的,因此我们可以直接使用迭代器同时遍历两个map,并比较这两个迭代器所指向的key和value是否相同。为什么可以这样?因为map容器是有序的,按key值从小到大排列 。
调整对比流程: 1.size不同,则map不相同。 2.size相同,同时遍历map1、map2,比较迭代器指向元素的key和value是否相同,只要有一个不同,则map不相同。
代码如下:
template<typename K, typename V>
bool CompareMap(const std::map<K, V>& map1, const std::map<K, V>& 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;
}
这样就可以了。从代码结构看,第二种效率是优于第一种的(最后的完整代码包含时间测试)。
上面完成了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;
}
};
上面定义了结构体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;
}
关于结构体,还有一种比较方式,就是使用memcmp (不推荐,仅作了解)。这时比较value就可以写为:if (0 != memcmp(&it1.second, &it2->second, sizeof(V)))。使用memcmp有些限制:数据成员是基本类型或简单复合类型(char[n]),并且结构体要1字节对齐。如果不是1字节对齐,结构体中被填充的字节部分可能是随机或无效的内容。另外数据成员也不能是自带内存管理类型(如std::string)。以上情况使用memcmp会得到意外的结果。
下面给出完整代码(带时间测试):
#include <iostream>
#include <map>
#include <Windows.h>
struct MapValue
{
int n;
std::string s;
MapValue(int _n = 0, std::string _s = "")
{
n = _n;
s = _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;
}
};
template<typename K, typename V>
bool CompareMap1(const std::map<K, V>& map1, const std::map<K, V>& 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;
}
template<typename K, typename V>
bool CompareMap2(const std::map<K, V>& map1, const std::map<K, V>& 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;
}
int main()
{
std::map<int, MapValue> map1;
std::map<int, MapValue> map2;
for (int i = 0; i < 1000000; ++i)
{
map1[i] = MapValue(1, "123");
map2[i] = MapValue(1, "123");
}
map1[1000000] = MapValue(1, "123");
map2[1000000] = MapValue(1, "1234");
ULONGLONG iTime = 0;
iTime = GetTickCount64();
std::cout << (CompareMap1(map1, map2) ? "map1 == map2" : "map1 != map2") << std::endl;
std::cout << "Time: " << GetTickCount64() - iTime << "ms" << std::endl;
return 0;
}
|