我们正在用 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;
}
最佳答案
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()
。
关于c++ - std::unordered_map 包含另一个 std::unordered_map?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16586551/