MMM MMM - 1 year ago 136
C++ Question

lower and upper_bound on sorted vector of struct

Say for example I have:

struct my_stuff{
long my_value;

struct less_than{
bool operator()(const my_stuff &a, const my_stuff &b){
return a.my_value < b.my_value;

In my code I have:

vector<my_stuff> my_vec;

This vector already contains all the objects that I'm interested in. I then sorted my vector based on the my_value member variable

sort(my_vec.begin(), my_vec.end(), my_stuff::less_than());

Everything is fine so far. Now my vector of objects with the member variable "my_value" is now sorted based on the value of "my_value".

My question/problem is: How do I get the lower_bound and upper_bound of this vector based on "my_value". For example, if I was given that I want all the objects in the range [low, high] of my_value, I would want my lower_bound to point to the lowest object in that bound(low) and my upper_bound to point to my high.

What I've tried so far is...

auto low = lower_bound(myvec.begin()->my_value, my_vec.end()->my_value, val);

And same thing for upper bound except with "upper_bound" instead of "lower_bound". How do I syntatically achieve this? What I'm trying to do after I have sorted my vector of objects is to be able to find all the objects within a certain range. I believe lower_bound and upper_bound is the correct way to go about this, but I'm stumped on writing it. Thank you for any help or guidance!

Answer Source

There are two ways. You could construct an instance of my_stuff wrapping a desired value, and pass that to lower_bound:

my_stuff test; test.my_value = val;
auto low = std::lower_bound(time_table.begin(), time_table.end(), test, 

Or, add a couple of overloads to less_than::operator(), taking my_stuff on one side and long on the other. With a comparator that supports heterogeneous comparisons, you can write

auto low = std::lower_bound(time_table.begin(), time_table.end(), val,

You can further avoid having to pass my_stuff::less_than() to std::lower_bound (and to std::sort, for that matter) if, instead of a separate comparator, you implement my_stuff::operator<() (you can have three overloads of that).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download