c++ - 无序 map 比C++中的 map 慢吗？

我正在使用带有map<long, X>的地图
为了调整性能，我决定也尝试无序映射。
我尝试了同时使用operator[]的100k插入。
对于相同的代码，地图花费了约140秒，而无序地图工具花费了约230秒。
我期望unordered_map更快！我是错了还是这里有些可疑？

搜索了以前的答案，但它们都指向更快的unordered_map。因此是一个问题。可以提供更多细节。运行以下基准测试，第一种情况需要约0秒，第二种情况需要8秒。

#include <map>
#include <unordered_map>
#include <iostream>
#include <time.h>
#include <stdlib.h>

using namespace std;

struct X{
   long a, b, c, d, e, f;
   string x, y, z;
};

struct mapZ{
   long id;
   map<long, X> xMap;
};

struct unmapZ{
   long id;
   unordered_map<long, X> xUnMap;
};

unmapZ & addUnMap(unmapZ & um, X & xtmp)
{
    um.xUnMap[xtmp.a] = xtmp;
    return(um);
}

mapZ & addMap(mapZ & mp, X & xtmp)
{
    mp.xMap[xtmp.a] = xtmp;
    return(mp);
}

int main()
{
    int numItr = 10000;
    map<long, X> myMap;
    unordered_map<long, X> myUnMap;
    mapZ mp;
    unmapZ uz;
    uz.id = (long)1;
    uz.xUnMap = myUnMap;
    mp.id = (long)1;
    mp.xMap = myMap;

    time_t start = time(0);

    for(int i = 0; i < numItr; i++)
    {
        long id = (long)rand();
        X tmp;
        tmp.a = id; tmp.b = id; tmp.c = id; tmp.d = id; tmp.e=id; tmp.f=id;
        tmp.x = "ABCDEF"; tmp.y = "WXYZS"; tmp.z = "UVGHJ";
        mp = addMap(mp, tmp);
    }
    cout << "size of map: " << mp.xMap.size() << "\n";
    time_t eof_map = time(0);

    for(int i = 0; i < numItr; i++)
    {
        long id = (long)rand();
        X tmp;
        tmp.a = id; tmp.b = id; tmp.c = id; tmp.d = id; tmp.e=id; tmp.f=id;
        tmp.x = "ABCDEF"; tmp.y = "WXYZS"; tmp.z = "UVGHJ";
        uz = addUnMap(uz, tmp);
    }

    cout << "size of unmap: " << uz.xUnMap.size() << "\n";
    time_t eof_unmap = time(0);

    cout << "Map inset time: " << eof_map - start << "\n";
    cout << "Unord Map insert time: " << eof_unmap - eof_map << "\n";
    return(0);
   }

这是运行基准测试的命令行：

g++ -O3 -std=c++0x -m64 -Wno-write-strings -fopenmp mapTest.cpp

在Ubuntu上运行GCC 4.6。

最佳答案

此基准代码存在许多很多问题，因此其输出无关紧要。

首先，您使用了完全不可靠和糟糕的计时时钟。使用std :: high_performance_clock。

其次，您在示例值类型上填充了许多额外的std :: strings，并将此类型复制到各处。内存分配器的高度可变性（以及您不公平地从非新进程运行一个测试的事实）非常糟糕。

第三，您在基准时间中包含了诸如I / O之类的东西-不，当您输出相同的字符串时，它仍然完全不公平。

第四，rand（）只能产生较小范围的值，这对于unordered_map是不公平的比较。如果您的用例实际上只是一个很小的值范围，则可以通过适当的哈希值更改更好地推出哈希映射。

但是这里的鲸鱼是您的考试是不公平的，因为您是自我分配的。您已将地图和无序地图分配给自己。这是一个不公平的测试，因为旧版map代码中包含自赋值检查，从而使该赋值成为无操作。新的unordered_map代码遵循新的最佳实践，而没有遵循。实际上，您只是为了好玩而多余地复制了unordered_map，并且仅复制了unordered_map数千次，将O（n）更改为O（n ^ 2）或O（n ^ 3）。当然，没有人理智地自我分配，因此这完全使所有结果毫无意义。

关于c++ - 无序 map 比C++中的 map 慢吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22199309/