CODEWITHSUNDEEP
c++stl
Ninja420
Ninja420

Reputation: 3872

How to modify the existing stl find function in C++?

Given that I have a data structure,

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 .. 
*/
}

How do you do that ? And for any stl function how do you get to know which operators to override so that it works in the given condition ?

Upvotes: 0

Views: 229

Answers (2)

billz
billz

Reputation: 45410

If you only want to make std::find work for your array of structure, you need to define operator== for struct data:

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

OR

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

To get index of value in A, use std::distance

std::distance(A, x);

Note: For more sufficent search with sorted container, use std::lower_bound, std::uppper_bound, std::binary_search instead.

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

Your operator< function signature better be like:

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

Upvotes: 2

Jerry Coffin
Jerry Coffin

Reputation: 490128

The modifications needed to find elements in such a case are pretty minimal. First, you want to make your operator< take its arguments as const references (technically not necessary for the current exercise, but something you want to do in general):

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

Then (the part that really matters specifically for std::find) you also need to define an operator==:

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

Note, however, that you don't have to define this if you use a binary search instead:

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

This will just use the operator< that you'd already defined. If the items are already sorted anyway, this will usually be preferable (generally quite a bit faster unless LEN is quite small).

Upvotes: 3

Related Questions