C++ std::map 与动态数组

Question

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

据我所知，数组查找或修改坐标的时间复杂度为 O(1)， map 查找或插入值的时间复杂度为 O(log n)。显然，对于访问值，数组更快。然而，这是否抵消了声明这样一个数组所花费的时间？

谢谢

Answer 1

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

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