C++ – How to use lower_bound to insert value into sorted vector

cstl

I have a vector of pointer to class A which I want to keep sorted by int key using STL. To do this I defined an operator < in class A

bool operator< (const A &lhs, const A &rhs){
    return (lhs.key < rhs.key);
};

and in my insert function it looks like

vector<A*>::iterator it = lower_bound(vec.begin(), vec.end(), element);
vec.insert(it, element);

I expect lower_bound to return first place where the new element can be placed, but it does not work. Inserting A objects with keys 0,1,2,3 will result in vector in incorrect order (2,3,1,0). Why is that ?

Probably I could also use comparator for this object:

compare function for upper_bound / lower_bound

but what's wrong with my code?

Best Answer

From your example, you're using a vector of pointers: std::vector<A*>. Hence, you need to define a comparison for pointers which you pass in to std::lower_bound:

bool less_A_pointer (const A* lhs, const A* rhs)
{
    return (lhs->key < rhs->key);
}

auto it = std::lower_bound(vec.begin(), vec.end(), element, less_A_pointer);
//...

Of course, the question is why are you using pointers in the first place - just store A objects unless you really need to. If you do need to store pointers, look into std::shared_ptr which will handle this for you:

std::vector<std::shared_ptr<A>> v;
std::shared_ptr<A> element(new A(...));
auto it = std::lower_bound(v.begin(), v.end(), element); //Will work properly

You can also use a lambda instead of having to write a free function:

auto it = std::lower_bound(v.begin(), v.end(), 
                          [](const A* lhs, const A* rhs)
                          { return lhs->key < rhs->key; });
Related Topic