Как изменить существующую функцию поиска stl в C++?

Question

Учитывая, что у меня есть структура данных,

struct data{ 
int val; 
}; 
struct data A[LEN]; // LEN: some length. 

// the below operator would be used in sorting. 
bool operator < (struct data &a1, struct data &a2){ 
return a1.val < a2.val; 
} 

int main(){ 
// fill up A. 
sort(A, A+LEN); // sort up A 

/*Now I want something like this to happen .. 
x = find(A, A+LEN, value); -> return the index such that A[index].val = value, 
find is the stl find function .. 
*/ 
} 

Как ты это делаешь? И для любой функции stl, как вы узнаете, какие операторы переопределить, чтобы она работала в данном условии?

Answer 1

Если вы хотите, чтобы сделать std::find работу для вашего массива структуры, необходимо определить operator== для данных структуры:

struct data 
{ 
    data(int value=0) : val(value) {} 
    int val; 
}; 

bool operator==(const data& l, const data& r) { return l.val == r.val;} 

auto x = find(A, A+LEN, value); 

ИЛИ

auto x = find(A, A+LEN, data(value)); 

Чтобы получить индекс стоимости в A, использовать std::distance

std::distance(A, x); 

Примечание: Для более точного поиска с сортированным контейнером используйте вместо этого std::lower_bound, std::uppper_bound, std::binary_search.

auto lower = std::lower_bound(A, A+LEN, data(3)); 
auto upper = std::upper_bound(A, A+LEN, data(3)); 

Ваша operator< функция подписи лучше быть, как:

bool operator < (const data &a1, const data &a2) 
//    ^^^^^   ^^^^^ 

Answer 2

Модификации, необходимые для поиска элементов в таком случае довольно минимальны. Во-первых, вы хотите, чтобы ваш operator< принимать свои аргументы как const ссылки (технически не является необходимым для текущего упражнения, но то, что вы хотите сделать в целом):

bool operator < (data const &a1, data const &a2){ 
    return a1.val < a2.val; 
} 

Тогда (та часть, которая действительно имеет значение, в частности, для std::find) также необходимо определить operator==:

bool operator==(data const &a, data const &b) { 
    return a.val == b.val; 
} 

Заметим, однако, что вы не должны определить это, если вы используете бинарный поиск вместо:

auto pos = std::lower_bound(data, data+LEN, some_value); 

Это будет использовать только operator<, который вы уже определили. Если элементы уже отсортированы в любом случае, это, как правило, будет предпочтительным (как правило, довольно быстро, если LEN не совсем мал).