Comparison operator to be used in std::lower_bound

Question

My compiler refuse to compile this simple code:

struct mystruct{
    int x;
    bool operator<(const mystruct& y) const{ return x < y.x; }
};


std::map<mystruct, int> test;
auto it = std::lower_bound(test.begin(), test.end(), mystruct{2});

I'm getting the error

error C2893: Failed to specialize function template 'unknown-type std::less<void>::operator ()(_Ty1 &&,_Ty2 &&) const'

Looking at this link, it seems that you just need to define a constant comparison operator which is exactly what I'm doing. Is there something I am missing here?

Answer 1

The problem is that the value type of your map is std::pair<const mystruct, int>, and so std::lower_bound is trying to compare mystruct with std::pair<const mystruct, int>. And there is no operator defined for that.

You shouldn't be using std::lower_bound on a std::map anyway. It will work in O(n) because a map does not have random-access iterators. std::map has its own lower_bound member function which will take advantage of the tree structure to give you the result in O(log n).

auto it = test.lower_bound(mystruct{2});