В чем разница между partition_point и lower_bound?

Question

C ++ 11 включает в себя алгоритм std::partition_point(). Однако для всех случаев, которые я пробовал, он дает тот же ответ, что и std::lower_bound(). Единственное отличие заключается в удобном параметре T& value.

Я что-то упустил или эти две функции выполняют более или менее одно и то же?

Answer 1

Они оба используют алгоритм двоичного поиска (для итератора произвольного доступа).

• 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 2

Они в основном эквивалентны. Это будет правильная реализация 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.

Эти фразы эквивалентны, поскольку требуется, чтобы диапазон был разделен. Но на первый взгляд это не так.

Answer 3

Они более или менее эквивалентны, за исключением того, что lower_bound будет использовать operator< для поиска элементов, если предикат не указан. * partition_point является более общим в том смысле, что он позволяет разделить диапазон в соответствии с некоторым общим предикат, а не какой-то предикат против value.

Обратите внимание, что 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, должны появляться перед теми, которые соответствуют нет.

Возвращает : середина итератора такая, что 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);

Требуется : элементы e из [first, last) должны быть разделены относительно выражения e < value или comp(e, value).

Возвращает : самый дальний итератор i в диапазоне [first, last] такой, что для каждого итератора j в диапазон [first, i) выполняются следующие соответствующие условия: *j < value или comp(*j, value) != false.

Сложность : Максимум log2(last - first) + O(1) сравнения.