做系统软件的网站,win2003搭建wordpress,wordpress获取设备参数,网站一键建设我目前手头上的项目#xff0c;需要编译在板端Linux上运行#xff0c;但是日常daily调试多在Windows上开发。这就涉及到同一份代码在多平台上的编译个运行。有一次遇到了一个奇怪的现象#xff1a;跑同样的一份代码#xff0c;Windows和Linux出来的结果是不一致的。最终确定…我目前手头上的项目需要编译在板端Linux上运行但是日常daily调试多在Windows上开发。这就涉及到同一份代码在多平台上的编译个运行。有一次遇到了一个奇怪的现象跑同样的一份代码Windows和Linux出来的结果是不一致的。最终确定到不一致的原因出现在unordered_map上就把这次记录总结下来。
这次不一致发生在处理一个状态序列的投票操作。从编程的角度而言最适合投票操作的容器就是键值对key放置投票的内容value放置投票的次数。在C中STL提供了两个相关容器map和unordered_map。在代码上选择了unordered_map来实现。 问题复现
我把这个问题简化假设车的类型有四种情况分别为UNKNOWN、SMALL、MIDDLE、BIG。现有15次的估计以出现次数最多的类型作为其最终类型。代码非常简单
#include iostream
#include unordered_map
#include stringint main()
{std::unordered_mapstd::string, int vehs;vehs[UNKNOWN] 5;vehs[SMALL] 3;vehs[MIDDLE] 5;vehs[BIG] 2;std::string max_type;int max_times -1;auto iter vehs.begin();for (; iter ! vehs.end(); iter) {if (iter-second max_times) {max_times iter-second;max_type iter-first;}std::cout iter-first ;}std::cout std::endl;std::cout max_type : max_type std::endl;return 0;
}在Windows平台下编译并运行代码
BIG UNKNOWN SMALL MIDDLE
max_type : UNKNOWN在Linux平台下编译并运行代码
BIG MIDDLE SMALL UNKNOWN
max_type : MIDDLE可以看到在Windows和Linux两个平台下的运行结果中出现次数最多的车的类型一个为UNKNOWN一个为MIDDLE。主要原因是这两种类型都是5次最多。这时unordered_map的遍历顺序就很重要了这将直接关系到最终的输出结果。通过打印结果可以看到两个平台下的遍历顺序是不一致的。
在C中STL提供了两个键值对容器map和unordered_map。上面的代码采用的是unordered_map容器如果将其改成map容器呢还会发生这种不一致的结果么
std::mapstd::string, int vehs; // 将unordered_map修改为map此时再在Windows和Linux平台下分别编译并运行代码最终的输出都是一致的
BIG MIDDLE SMALL UNKNOWN
max_type : MIDDLE也就是说这种平台不一致性只发生在unordered_map容器上而不发生在map容器上。 原因分析
map和unordered_map分别在Windows和Linux上的不同运行结果主要体现在遍历顺序上。对于map而言两个平台上的遍历顺序是一致的而对于unordered_map而言两个平台上的遍历顺序是不一致的。
遍历顺序的不同究其根本主要体现在其内部构造的不同
map的内部构造
map的内部实现了一个红黑树红黑树是非严格平衡二叉搜索树而AVL是严格平衡二叉搜索树红黑树具有自动排序的功能因此map内部的所有元素都是有序的。红黑树的每一个节点都代表着map的一个元素。因此对于map进行的查找删除添加等一系列的操作都相当于是对红黑树进行的操作。
unordered_map的内部构造
unordered_map的内部实现了一个哈希表也叫散列表通过把关键码值映射到Hash表中一个位置来访问记录查找的时间复杂度可达到O(1)其在海量数据处理中有着广泛应用。因此其元素的排列顺序是无序的。
两者在运行效率和占用内存的对比
运行效率方面unordered_map最高而map效率较低但提供了稳定效率和有序的序列占用内存方面map内存占用略低unordered_map内存占用略高而且是线性成比例的
需要无序容器快速查找删除不担心略高的内存时可以选择unordered_map需要有序容器稳定查找删除效率内存很在意时候用map。
因此如果需要使用map那么key需要定义operator用于进行有序的排序如果需要使用unordered_map那么key需要定义hash_value函数并且定义operator用于hash值的计算。而
当使用map时Windows和Linux对于operator的定义都是一致的当使用unordered_map时Windows和Linux对于operator的定义都是一致的对于hash_value函数的定义是不一致的
从而在使用unordered_map时Windows和Linux使用两种不同的哈希函数产生不同的哈希码从而依次产生不同的存储区放置导致在迭代时产生不同的顺序。 相关阅读
c - Windows 和 Linux 上 std::unordered_map 容器的不同行为
