我有一个数据数组（通用顶点数据）。我需要能够根据位置搜索数组的元素。目前，每个顶点元素都记录自己的位置，我只需使用for-loop来搜索每个元素并比较位置。我必须在我的程序中做很多事情，这对性能相当关键。遍历每个元素似乎真的非常低效。
我用C++，顺便说一句。
我的问题是：有没有更好的方法？也就是说，有没有办法直接基于 3D 位置访问必要的元素？这些位置是整数，所以这可能会有所帮助。
我想过简单地使用3D数组（即顶点[256][256][256]），但我不能浪费内存，因为只有大约30-50%的顶点位置实际上包含一个顶点。也许这可以通过指针来实现？它们在未分配时是否使用内存？
3D阵列的另一个问题是顶点可以分布在几乎无限的区域内，这将形成一个非常非常大的阵列。此外，顶点实际上是动态添加的，这意味着它们可以在 <0 位置添加，这意味着数组必须向后移动并重新分配每个元素。
如果有人有任何建议，我将不胜感激:)
Octree 可能是基于体素的地形（或模型）的最佳解决方案。八叉树的基本概念由节点和叶子组成。每个节点（和叶）代表立方体空间，每个节点包含 8 个子节点（或叶），使得每个子节点占用其父节点空间的 1/8（见图）。
叶子与节点的不同之处在于没有更多的子节点，但包含数据本身 - 在您的情况下是顶点数组。
八叉树的深度取决于您，这实际上取决于您的地形的详细程度。现在，如果您想将顶点组织到树中，对于每个顶点，您将首先将其发送到主节点（作为树根的节点，即包含所有其他节点），然后根据位置确定顶点属于哪个子节点。然后以递归方式传递顶点，直到它到达存储在数组中的叶节点。
简单起见，这里是四叉树的 2D 示例：
(4,4)
-----------------
| 3 | 4 |
| | |
-----------------
| 1 | 2 |
| | |
-----------------
(0,0)
假设地形的大小是 4x4。在此示例中，我们仅使用主节点作为包含叶节点的节点。如果我们现在有顶点，让我们说(0.2, 3.2).顶点将传递到根节点。由于0.2 < 4/2和3.2 > 4/2，节点将顶点发送到存储顶点的叶子3号。如果要在空间（或本例中为平面）中搜索位置，则以与存储描述类似的方式执行此操作。
在实现中，可以使用指针表示节点的子节点/叶。如果要优化空间，则根本不需要存储每个节点的维度和位置，而是隐含地说每个节点的维度1x1x1，然后在传递之前相应地转换每个顶点。即您在位置 (600,600,100) 处有大小为 1000x1000x1000 和顶点的地形。现在，您将位置除以大小，以便获得传递给节点的位置(0.6,0.6,0.1)。由于0.6 > 1/2和0.1 < 1/2，您将相应地将其传递给节点，但在转换它之前，再次通过从高分量中减去 1/2，然后将所有分量乘以 2（因为子节点在所有维度上都小两倍）以获得您将传递的位置(0.2, 0.2, 0.2)......等等。但是，这更高级，因为每次使用树时都需要依靠它。
在互联网上很难找到有关该主题的教程，但是有很多实现可以学习。以下是我发现的几个：
http://www.flipcode.com/archives/Octree_Implementation.shtmlhttps://github.com/brandonpelfrey/SimpleOctree
还有一个实际的教程（但它非常沉重）：http://www.xbdev.net/maths_of_3d/octree/tutorial/
您可以考虑的解决方案是使用稀疏网格作为 ADT。
std::unordered_map是一个散列映射，可用于创建稀疏网格数据结构。 如果你为 3d 向量写了一个好的哈希，你可以得到很好的 O（1） 读取性能，这将接近原始数组的性能。
散列映射还允许您使用"几乎无限"的区域（当然约束将在底层数据类型中。
抱歉耽搁了。
对于unordered_map来说，这是一个很好的信息资源： unordered_map哈希函数 c++
我在自己的项目中使用一对整数实现，但我确信它可以用于三维坐标。
namespace std {
template <class T>
inline void hash_combine(std::size_t & seed, const T & v) {
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template<> struct hash<pair<int, int> > {size_t operator()(pair<int, int> x) const { size_t seed=0; hash_combine(seed, x.first); hash_combine(seed, x.second); return(seed); } };
}
然后你可以声明你的unordered_map
std::unordered_map<std::pair<int, int>, [VALUE] > my_map; //[VALUE] being the data type of vertex
在此之后，您可以将结构视为常规std::map。 如果您不确定如何使用一个，那里有很多示例。
对于 3d 坐标，您可以声明自己的结构
struct vector
{
int i,j,k;
};
然后修改哈希函数（格式化为可读性）
template<> struct hash<vector > {
size_t operator()(vector x) const {
size_t seed=0;
hash_combine(seed, x.i);
hash_combine(seed, x.j);
hash_combine(seed, x.k);
return(seed);
}
};