C++ STL 设置 lower_bound 错误结果

Question

我在使用 lower_bound 比较函数时遇到了一些问题。

我有一组按对的第二个值排序的对，我试图通过一个值从这个集合中获取下界。

我当前的代码是:

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

预期结果是15，但实际结果是33。

怎么了？

Answer 1

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

不，预期结果是 20，因为函数“返回指向范围 [first,last) 中第一个元素的迭代器，它比较不小于 val。”，如您在 std::lower_bound 中所读引用。

你不会得到这个结果，因为你使用了<=而不是 <在你的setCompareFunctorAux结构。

因此，当你搜索20时，它被相等性迷惑了，并且在搜索时走向了错误的方向。

---

PS:与你的问题无关，但setCompareFunctor不是有效的比较器，因为它不满足严格的弱排序。为此，只需更改 <=至 < .在 Operator< and strict weak ordering 中阅读更多内容.