c++ - C++中快速搜索的数据结构

Question

我需要在数据结构中存储如下值，

id   x     y     z
0    0.1   0.1   0.1
1    0.2   0.1   0.6
2    0.01  0.3   0.1
.....

现在我需要匹配 x,y,z double 值并获取相应的 id(int) 值。我可能需要存储大约 400000 个值。我应该使用哪种数据结构来进行高效搜索？ C++ 是否带有支持我的要求的任何内置结构。

Answer 1

如果您对 NN 搜索不感兴趣，可以使用 std::unordered_set。但是，您需要定义自己的哈希函数。

这是一个(可能很糟糕的)例子:

struct entry
{
    int id;
    double x, y, z;

    // constructor if needed, etc...
};

struct entry_hasher
{
    size_t operator()(const entry &e) const
    {
        std::hash<double> h;
        return h(e.x) ^ (h(e.y) << 1) ^ (h(e.z) << 2);
    }
};

std::unordered_set<entry, entry_hasher> entries;

否则，标准不提供能够进行几何查询(例如NN)的容器。