快速模糊搜索在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 对象，使用线性搜索来查找与其相似的向量中第一个元素是最快的方法吗？

此外，是否存在一种容器类似于 std::map 但接受相似概念而不是相等？

至于我为什么问这个问题： 我有几个值，它们表示其他对象（在我的情况下，整数表示图像），相似的图像会得到相似的值。当逐个将值插入容器时，如果已经存在相似的值，则希望避免添加该值。我不关心插入顺序导致不同的容器。

- Banex

---

重载 == 使其不具有传递性是不好的实践，请改用 bool isSimilar(const Test&) 或其他方法。 - Mooing Duck

@MooingDuck 已修复，谢谢！ - Banex

我感觉在一个毫无意义的外表背后隐藏着一个完全合理的问题。也许如果您告诉我们您真正想做什么，我们可以提供解决方案。 - Veedrac

我特别想知道你为什么需要一个std::map。听起来像是一个区间树或者你可以在其中搜索最接近匹配的map，这可能会解决你的问题。 - Veedrac

@Veedrac 我已经添加了我的具体问题。 - Banex

太好了。这样会容易得多。使用一个非模糊值的map，在插入之前只需检查要插入的值是否与其在map中的upper_bound或lower_bound是fuzzyEqual的即可。 - Veedrac

Answer 1

您可以对向量进行排序并使用二分查找来找到与该点距离最小的位置。

例如，std::lower_bound 可以在 O(log(n)) 的时间复杂度内返回大于或等于初始值的最小值。而前一个元素 --std::lower_bound 则是小于初始值的最大元素。如果存在一个模糊的值相等，则这两个找到的值之一就是所搜索的值。

- Jakube

---

我认为你需要使用std::next(std::lower_bound)，顺便说一下。 - Veedrac