c++ - std::upper_bound() 的库引用和编译器之间的奇怪差异

Question

我需要在组中处理类型为 Foo 的对象列表，共享对应于相同 Bar 值的质量。该列表已根据该质量进行了预先排序，因此我的想法是使用 std::upper_bound 来查找后续组的开始位置。

Bar FooToBar(const Foo &foo);
// sorted so that FooToBar(foolist[0] <= FooToBar(foolist[1]) <= ...
std::list<Foo> foolist; 

// find bounds of a group of Foo-s corresponding to someBar;
Bar someBar;
auto 
    groupBegin = foolist.begin(),
    // find last item of foolist whose FooToBar() == someBar
    groupEnd   = std::upper_bound( foolist.begin(), 
                                   foolist.end(), 
                                   someBar ); 

当然这不会起作用，因为 Foo 和 Bar 不能直接比较。幸运的是，std::upper_bound 有一个重载，它需要一个额外的比较器参数:

groupEnd = std::upper_bound( foolist.begin(), foolist.end(), someBar, Compare);

问题是，我该如何编写 Compare()？这就是事情变得有趣的地方。 cppreference.com说:

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function object must not modify the objects passed to it. The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2. ​

显然，我无法用 Foo 和 Bar 来满足这些条件。然而，cplusplus.com说点不一样的:

Binary function that accepts two arguments (the first is always val, and the second of the type pointed by ForwardIterator), and returns a value convertible to bool.

我可以使用它，所以:

bool Compare(const Bar &bar, const Foo &foo) { /* ... */ }

但是，这不会在 VS2013 或 g++ 中编译:

/usr/lib/gcc/x86_64-pc-cygwin/4.9.2/include/c++/bits/predefined_ops.h:141:37: error: cannot convert ‘Foo’ to ‘Bar’ in argument passing

奇怪的是，当我颠倒参数顺序时，它会按预期编译、运行和运行:

bool Compare(const Foo &foo, const Bar &bar) { /* ... */ }

所以看起来一个引用说的是一回事，另一个引用说的是另一回事，而编译器接受的东西仍然不同。还是我误解了什么？

Answer 1

您指的是标准中的缺陷:#270 .原始措辞被认为是严格的(实际上，提到了您的特定用例)。标准中的部分现在是 [upper.bound]:

template<class ForwardIterator, class T>
  ForwardIterator
    upper_bound(ForwardIterator first, ForwardIterator last,
                const T& value);

template<class ForwardIterator, class T, class Compare>
  ForwardIterator
    upper_bound(ForwardIterator first, ForwardIterator last,
                const T& value, Compare comp);

Requires: The elements e of [first,last) shall be partitioned with respect to the expression !(value < e) or !comp(value, e).
Returns: The furthermost iterator i in the range [first,last] such that for every iterator j in the range [first,i) the following corresponding conditions hold: !(value < *j) or comp(value, *j) == false.

在这两种情况下，value是 comp 的第一个参数元素是第二个。所以下面是完全有效的代码:

struct Foo { };
struct Bar { };

std::vector<Foo> foolist;

auto it = std::upper_bound(foolist.begin(), foolist.end(), Bar{}, 
                           [](Bar const&, Foo const&) { return false; });

以上内容适用于 gcc 5.2(甚至 4.6.4——对 lambda 取模——这是我可以轻松访问的最古老的版本)和 clang 3.6。