How to use lower_bound to insert value into sorted vector

Question

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?

Answer 1

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; });

Answer 2

If you really want a std::vector of pointers, you may want to consider using a smart pointer like std::shared_ptr.
Raw pointers are OK if they are observing pointers, but generally you should not using raw owning pointers (unless in some special conditions).

You can pass a lambda to std::lower_bound(), to specify the sorting criteria (in this case, compare the key data members).

Moreover, instead of explicitly writing std::vector<std::shared_ptr<A>>::iterator for the return value of std::lower_bound(), you could just use C++11's auto keyword, which makes the code more readable in this case.

A compilable code sample follows (compiled with g++ 4.8.0):

#include <algorithm>    // for std::lower_bound
#include <iostream>     // for console output
#include <memory>       // for std::make_shared, std::shared_ptr
#include <string>       // for std::string
#include <vector>       // for std::vector
using namespace std;

// Test data structure
struct A
{
    int Key;
    string Data;

    A()
        : Key(0)
    {}

    A(int key, const string& data)
        : Key(key), Data(data)
    {}
};

ostream& operator<<(ostream& os, const A& a)
{
    os << "(key=" << a.Key << ", data=\"" << a.Data << "\")";
    return os;
}

void Print(const vector<shared_ptr<A>> & v)
{
    cout << "[ ";
    for (const auto & p : v)
    {
        cout << *p << " ";
    }
    cout << " ]\n";
}

int main()
{
    // Test container
    vector<shared_ptr<A>> v;

    // Test data
    const char* data[] = {
        "hello",
        "world",
        "hi",
        nullptr
    };

    // Index in data array
    int i = 0;

    // Insertion loop
    while (data[i] != nullptr)
    {
        // Create new element on the heap
        auto elem = make_shared<A>(i, data[i]);

        // Find ordered insertion position
        auto it = lower_bound(v.begin(), v.end(), elem,
            [](const shared_ptr<A>& lhs, const shared_ptr<A>& rhs)
            {
                return lhs->Key < rhs->Key;
            }
        );

        // Insert in vector
        v.insert(it, elem);

        // Move to next data
        i++;
    }

    // Show the result
    Print(v);
}

Here's the output:

[ (key=2, data="hi") (key=1, data="world") (key=0, data="hello")  ]