c++ - std::unordered_map 包含另一个 std::unordered_map？

Question

我们正在用 C++ 为学校开发一个游戏项目。我负责 map 对象，它将包含炸弹、玩家、墙壁和盒子等实体。我的 map 中有 3 个容器:

• 玩家的 std::list(多个玩家可以站在同一个盒子上)。
• A std::unordered_map<int, std::unordered_map<int, AEntity*> >用于墙壁。
• 另一个std::unordered_map<int, std::unordered_map<int, AEntity*> >用于炸弹+盒子。

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

这就是我想到 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

问题一:

首先，对于这种用法，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 n)。它们之间有很多差异，如果您不知道这些差异，我建议您阅读一本数据结构书籍，但这里有一些:

对于 std::unordered_map

• 分配一个连续的内存数组，您可以使用 reserve() 来防止在不合时宜的时候调整大小，但是由于哈希表的性质，这将始终分配比您更多的空间实际上曾经打算使用
• 计算散列很快，但在 std::map 中查找一些指针可能会更快

对于 std::map

• 为 map 中的每个元素动态分配新内存，如果您向 map 添加数百万个元素，这可能会很慢。
• 删除元素也是一个 log n 操作，如果您经常这样做，可能会很慢。
• 因为它是一棵树，所以它是排序的，所以你可以按顺序遍历元素，这是无序 map 做不到的事情

还有很多其他问题，我建议查找它们，stackoverflow 上已经有很多重复的此类问题。

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