partition_point 和 lower_bound 有什么区别？

Question

C++11 包含算法 std::partition_point(). However for all the cases I have tried it gives the same answer as std::lower_bound()。唯一的区别是方便的 T& value 参数。

我是不是漏掉了什么，或者这两个函数的作用大致相同？

Answer 1

它们或多或少是等价的，除了如果未提供谓词，lower_bound 将使用 operator< 来搜索元素。* partition_point 更通用，因为它允许该范围是根据一些通用谓词而不是一些针对 avalue.

的谓词进行分区的

请注意 lower_bound 大大早于 C++ 中更通用的分区概念的存在。

_{*并且在很大程度上暗示 lower_bound 中使用的谓词应该满足小于关系，尽管不是必需的}

来自 [alg.partitions]

template<class ForwardIterator, class Predicate> 
ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);

要求：ForwardIterator’s值类型应可转换为Predicate’s参数类型。 [first, last) 应按 pred 划分，即所有满足 pred 的元素应出现在满足 pred 的元素之前没有。

Returns：一个迭代器 mid 使得 all_of(first, mid, pred) 和 none_of(mid, last, pred) 是都是真的。

复杂性：O(log(last - first)) 应用pred。

来自 [lower.bound]

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

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

要求：[first, last) 的元素e 应根据表达式e < value 或comp(e, value) 进行分区。

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

复杂度：最多log2(last - first) + O(1)次比较。

Answer 2

他们都使用二进制搜索算法（用于随机访问迭代器）。

std::lower_bound 要求范围 ~~根据（二进制）谓词~~ 排序相对于表达式 element < value 或 comp(element, value) （如果范围是根据二进制谓词排序的情况）。
std::partition_point 要求根据（一元）谓词对范围进行分区。

您确实可以创建一个能够使用其他算法的谓词。

有：

const std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};

你可以用 lower_bound:

assert(std::is_sorted(v.begin, v.end(), std::less<>));
auto it1 = std::lower_bound(v.begin, v.end(), 5, std::less<>);

或 partition_point:

auto pred = [](int e){ return e < 5; }
assert(std::is_partition(v.begin, v.end(), pred));
auto it2 = std::partition_point(v.begin, v.end(), pred);

assert(it1 == it2); // *it1 = 5

或者，与另一边

const std::vector<int> v{1, 3, 4, 2, 7, 5, 8, 6};

你可以用 partition_point:

auto pred = [](int e){ return e < 5; }
assert(std::is_partition(v.begin, v.end(), pred));
auto it1 = std::partition_point(v.begin, v.end(), pred);

或 lower_bound:

auto pred2 = [](int lhs, int rhs){ return (lhs < 5) > (rhs < 5); }
assert(std::is_sorted(v.begin, v.end(), pred2));
auto it2 = std::lower_bound(v.begin, v.end(), 5, pred2);

assert(it1 == it2); // *it1 == 7

Answer 3

它们基本上是等价的。这将是 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 的一元谓词，与 [= 的值或值和二元谓词12=]).

我们通常只是在带有二元谓词的排序范围的上下文中考虑 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 (the upper_bound wording is 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.

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

partition_point 和 lower_bound 有什么区别？

What is the difference between partition_point and lower_bound?

c++

partitioning

std

binary-search

c++11