c++ - partition_point 和 lower_bound 有什么区别？

Question

C++11 包含算法 std::partition_point() .然而，对于我尝试过的所有情况，它给出的答案与 std::lower_bound() 相同。 .唯一的区别是方便的 T& value 参数。

我是否遗漏了什么，或者这两个函数做的事情或多或少是一样的？

Answer 1

它们基本上是等价的。这将是 lower_bound 的有效实现。 :

template <typename ForwardIterator, typename T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
    T const& value)
{
    return partition_point(first, last, [&](auto&& elem) {
        return elem < value;
    });
}

template <typename ForwardIterator, typename T, typename Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
    T const& value, Compare comp)
{
    return partition_point(first, last, [&](auto&& elem) {
        return comp(elem, value);
    });
}

这两种算法依赖于找到分区范围的分区点，它们只是采用不同的参数进行搜索(partition_point 的一元谓词，lower_bound 的值或值和二元谓词)。

我们通常会想到 lower_bound在具有二元谓词的排序范围的上下文中 - 即使关于这种谓词的完全排序范围是 not a requirement for that algorithm .

---

当我们这样做时，upper_bound也可以根据 partition_point 来实现, 只是操作数被翻转并且谓词被否定:

template <typename ForwardIterator, typename T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
    T const& value)
{
    return partition_point(first, last, [&](auto&& elem) {
        return !(value < elem);
    });
}

template <typename ForwardIterator, typename T, typename Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
    T const& value, Compare comp)
{
    return partition_point(first, last, [&](auto&& elem) {
        return !comp(value, elem);
    });
}

---

这两者的措辞有多么不同，这很奇怪。

lower_bound returns (upper_bound 的措辞是 similar):

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: *j < value or comp(*j, value) != false.

而 partition_point returns

An iterator mid such that all_­of(first, mid, pred) and none_­of(mid, last, pred) are both true.

这些短语是等效的，因为要求是对范围进行分区。但乍一看肯定不是这样。