How to use lower_bound to insert a value into a sorted vector

Question

I have a pointer vector to class A, which I want to keep sorted using the int key using STL. For this, I defined 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 return the first place where a new item can be placed, but it does not work. Inserting objects with keys 0,1,2,3 will cause the vector to be in the wrong order (2,3,1,0). Why is this?

Perhaps I could also use a comparator for this object:

compare function for upper_bound / lower_bound

but what is wrong with my code?

Answer 1

In your example, you are using a pointer vector: std::vector<A*> . Therefore, you need to define a comparison for the pointers you pass 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 you use pointers in the first place - just store A objects if you really don't need to. If you need to save pointers, take a look at 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 lambda instead of writing 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 std::vector pointers, you might want to use a smart pointer , like std::shared_ptr .
Raw pointers are fine if they observe pointers, but usually you shouldn't use raw pointers (unless in some special conditions).

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

Also, instead of spelling std::vector<std::shared_ptr<A>>::iterator explicitly for the return value of std::lower_bound() you can simply use the C ++ 11 auto keyword, which makes the code more readable in this case.

The following is a compiled code example (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 < lhs->Key; } ); // Insert in vector v.insert(it, elem); // Move to next data i++; } // Show the result Print(v); } 

Here's the conclusion:

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