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

如果您阅读了您在问题中引用的文档部分，您就会明白，除非存在从 Bar 到 Foo 的隐式转换，否则 [=12= 的两个版本] 不正确。一个版本有效的事实只是一个幸运的巧合。使用不同的编译器可能很容易失败。

Answer 2

您指的是标准中的缺陷：#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。

std::upper_bound() 的库参考和编译器之间的奇怪差异

Strange discrepancy between library reference and compiler for std::upper_bound()

c++

stl

c++-standard-library