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

Viewed 1003

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?

1 Answers
Related