c++ - C++ 容器中的快速模糊搜索

Question

假设一个类定义如下:

class Test
{
public:
    Test(int arg)
    {
        x = arg;
    }

    bool fuzzyEqual(const Test& other) const {
        if (abs(x - other.x) < FUZZY_EQUAL)
            return true;
        else return false;
    }

    int x;

private:
    static const int FUZZY_EQUAL = 5;
};

现在假设我们有一个 std::vector<Test>有很多元素。

给定一个新的 Test对象，线性搜索是在 vector 中找到与它“模糊”相等(相似)的第一个元素的最快方法吗？

此外，有没有像std::map这样工作的容器？但这接受相似而不是平等的概念吗？

至于我为什么要问:我有几个代表其他一些对象的值(在我的例子中，一个整数代表一个图像)，相似的图像产生相似的值。在容器中一次插入一个值时，我想避免在已经存在类似值的情况下添加一个值。我不关心不同的插入顺序会导致不同的容器。

Answer 1

您可以对 vector 进行排序并使用二进制搜索来查找与该点距离最小的位置。

例如 std::lower_bound 为您提供最小值 >= O(log(n)) 中的初始值。而前面的元素 --std::lower_bound 是最大的元素 < 你的初始值。如果存在模糊值，即相等，则这两个找到的值之一就是搜索到的值。