std::unordered_map包含另一个std::unordered_map？

Question

我们正在c++为学校做一个游戏项目。我负责地图对象，它将包含炸弹、播放器、墙壁和盒子等实体。我的地图上有三个容器：

• 一个std：：名单的球员(多个球员可以站在同一情况)。
• 墙壁用的std::unordered_map<int, std::unordered_map<int, AEntity*> >。
• 另一个用于std::unordered_map<int, std::unordered_map<int, AEntity*> >的bombs+boxes。

目的是为了快速访问地图上的实体，实体数量可以非常多。

这就是我为什么想到unordered_maps的原因，我计划以这样的方式使用它们：

Unordered_map A contain:
  KEY: y coord of the Entity || VALUE: pointer to unordered_map B

Unordered_map B contain:
  KEY: x coord of the entity || VALUE: pointer to the AEntity instance

问题1：

首先，对于这种用法，unordered_maps有那么快吗？我对unordered_maps非常陌生。

问题2：

第二，这是添加元素的可行方法吗？

int main(int ac, char **av)
{
   std::unordered_map <int, unordered_map <int, char*>> umap;

   (umap[4])[2] = "salut";
   std::cout << (umap[4])[2] << std::endl;
}

Answer 1

std::unordered_map是根据哈希表实现的，而std::map是根据树实现的。这意味着对于unordered_map来说，访问通常是O(1)，对于std::map来说，它是O(log )。这两者之间有很多不同之处，如果您不知道这些差异，我建议看一本数据结构手册，但是这里有几个：

对于std::unordered_map

• 分配一个连续的内存数组，您可以使用reserve()来防止在不合适的时刻调整大小，但是由于哈希表的性质，这将总是分配比实际要使用的空间更多的空间。
• 计算哈希比较快，但是在std::map中查找几个指针可能会更快。

对于std::map

• 动态地为映射中的每个元素分配新内存，如果要向映射中添加数百万个元素，这可能会很慢。
• 删除元素也是一种日志n操作，如果您经常这样做，它可能会很慢。
• 因为它是一棵树，所以它是排序的，所以您可以按顺序遍历元素，这在无序地图中是不可能的。

还有很多其他的，我建议查找它们，已经有许多关于堆栈溢出的此类问题的重复。

至于秒问题，这是在unordered_map中添加和访问元素的有效方法。但是，如果您知道要放置在地图中的项目的数量，我强烈建议您使用reserve()。

Answer 2

其他人已经解释了unordered_map与map之间的关系，但是如果这是真正的速度，那么我建议使用普通数组(或向量)来代替。您说实体的数量可以是“非常大的”，这样我就知道您正在处理密集的数据(也就是说，大多数坐标包含一个实体)。unordered_map是一种hashmap，这意味着密集的数据将迅速填满桶。大桶将降低速度和增加内存使用，减少使用unordered_map的优势。

恢复到数组将总是提供更快的访问和插入实体，而代价是一些额外的RAM。我不知道可能的坐标范围，但假设您的地图范围是(0,0) - (1024,1024)。为此使用指针数组将只使用1024x1024x8字节= 8MBytes的RAM，不管您在其中存储了多少实体。我需要运行一些测试来确保，但是我认为如果您的地图中有超过80%的实体填充，数组方法实际上将比unordered_map方法使用更少的内存。

最后，我还想提一下，你不应该总是关注速度。优化的C++代码通常已经非常快了，除非您真的非常非常需要我建议的使用最简单的解决方案而不是最快的解决方案的速度。

Answer 3

当您需要访问unordered_map容器的密钥时，它们比map容器更快，但是在尝试访问它们的元素子集时被认为效率较低。我认为，如果您要直接访问unordered_map容器中包含的指针，那么它的效率就会降低。map/