C ++ бинарный поиск для класса - PullRequest
Новая
       20

C ++ бинарный поиск для класса

1 голос
/ 29 мая 2019

У меня есть класс, и я хочу реализовать для него binary_search (из библиотеки): 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class T_value{
public:

    T_value(const int _timestamp, const string _value) :
        timestamp(_timestamp),
        value(_value)
    {}
    int get_time() {return timestamp;}


private:
    int timestamp;
    string value;
};

int main()
{

    T_value one(1, "one"),
    two(3, "two"),
    three(43, "three"),
    four(-1, "four");
    vector<T_value> v{one,two,three, four};

    cout << binary_search(begin(v), end(v), 3);
}

Возможно ли это?Стоит ли перегрузить операторы '==' и '<' (пробовал, не получилось) или что-то еще? </p>

Заранее спасибо!

Ответы [ 2 ]

3 голосов
/ 29 мая 2019

Поскольку вы отправляете int в качестве 3-го аргумента для binary_search, просто operator< будет недостаточно, поскольку вам необходимо поддерживать как int<T_value, так и T_value<int

Предложениезаключается в создании класса компаратора с членами: 

bool operator()(const T_value& lhs, int rhs) const
bool operator()(int lhs, const T_value& rhs) const

и отправке экземпляра в качестве четвертого параметра.

Кроме того, вектор должен быть отсортирован до вызова binary_search.Вы можете сделать это с помощью std::sort, но теперь вам нужно поддерживать третий тип сравнения, это может сделать третий член класса сравнения, например: 

bool operator()(const T_value& lhs, const T_value& rhs) const

Конечный результат может выглядеть примерно так это

2 голосов
/ 29 мая 2019

Да.Хотя нужно просто реализовать operator<.Кроме того, аргумент binary_search не совпадает, и контейнер должен быть предварительно отсортирован.

Ссылка на рабочий пример:

http://coliru.stacked -crooked.com / a / 0343dd205abac6f2

Оператор меньше: 

bool operator<(const T_value& other) const {
    return timestamp < other.timestamp;//you may wan't another sort criteria
}

Контейнер предварительной сортировки и двоичный_поиск: 

std::sort(v.begin(), v.end());
cout << (binary_search(begin(v), end(v), T_value(3, "not used") ) ? "found" : "not found") << std::endl;
...