CODEWITHSUNDEEP
c++searchstl
user1285419
user1285419

Reputation: 2225

using std::equal_range to search the vector within some ranges

I have a std::vector with the element as pair and need to find all the elements with the first component within some ranges, for example, to find all elements such that abs(value of first component - reference)<0.01, I got the code from other post that

bool comp(pair<double, double> v1, pair<double, double> v2)
{
  return (abs(v1.first-v2.first)<0.001);
}

vector< pair<double, double> data;
for (int i=0; i<10; i++)
{
  double a, b; 
  // a & b are initialized randomly (the code was not shown here)
  data.push_back(make_pair(a, b));
}

// we sort the vector here based on the pair.first (code not shown)

// compval is used as reference value, i.e. we are going to find all elements with     abs(pair.first-ref.first)<0.01
pair<double, double> ref
ref.first = 0.5;
ref.second = 0.5;

std::pair< vector< pair<double, double>::iterator, vector< pair<double, double>::iterator> const range = std::equal_range(data.begin(), data.end(), ref, comp);

but if you look at all elements given by the resulting ranges, you will see that all elements of the data instead of the one satisfying abs(pair.first-ref.first)<0.01 will be returned. Is that anything I miss in the code? Thanks.

Upvotes: 0

Views: 3768

Answers (3)

Jid
Jid

Reputation: 1

I think you should use fabs instead of abs in function comp().

Upvotes: 0

Fraser
Fraser

Reputation: 78330

Your comparison function does not satisfy the requirements of strict weak ordering, i.e. for two elements say a and b, if comp(a, b) == true then comp(b, a) should be false.

You maybe want something more like this:

struct Comp {
  double target;
  bool operator()(const pair<double, double>& lhs,
                  const pair<double, double>& rhs) const {
    return abs(lhs.first - target) < abs(rhs.first - target);
  }
};

vector< pair<double, double> > data;
data.push_back(make_pair(0.1, 1.0));
data.push_back(make_pair(0.15, 1.2));
data.push_back(make_pair(0.189, 2.1));
data.push_back(make_pair(0.19, -2.1));
data.push_back(make_pair(0.192, 3.1));
data.push_back(make_pair(0.2, 0.1));
data.push_back(make_pair(0.205, 0.1));
data.push_back(make_pair(0.205, 0.0));
data.push_back(make_pair(0.206, 12.1));
data.push_back(make_pair(0.21, -12.9));
data.push_back(make_pair(0.3, 3.4));
data.push_back(make_pair(0.5, 7.5));
// We *must* sort the vector using the same comparison function that we're
// about to use to get the lower and upper bounds
Comp comp;
comp.target = 0.2;
sort(data.begin(), data.end(), comp);

// Get the lower bound
pair<double, double> low(make_pair(comp.target, 0.0));
vector< pair<double, double> >::iterator lower =
    lower_bound(data.begin(), data.end(), low, comp);

// Get the upper bound
pair<double, double> up(make_pair(comp.target + 0.01, 0.0));
// N.B. use "lower_bound" here to get upper bound of target + 0.01 exclusive.
//      If we want to include target + 0.01, use "upper_bound"
vector< pair<double, double> >::iterator upper =
    lower_bound(data.begin(), data.end(), up, comp);

for_each(lower, upper, [](const pair<double, double> &data_point) {
  cout << data_point.first << "\t" << data_point.second << "\n";
});


which outputs:

0.2     0.1
0.205   0.1
0.205   0
0.206   12.1
0.192   3.1
0.21    -12.9

Upvotes: 0

Mankarse
Mankarse

Reputation: 40613

equal_range requires a sorted range.

The order implied by your comparison function does not match the order that you sorted the range into - and so the call to equal_range has undefined behaviour.

For example - say your list contained {{.5, 0}, {.6, 0}} (these are sorted), and you then applied std::bind(comp({.5,.5},_1)) to each element.

comp({.5,.5},{.5,0}) would return true.

comp({.5,.5},{.6,0}) would return false.

Your sort order is saying: ".5 is less than .6", but at the same time your comp function is saying ".6 is less than .5" (because a there is a value which is less than .5 but not less than .6). This is contradictory, and the cause of your problems.

To actually find all the elements such that std::bind(comp({.5,.5}, _1)) returns true, you could use std::copy_if(data.begin(), data.end(), some_output_iterator, std::bind(comp(ref, std::placeholders::_1))) (although there are a variety of different ways of doing this, depending on your exact needs).

Upvotes: 2

Related Questions