CODEWITHSUNDEEP
c++containersfuzzy-search
Banex
Banex

Reputation: 2938

Fast fuzzy search in C++ container

Suppose a class is defined as follows:

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;
};

Now suppose we have a std::vector<Test> with a lot of elements.

Given a new Test object, is linear search the fastest way to find the first element in the vector that is "fuzzy" equal (similar) to it?

Furthermore, is there a container that works like std::map but that accepts the concept of similarity and not equality?

As for why I am asking: I have several values that represent some other objects (in my case, an integer represents an image), and similar images result in similar values. When inserting the values one at a time in a container, I want to avoid adding a value if a similar one is already present. I do not care that different orders of inserting result in different containers.

Upvotes: 3

Views: 1490

Answers (1)

Jakube
Jakube

Reputation: 3565

You could sort the vector and use binary search to find the positions, that have the smallest distance to the point.

For instance std::lower_bound gives you the smallest value >= your initial value in O(log(n)). And the previous element --std::lower_bound is the biggest element < your initial value. If there is a fuzzy value, that is equal, then one of these two found values is the searched one.

Upvotes: 1

Related Questions