CODEWITHSUNDEEP
c++algorithmstlbinary-search
hisham
hisham

Reputation: 215

binary_search to find a class object by the return variable of its member function [c++]

I have a vector of class objects sorted by its integer indices. But the index of an object is generated by the member function of the class - so no int id is stored as a member variable.

class boundary
{
     public:
     int get_id();
}

std::vector<boundary> sample;

Now I need to find the boundary object ,which's int id generated by get_id() is same as the int value I'm searching.

auto &iter = binary_search(sample.begin(),sample.end(), 5, custom_function)
 //should compare iter.get_id() == 5

Is it possible to use binary_search in this case? How do I achieve this?

Upvotes: 5

Views: 1654

Answers (3)

Andrzej
Andrzej

Reputation: 5127

Assumption: you want to obtain a reference to the sought element (rather than an iterator to it).

boundary& find_boundary(std::vector<boundary>& sample, int id)
// precondition: a boundary with id does exist in the sample
{ 
  auto less_by_id = [](boundary const& b, int id) // lambda is faster than function pointers
    { return b.get_id() < id; };

  auto it = lower_bound(sample.begin(), sample.end(), id, less_by_id);

  assert (it != sample.end());
  assert (it->get_id() == id);
  return *it;      
}

Now, you can use it:

boundary& b = find_boundary(sample, 5);

Upvotes: 2

mcrlc
mcrlc

Reputation: 137

You can create an object which satisfies the "Compare" concept. http://en.cppreference.com/w/cpp/concept/Compare

For example:

class Compare {
public:
    bool operator()(boundry a, boundry b) {
        return a.get_id() < b.get_id();
    }
}

Upvotes: -1

Laney
Laney

Reputation: 1649

You should use std::lower_bound in this case: 

bool custom_function(boundary& obj, int id)  { return obj.get_id() < id; }
...
auto iter = lower_bound(sample.begin(),sample.end(), 5, custom_function);

(replace function pointer with function object if you want better performance)

Upvotes: 6

Related Questions