C++ STL set lower_bound wrong result

Question

I'm having some issues with the lower_bound comparison function.

I have a set of pairs ordered by the second value of the pair and i'm tryin to get the lower_bound from this set by a value.

My current code is:

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

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


int main( )
{
    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 ) );

    set< pair< int, int >, setCompareFunctor >::iterator it = lower_bound( submultimi.begin( ), submultimi.end( ), 20, setCompareFunctorAux( ) );


    cout << ( *it ).second << endl;


    return 0;
}

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

What is wrong ?

Answer 1

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.

Answer 2

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.

Answer 3

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

No, the expected result is 20, since the function "Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.", as you can read in the std::lower_bound reference.

You will not get this result, because you use <= instead of < in your setCompareFunctorAux struct.

As a result, when you search for 20, it get confused from the equality, and go towards the wrong direction when searching.

---

PS: Not related to your problem, but setCompareFunctor is not a valid comparator, because it doesn't satisfy the strict weak ordering. In order to do so, just change <= to <. Read more in Operator< and strict weak ordering.

Answer 4

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.