std::upper_bound 和 std::lower_bound 的不同比较签名

Question

这是 std::lower_bound 和 std::upper_bound 的示例，请注意传递给它们的比较 lambda 的签名 -

const auto lower_x = std::lower_bound(
          points.begin(), points.end(), rec.min_corner.x,

          [](const RankedPoint &rp, const double x) { return rp.point.x < x; });

const auto upper_x = std::upper_bound(
          points.begin(), points.end(), rec.max_corner.x,

          [](const double x, const RankedPoint &rp) { return x < rp.point.x; });

保持签名完全相反的可能原因是什么？我不知道这一点，当我使用 auto 而不是带有错误签名的明确类型时，gcc 编译了它（clang 没有）。让我沮丧了 10 分钟。

Answer 1

lower_bound 和 upper_bound 的自定义比较器版本是简单使用 < 的概括。 lower_bound 产生第一个不小于 value 的元素，因此发生的检查是 elem < value（或实际上是 !(elem < value)）。 upper_bound 产生第一个元素 比 value 大 ，但我们不写 elem > value（这需要 operator>），我们只是将顺序翻转为 value < elem。这保持了 operator< 的唯一要求，但结果是参数的顺序颠倒了。

这概括了从 elem < value 到 comp(elem, value) 和 value < elem 到 comp(value, elem)。

最终，在设计时我们可以做出两种选择：我们可以在任何地方使用 same 比较器，但对于某些算法，参数的顺序是相反的。或者，我们可以为每种算法使用 不同的 比较器，具体取决于对特定算法有意义的内容。在任何地方使用相同的比较器有很多优点 - 你只需使用相同的比较器：

std::vector<int> vs = ...;
std::sort(vs.begin(), vs.end(), std::greater<>{});
auto lo = std::lower_bound(vs.begin(), vs.end(), 5, std::greater<>{});
auto hi = std::upper_bound(vs.begin(), vs.end(), 5, std::greater<>{});

到处都是相同的比较器，代码看起来是正确的，而且做的事情也是正确的。如果我们翻转 upper_bound() 传递给它的比较器的参数顺序，我们就必须传入 std::less<>{}。这只会……看起来不对。

您可能会对 Ranges TS 感兴趣，它通过可调用投影解决了这个问题。

std::upper_bound 和 std::lower_bound 的不同比较签名

different compare signature for std::upper_bound and std::lower_bound

c++

stl

c++-standard-library

c++11

c++14