c++ - C++ std::map vs 动态数组

Question

我正在尝试制作一个 3 维布尔数组，它告诉我是否以前访问过 3d 空间中的某个位置以进行简单的导航算法。该数组可能非常大（大约为 1,000,000 x 1,000,000 x 1,000,000 或更大），所以我想知道声明该大小的数组并将每个布尔值设置为 false 是否会更快，或者使带有坐标键 (x, y, z) 和 bool 类型值的映射。

据我所知，数组需要 O(1) 来查找或修改坐标，而地图需要 O(log n) 来查找或插入值。显然，对于访问值，数组更快。但是，这会抵消声明这样一个数组所需的时间吗？

谢谢

Answer 1

即使每个布尔值 1 位，您的数组也将占用 2**39 个字节。set如果没有太多元素，我会建议true.

您可以使用一个类来隐藏实现细节，并使用一维集。

Answer 2

您是否尝试过计算这样的数组需要多少内存？很多！如果点的顺序很重要，则使用 std::map，否则使用 std::unordeded_map。此外，无序映射为您提供了恒定的时间插入和查找。我想某种搜索树可能是您正在寻找的（例如 kd 树）。

Answer 3

假设您每点使用 8 位，您将创建一个 1 EB 的数组？哇，你有很多内存！

我认为你应该重新考虑你的方法。