C++ STL 设置 lower_bound 错误结果

Question

我在使用 lower_bound 比较功能时遇到一些问题。

我有一组按对的第二个值排序的对，我正在尝试通过一个值从该组中获取 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

集合的排序必须像 <，而不是 <=。因为您有一个包含您要查找的键的元素，所以 <= 是错误的并且以错误的方式发送搜索。

同时，在 set 上使用 std::lower_bound 是一种浪费：迭代器不公开搜索结构，因此搜索实际上是线性的。如果定义 setCompareFunctorAux ::is_transparent.

，则可以使用 C++14 的 heterogeneous comparisons 避免这种情况

Answer 2

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

不，预期结果是 20，因为函数 "Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val."，您可以在 std::lower_bound 参考中阅读。

您不会得到此结果，因为您在 setCompareFunctorAux 结构中使用 <= 而不是 <。

导致你在搜索20的时候，从相等性上混淆了，搜索的时候走错了方向。

PS：与您的问题无关，但是 setCompareFunctor 不是有效的比较器，因为它不满足严格的弱排序。为此，只需将 <= 更改为 <。在 Operator< and strict weak ordering.

中阅读更多内容

Answer 3

你必须使用严格的 less 运算符来自C++ 2017标准（28.7排序及相关操作）

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

考虑到在被调用的算法中使用了运算符

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

};

这是一个演示程序

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

它的输出是

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

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

预期的正确结果是 20，因为有一个元素的第二个值等于 20，而您正在搜索恰好是 20。

考虑到模板 class std::set 有自己的成员函数 lower_bound.

Answer 4

我认为您正在努力实现与 std::lower_bound 不同的目标。

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

产出

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

根据 http://en.cppreference.com/w/ 中提供的文档，一切似乎都是合法的。

我假设您正在尝试使用一些技巧来放置 6->15，并且由于违反了其他响应者已经指出的弱顺序，同样的技巧中断了 std::lower_bound。

C++ STL 设置 lower_bound 错误结果

C++ STL set lower_bound wrong result

c++

algorithm

stl

function

lower-bound