lower_bound for vector<MyClass*>

Question

I have this simple class:

class MyClass {
public:
    int id;
    string name;

};

I want to have a vector with pointers to objects of this class that is sorted by the referenced MyClass id. I thought that using lower_bound would be easy, I did it before with vectors of objects (not pointers). With objects, I overloaded operator< like that:

bool operator<(MyClass left, int right) {
    return (left.id < right);
}

Then I used lower_bound to insert new MyClass object to sorted vector.

vector<MyClass>::iterator low;
low = lower_bound(vectorname.begin(),vectorname.end(),id);
prP = idContainer.begin();
prP = idContainer.insert(low, newobject); 

I am lost how to do the same with the vector of MyClass pointers. Can anyone help me achieve that?

Jeffcott

Answer 1

There are two overloads of std::lower_bound:

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

The first one is the one you used for your vector<MyClass>, it uses operator< by default. The second one allows for a custom comparison function which takes an element from the container as the first argument and the value as the second. That's what you want to use for your vector<MyClass*>:

std::vector<MyClass*> pvec;
auto low = std::lower_bound(pvec.begin(), pvec.end(), id,
    [](const MyClass* c, const MyClass& id) {
        return *c < id;
    });

It's a little odd that the comparison takes two arguments of different types, but that's just how it is.

Note: your current operator< takes its arguments by value. That incurs unnecessary copies. You'll want to change that to take them by reference to const.

Socinus

+1 for pointing out that the comparison function doesn't need to have the same type for both parameters. – Crossstaff