C++ STL set lower_bound wrong result

The ordering for a set must act like <, not <=. Since you have an element with the key you’re looking for, the <= is wrong and sends the search the wrong way.

Meanwhile, using std::lower_bound on a set is wasteful: the iterators don’t expose the search structure, so the search is effectively linear. You can avoid this with C++14’s heterogeneous comparisons if you define setCompareFunctorAux ::is_transparent.

You have to use the strict less operator From the C++ 2017 Standard (28.7 Sorting and related operations)

3 For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 28.7.3, comp shall induce a strict weak ordering on the values.

4 The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering...

struct setCompareFunctor { bool operator( )(const pair< int, int > &lhs, const pair< int, int > &rhs) const { return(lhs.second < rhs.second); } }; struct setCompareFunctorAux { bool operator( )(const pair< int, int > &lhs, const pair< int, int > &rhs) const { return(lhs.second < rhs.second); } bool operator( )(const pair< int, int > &lhs, int val) const { return(lhs.second < val); } bool operator( )(int val, const pair< int, int > &rhs) const { return(val < rhs.second); } }; 

Take into account that within the called algorithm there is used the operator

struct setCompareFunctorAux { //... bool operator( )(const pair< int, int > &lhs, int val) const { return(lhs.second < val); } }; 

Here is a demonstrative program

#include <iostream> #include <set> #include <algorithm> int main() { using namespace std; struct setCompareFunctor { bool operator( )(const pair< int, int > &lhs, const pair< int, int > &rhs) const { return(lhs.second < rhs.second); } }; struct setCompareFunctorAux { bool operator( )(const pair< int, int > &lhs, const pair< int, int > &rhs) const { return(lhs.second < rhs.second); } bool operator( )(const pair< int, int > &lhs, int val) const { return(lhs.second < val); } bool operator( )(int val, const pair< int, int > &rhs) const { return(val <= rhs.second); } }; set< pair< int, int >, setCompareFunctor > submultimi; submultimi.insert(make_pair(1, 15)); submultimi.insert(make_pair(2, 9)); submultimi.insert(make_pair(3, 33)); submultimi.insert(make_pair(4, 44)); submultimi.insert(make_pair(5, 20)); submultimi.insert(make_pair(6, 15)); for (const auto &p : submultimi) { cout << "{ " << p.first << ", " << p.second << " } "; } cout << endl; set< pair< int, int >, setCompareFunctor >::iterator it = lower_bound(submultimi.begin(), submultimi.end(), 20, setCompareFunctorAux()); cout << (*it).second << endl; return 0; } 

Its output is

{ 2, 9 } { 1, 15 } { 5, 20 } { 3, 33 } { 4, 44 } 20 

The expected result is 15, but the real result is 33.

And the expected and correct result is 20 because there is an element with the second value equal to 20 and you are searching exactly 20.

Take into account that the template class std::set has its own member function lower_bound.

I think you are trying to achieve something different from what std::lower_bound can give to you.

#include <algorithm> #include <iostream> #include <set> #include <utility> using my_key = std::pair<int, int>; int main(int argc, char *argv[]) { auto comp = [](const my_key &l, const my_key &r) { return l.second < r.second; }; std::set<my_key, decltype(comp)> submultimi(comp); submultimi.insert({1, 15}); submultimi.insert({2, 9}); submultimi.insert({3, 33}); submultimi.insert({4, 44}); submultimi.insert({5, 20}); submultimi.insert({6, 15}); // "<=" inside comp will put this pair into the set for (const auto &elem : submultimi) std::cout << elem.first << " -> " << elem.second << '\n'; auto it = std::lower_bound( submultimi.begin(), submultimi.end(), 20, [](const my_key &l, const int &r) { return l.second < r; }); std::cout << it->second << '\n'; return 0; } 

outputs

2 -> 9 1 -> 15 # note the lack of 6 -> 15 in the set 5 -> 20 3 -> 33 4 -> 44 20 

Everything seems legitimate as per the documentation provided in http://en.cppreference.com/w/.

I assume you are trying to put 6->15 using some trick, and the very same trick breaks std::lower_bound due to the violation of the weak ordering as is already pointed out by the other responders.