how to do a binary search on a vector to find element with certain id?

Question

I have a sorted vector and now I would like to find elements from that vector that have a certain id. std::binary_search just tells me if the element exists, so I use std::lower_bound:

#include <vector>
#include <iostream>
#include <algorithm>

struct Foo {
    int id; 
    // ... more members ... //
    Foo(int id) : id(id) {} 
};

bool compareById(const Foo& a,const Foo& b) { return a.id < b.id; }

int main(){
    std::vector<Foo> vect;
    vect.push_back(10);
    vect.push_back(123);
    vect.push_back(0);
    std::sort(vect.begin(),vect.end(),compareById);
    int id_to_find = 1;
    std::vector<Foo>::iterator f = std::lower_bound(vect.begin(),vect.end(),Foo(id_to_find),compareById);
    if (f != vect.end() && f->id == id_to_find) { std::cout << "FOUND"; }
}

This kinda works, but I strongly dislike it that I have to create a Foo(id_to_find) to pass it to std::lower_bound and then I have to double check if the element I got is really the one I was looking for.

I think I could use find_if to avoid creating that superfluous instance, but as far as I know find_if is only linear and doesn't make use of the vector being sorted. I am a bit surprised that I cannot find the right algorithm for the task and I am already considering writing my own.

What is the idomatic way to do this?

Answer 1

There are a couple things you can do to make you life easier. The first thing is that the comparator does not need to have the same parameter for the first and second parameters. The requirement is that the first parameter must be implicitly convertible to the dereferenced iterator and the second parameter needs to be implicitly convertible to the type of the third parameter passed to lower_bound.

We can leverage this and just take an int as the second parameter so you don't have to construct a Foo. That allows us to make a compareFooById like:

bool compareFooById(const Foo& a,const int& b) { return a.id < b; }

And then we can use it now like:

std::vector<Foo>::iterator f = std::lower_bound(vect.begin(), vect.end(), id_to_find, compareFooById);

^{Note that I did add a new function here. You use compareById for std::sort so I couldn't just change it as that would break the call to sort.}

Now as far as having to check if you have a valid iterator you have a couple options. You can write a wrapper function that takes a reference to an iterator to populate and returns if it found an item. That would look like

template<typename It, typename Value, typename Comp
bool my_binary_search(It begin, It end, Value val, Comp c, It& ret)
{
    ret = std::lower_bound(begin, end, val, c);
    return ret != end;
}

and then you call it like

std::vector<Foo>::iterator f;
if(my_binary_search(vect.begin(), vect.end(), id_to_find, compareFooById, f))
    //do something with f.

The other option is to throw an exception if the item is not found. That, in my opinion, is not what you wan to do though unless not finding the item is a truly exceptional case.