c++中map和unordered_map的性能差异
我有一个简单的要求，我需要一个地图的类型。然而，我需要理论上最快的检索时间。
我使用了map和来自tr1的新提议的unordered_map，我发现至少在解析文件和创建map时，通过一次插入一个元素。
map只用了2分钟，而unordered_map用了5分钟。
因为它将是在Hadoop集群上执行的代码的一部分，并且将包含大约1亿个条目，所以我需要尽可能少的检索时间。
还有另一个有用的信息:当前插入的数据(键)是从1,2，...增加到约1000万。
我还可以强制用户指定最大值并使用上面的顺序，这会对我的实现产生重大影响吗？(我听说map是基于rb树的，按递增顺序插入会带来更好的性能(或者更糟？)
以下是代码
map<int,int> Label // this is being changed to unordered_map
fstream LabelFile("Labels.txt");
// Creating the map from the Label.txt
if (LabelFile.is_open())
{
while (! LabelFile.eof() )
{
getline (LabelFile,inputLine);
try
{
curnode=inputLine.substr(0,inputLine.find_first_of("\t"));
nodelabel=inputLine.substr(inputLine.find_first_of("\t")+1,inputLine.size()-1);
Label[atoi(curnode.c_str())]=atoi(nodelabel.c_str());
}
catch(char* strerr)
{
failed=true;
break;
}
}
LabelFile.close();
}试探性的解决方案:在查看评论和答案之后，我认为动态C++数组将是最好的选择，因为实现将使用密集键。谢谢
回答 2
Stack Overflow用户
发布于 2012-06-22 01:49:41
加载unordered_map的额外时间是由于动态调整数组大小造成的。调整大小的计划是，当表格超过其负载因子时，每个单元格的数量都会增加一倍。因此，从一个空表中，预期整个数据表的副本为O(lg )个。您可以通过预先调整哈希表的大小来消除这些额外的副本。具体来说
Label.reserve(expected_number_of_entries / Label.max_load_factor());除以max_load_factor是为了计算哈希表运行所必需的空单元格。
Stack Overflow用户
发布于 2010-02-28 14:12:33
unordered_map (至少在大多数实现中)提供了快速的检索，但与map相比插入速度相对较慢。当数据被随机排序时，树通常处于最佳状态，而当数据被排序时，树处于最差状态(不断地在树的一端插入，增加了重新平衡的频率)。
假设总共有大约1000万个条目，您可以分配一个足够大的数组，并获得真正快速的查找--假设有足够的物理内存，它不会导致颠簸，但按照现代标准，这并不是一个巨大的内存量。
编辑:是的，向量基本上是一个动态数组。
Edit2:你添加了一些问题的代码。你的while (! LabelFile.eof() )坏了。你通常想要做一些像while (LabelFile >> inputdata)这样的事情。您读取数据的效率也有些低--您显然期望的是由制表符分隔的两个数字。在这种情况下，我会编写类似这样的循环：
while (LabelFile >> node >> label)
Label[node] = label;https://stackoverflow.com/questions/2350248
复制相似问题