c++ - C++中的map和unordered_map之间的性能差异

我有一个简单的要求，我需要一个type的映射。但是我需要理论上最快的检索时间。

我同时使用了 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++数组将是最佳选择，因为实现将使用密集键。谢谢

最佳答案

unordered_map的插入应为 O(1)，检索应大致为 O(1)(其本质上是一个哈希表)。

结果，您的计时方式为 OFF ，或者您的unordered_map的实现或用法有些 WRONG 。

您需要提供更多信息，以及可能如何使用容器。

根据n1836的6.3节，给出了插入/重新插入的复杂性:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf

您应该考虑的一个问题是，您的实现可能需要不断地重新哈希结构，因为您说您有超过1千万个项目。在这种情况下，实例化容器时，如果您对要在容器中插入多少个“唯一”元素有一个大概的了解，可以将其作为参数传递给构造函数，然后将使用bucket-实例化该容器-适当大小的表格。

关于c++ - C++中的map和unordered_map之间的性能差异，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2350248/