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带有二元谓词的排序范围的上下文 - 即使相对于这样的谓词的完全排序范围不是该算法的要求.

虽然我们在它,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返回(upper_bound措辞类似):

范围中的最远迭代器i,对于范围[first, last]中的每个迭代器j,[first, i)以下相应条件成立:*j < value或comp(*j, value) != false.

而partition_point回归

迭代器mid,使得all_­of(first, mid, pred)和none_­of(mid, last, pred)都是true.

这些短语是等价的,因为要求是范围是分区的.但乍看之下肯定不是这样.