0

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

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

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

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

3 回答 3

4

Astd::unordered_map是根据哈希表实现的，不像 astd::map是根据树实现的。这意味着对于 a unordered_map，访问通常是 O(1)，而对于 astd::map它是 O(log n)。这些之间有很多差异，如果您不知道这些差异，我建议您查看数据结构书籍，但这里有一些：

为了std::unordered_map

  • 分配单个连续的内存数组，您可以使用它reserve()来防止在不合时宜的时刻调整大小，但是由于哈希表的性质，这将始终分配比您实际使用的空间更多的空间
  • 计算哈希值很快，但在std::map

为了std::map

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

还有很多其他的，我建议查一下，stackoverflow 上已经有很多此类问题的重复项。

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

于 2013-05-16T12:09:22.710 回答
2

其他人已经解释了unordered_mapvs. map，但如果它真的是你追求的速度，那么我建议使用普通数组（或向量）。您说实体的数量可能“非常大”，据我所知，您正在处理密集数据（即大多数坐标都包含一个实体）。Anunordered_map是一种 hashmap，意味着密集的数据会迅速填满桶。大存储桶会降低速度并增加内存使用量，从而降低使用unordered_map.

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

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

于 2013-05-16T12:29:11.133 回答
0

当您需要访问它们的键时，unordered_map容器比map容器更快，但在尝试访问其元素的子集时被认为效率较低。我认为，如果您要unordered_map直接访问容器中包含的指针，效率会降低。 http://www.cplusplus.com/reference/unordered_map/unordered_map/

于 2013-05-16T11:58:50.687 回答