быстрого нечеткого поиска в 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, но который принимает концепцию подобия, а не равенства?

А почему я спрашиваю: У меня есть несколько значений, которые представляют другие объекты (в моем случае, целое представляет собой изображение), и подобные изображения приводить к аналогичным значениям. При вставке значений по одному в контейнере я хочу избежать добавления значения, если он уже присутствует. Меня не волнует, что разные заказы вставки приводят к разным контейнерам.

Answer 1

Вы можете отсортировать векторный и использовать бинарный поиск, чтобы найти позиции, которые имеют наименьшее расстояние до точки.

Например, std::lower_bound дает наименьшее значение> = ваше начальное значение в O(log(n)). И предыдущий элемент --std::lower_bound является самым большим элементом < вашего начального значения. Если есть нечеткое значение, то это равно, то одно из этих двух найденных значений является искомым.