Unordered_map vs vector

Question

我正在构建一个小的2D游戏引擎。现在我需要存储游戏对象的原型（所有类型的信息）。一个容器最多我猜几千个元素都有唯一的键，没有元素将被删除或在第一次加载后添加。键值是一个字符串。

将运行各种线程，并且我需要向每个人发送一个键（或索引）并且具有该访问权限的其他信息（例如用于渲染过程的纹理或用于混合器过程的声音）仅可用于那些线程。

通常我使用向量，因为它们访问已知元素的速度更快。但我发现，如果我使用::at元素访问，无序地图通常也会保持恒定速度。这将使代码更清晰，也更容易维护，因为我将处理更易理解的人造字符串。

所以问题是，与vector[n]相比，获得unorderedmap.at("string")的速度与他的收益相比可以忽略不计？

根据我的理解，在程序的不同部分访问各种地图，不同的线程只为我运行“名称”是一个大问题，速度差异不是那么大。但我太缺乏经验，无法确定这一点。虽然我发现有关它的信息似乎我无法理解我是对还是错。

感谢您的时间。

Answer 1

作为替代方案，您可以考虑使用有序向量，因为向量本身不会被修改。您可以使用STL lower_bound等轻松编写实现，或使用库中的实现（ boost::flat_map）。

在这种情况下，有一个关于集装箱性能的blog post from Scott Meyers。他做了一些基准，结论是unordered_mapis可能是一个非常好的选择，很有可能它将是最快的选择。如果您有一组受限制的密钥，您还可以计算最小的最佳散列函数，例如with gperf

但是，对于这些问题，首要的规则是衡量自己。

Answer 2

我的问题是通过给定的std :: string类型找到容器上的记录作为密钥访问。考虑只有EXISTS的键（没有找到它们的选项），并且该容器的元素仅在程序开始时生成，之后从未触及。

我有巨大的恐惧无序地图不够快。所以我测试了它，我希望分享结果，希望我没有弄错所有事情。我只是希望能帮助像我这样的人并得到一些反馈，因为最后我是初学者。因此，给定一个随机填充的记录结构，如下所示：

struct The_Mess 
{   
    std::string A_string;
    long double A_ldouble;
    char C[10]; 
    int* intPointer;
    std::vector<unsigned int> A_vector;
    std::string Another_String;
}        

我做了一个无序的地图，给A_string包含记录的密钥：

std::unordered_map<std::string, The_Mess> The_UnOrdMap;

和一个矢量我按A_string值排序（包含键）：

std::vector<The_Mess> The_Vector;

还有一个索引向量排序，并用于访问第3方式：

std::vector<std::string> index;

密钥将是一个长度为0-20个字符的随机字符串（我希望最糟糕的情况）包含大写字母和普通字母以及数字或空格。

所以，简而言之，我们的竞争对手是：

1. 无序映射我测量程序执行的时间： record = The_UnOrdMap.at( key );记录只是一个The_Mess结构。
2. Sorted Vector测量语句：

   low = std::lower_bound (The_Vector.begin(), The_Vector.end(), key, compare);
    record = *low;

3. 排序索引向量：

   low2 = std::lower_bound( index.begin(), index.end(), key);
    indice = low2 - index.begin();
    record = The_Vector[indice];

时间以纳秒为单位，是200次迭代的算术平均值。我有一个向量，我在包含所有键的每次迭代中都会随机播放，并且在每次迭代中我都循环遍历它，并以三种方式查找我在这里的键。所以这是我的结果：

我认为首字母尖峰是我的测试逻辑的错误（我迭代的表只包含到目前为止生成的密钥，所以它只有1-n个元素）。因此，首次进行了200次迭代的1键搜索。 2个键的200次迭代第二次搜索等...

无论如何，似乎最好的选择是无序映射，考虑到代码少得多，它更容易实现，并且使整个程序更容易阅读并可能维护/修改。

Answer 3

你也必须考虑缓存。在std::vector的情况下，当访问元素时，你将具有非常好的缓存性能 - 当访问RAM中的一个元素时，CPU将缓存附近的内存值，这将包括std::vector的附近部分。

当你使用std::map（或std::unordered_map）时，这已不再适用。映射通常实现为self balancing binary-search trees，在这种情况下，值可以分散在RAM周围。这对缓存性能造成了极大的打击，特别是当地图变得越来越大，因为CPU无法缓存您即将访问的内存。

您必须运行一些测试并测量性能，但缓存未命中会严重影响程序的性能。

Answer 4

您最有可能获得相同的性能（差异无法衡量）。

与某些人似乎相信的相反，unordered_map不是二叉树。底层数据结构是一个向量。因此，缓存局部性在这里无关紧要 - 它与矢量相同。当然，如果你因为散列函数不好而发生了碰撞，你将会受苦。但是如果你的密钥是一个简单的整数，那就不会发生。因此，对哈希映射中元素的访问与对向量中元素的访问完全相同，并且花费时间来获取整数的哈希值，这实际上是不可测量的。