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 ?

Here's something to play with: http://coliru.stacked-crooked.com/a/710c3bbde16a5ecd — user0042, Oct 21 '17 at 13:11
`setCompareFunctor` is not a valid comparator as per the [strict weak ordering](https://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering) criteria. The `<=` condition should be `<`. But that aside, how do you want your elements sorted? Why is the expected result 15? — wally, Oct 21 '17 at 13:12
not working.. i've tried.. it always works like an upper_bound, not a lower one — Adi Pîslaru, Oct 21 '17 at 13:13

gsamaras · Accepted Answer · 2017-10-21T13:35:24.870

5

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.

edited Oct 21 '17 at 13:35

answered Oct 21 '17 at 13:16

gsamaras

71,951
46
188
305

1

ok .. this is a good answer. but, there is a way to get '15' ? – Adi Pîslaru Oct 21 '17 at 13:17
@AdiPîslaru thanks. And you asked a good question. =) Yes, pass 15, instead of 20 as the function's argument. – gsamaras Oct 21 '17 at 13:19
haha :)) can't do this.. i used that value just for an example, the code will be implemented in an algorithm .. i want to have something like a lower bound, but not equal with the value passed.. – Adi Pîslaru Oct 21 '17 at 13:20
@AdiPîslaru: But that _is_ `upper_bound`. Maybe you mean “greatest value less than a query”, which is just the element before `lower_bound`, if any exists. – Davis Herring Oct 21 '17 at 13:31
Your recommended iterator type doesn’t match the container. – Davis Herring Oct 21 '17 at 13:33

Davis Herring · Answer 2 · 2017-10-21T13:24:13.257

2

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.

edited Oct 21 '17 at 13:24

answered Oct 21 '17 at 13:13

Davis Herring

36,443
4
48
76

If i put <, it works like an upper_bound, don't know why – Adi Pîslaru Oct 21 '17 at 13:14

Vlad from Moscow · Answer 3 · 2017-10-21T14:04:35.660

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.

ok but if i use < instead <=, the duplicate values are not inserted in the set, for e.g. only one 15 value will be in the set and there are 2 inserted. — Adi Pîslaru, Oct 21 '17 at 13:43
@AdiPîslaru If you want to use duplicate values then use the standard container std::multiset. — Vlad from Moscow, Oct 21 '17 at 13:56
If i use 10 instead 20 in : set< pair< int, int >, setCompareFunctor >::iterator it = lower_bound(submultimi.begin(), submultimi.end(), 10, setCompareFunctorAux()); , the result is wrong, the result is 15 but the lower bound is 9 — Adi Pîslaru, Oct 21 '17 at 14:01
@AdiPîslaru lower_bound returns an iterator before the position where a new element with the value could be inserted. It can nor return 9 because 9 is less than 10. — Vlad from Moscow, Oct 21 '17 at 14:16

score 0 · Answer 4 · answered Oct 21 '17 at 13:53

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.

C++ STL set lower_bound wrong result

4 Answers4