Бинарный поиск C++ для класса
У меня есть класс, и я хочу внедрить в него 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);
}
Это возможно? Должен ли я перегружать операторы '==' и '<' (пробовал, не получилось) или что-то еще?
Заранее спасибо!
Какие ошибки вы получаете? Как это не работает? Возможно, это поможет вам понять, что именно вы должны реализовать;)
Ответы 2
Поскольку вы отправляете int в качестве третьего аргумента 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, но теперь вам нужно
поддерживать 3-й тип сравнения, 3-й член компаратора
класс может сделать это, например:
bool operator()(const T_value& lhs, const T_value& rhs) const
Конечный результат может выглядеть примерно так: это.
Большое спасибо, Дэнни! Раньше я не знал о концепции 'operator()' (в отличие от 'operator+' или 'operator<'). Это абсолютно работает! Кстати, как узнать, какие именно операторы нужно перегрузить для конкретного алгоритма (например, 'binary_search')? Почему мы добавляем '{}' после 'Comp' ('Comp{}')? :)
std::binary_search принимает бинарный предикат, который должен реализовать оператор вызова функции. Все алгоритмы документируют свои аргументы таким образом.
Comp — это тип. Comp{} — это созданный по умолчанию объект типа Comp. Все алгоритмы, которые принимают функциональные параметры, хотят иметь что-то с operator() (произносится как «операторский вызов»).
У меня также возникло бы желание добавить using is_transparent = void; к Comp
да. Хотя нужно просто реализовать 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
}
Контейнер предварительной сортировки и binary_search:
std::sort(v.begin(), v.end());
cout << (binary_search(begin(v), end(v), T_value(3, "not used") ) ? "found" : "not found") << std::endl;
Вы либо перегружаете
operator <, либо передаете пользовательский предикат вstd::binary_search. Оба варианта возможны, но вам нужно убедиться, что вектор уже отсортирован по до, вызывая бинарный поиск.