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

我试图做一个布尔值的3维数组，告诉我如果我以前访问过一个简单的导航算法的三维空间位置。该数组可能很大（沿着1,000,000 x 1,000,000 x 1,000,000或更大的线），所以我想知道是否会更快地声明一个大小的数组并将每个布尔值设置为false，或者使一个坐标为（x，y，z）的键和一个bool类型的值的映射。C++ std :: map vs动态数组

从我认为，该数组将需要O（1）来查找或修改一个坐标，并且地图将采取O（log n）来查找或插入一个值。显然，为了访问值，数组更快。但是，这是否抵消了声明这样一个数组所需的时间？

谢谢

来源

2012-09-23 VerTiGo_Etrex

'std :: unordered_map'平均为O（1） – Rapptz

为什么不使用哈希映射（C++ 11中的'unordered_map'）？ – Xeo

即使在每个单元一位，您也需要10^11 GB以上的内存来存储数组。你应该考虑更好的方法。 –

即使在每个布尔1位，您的数组将会接管2 ** 39个字节。如果没有太多的元素将会是true，我会建议set。

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

来源

2012-09-23 00:23:08

这似乎是'std :: set'是理想的数据结构的少数用例之一，因为所有你关心的是“我到过这里吗？”。“实现细节”类将有3个数据成员（x，y和z坐标）并定义'operator <'。根据你的用例，你可能需要的唯一一件事是一个接受x，y和z坐标的构造函数，数据成员是私有的（如果你真的关心这些坐标的话，那就是你是否曾经去过）。 –

这比std :: unordered_set更快吗？在那个笔记上，我一直很难弄清楚我需要在我的类中实现哪些函数（它只包含三个int值）以允许使用unordered_set。 –

@VerTiGo_Etrex，'std :: set'和'std :: unsorted_set'之间的速度差异将取决于您填充的元素数量和散列函数的质量。 'std :: set'需要一个'''比较器，'std :: unordered_set'需要一个散列函数和一个'=='比较器。 –

你有没有试过计算这样的数组需要多少内存？很多！如果点的排序很重要，则使用std :: map，否则使用std :: unordeded_map。无序映射也给你一个不变的时间插入和查找。我猜想某种搜索树可能是你正在寻找的东西（例如k-d树）。

来源

2012-09-23 00:26:52 lego

假设您使用每点8位的数据，那么您将创建一个数组，该数组是一个exabyte？哇，你有很多RAM！

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

来源

2012-09-23 03:13:29

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

回答

相关问题