无序映射与向量

Question

我正在构建一个小型 2d 游戏引擎。现在我需要存储游戏对象的原型（所有类型的信息）。一个容器，我猜最多只有几千个元素，所有元素都具有唯一键，并且在第一次加载后不会删除或添加任何元素。键值为字符串。

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

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

那么问题来了，一个vector[n]和一个unorderedmap.at("string")的访问速度上的差异，和他的好处相比可以忽略不计？

根据我的理解，在程序的不同部分访问各种地图，使用不同的线程运行ning 只是 "name" 对我来说是一个大问题，速度差异不是那个伟大的。但我太缺乏经验，无法确定这一点。虽然我找到了相关信息，但我真的无法理解我是对还是错。

感谢您的宝贵时间。

Answer 1

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

附近的部分

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

您必须运行进行一些测试和衡量性能，但是 缓存未命中 会极大地损害程序的性能。

Answer 2

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

与某些人似乎相信的相反，unordered_map 不是二叉树。底层数据结构是一个向量。因此，缓存位置在这里并不重要——它与矢量相同。诚然，如果由于散列函数不好而发生碰撞，您将会受苦。但是，如果您的密钥是一个简单的整数，则不会发生这种情况。因此，访问 hash map 中的元素将与访问 vector 中的元素完全相同，并且花费时间来获取整数的哈希值，这确实是不可测量的。

Answer 3

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

有个blog post from Scott Meyers about container performance in this case. He did some benchmarks and the conclusion would be that an unordered_mapis probably a very good choice with high chances that it will be the fastest option. If you have a restricted set of keys, you can also compute a minimal optimal hash function, e.g. with gperf

但是，对于这类问题，首先要衡量自己。

Answer 4

我的问题是通过给定的 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包含记录的key：

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

和我按 A_string 值（包含键）排序的向量：

std::vector<The_Mess> The_Vector;

还有一个排序的索引向量，用于作为第三种方式访问：

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

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

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

无序映射我测量程序开始执行的时间：

record = The_UnOrdMap.at( key ); 记录只是一个 The_Mess 结构。
排序向量测量语句：

low = std::lower_bound (The_Vector.begin(), The_Vector.end(), key, compare); record = *low;
排序索引向量：

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

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

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

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

无序映射与向量

Unordered map vs vector

c++

unordered-map

vector

c++11