upper - lower bound c++

¿Cuál es la diferencia entre partition_point y lower_bound?

Question

C ++ 11 incluye el algoritmo std::partition_point() . Sin embargo, para todos los casos que he probado, da la misma respuesta que std::lower_bound() . La única diferencia es el conveniente parámetro T& value .

¿Me perdí algo o estas dos funciones están haciendo más o menos lo mismo?

Answer 1

Ambos utilizan un algoritmo de búsqueda binario (para iterador de acceso aleatorio).

• std::lower_bound requiere que el rango se std::lower_bound acuerdo con el predicado (binario) particionado con respecto al element < value expresión element < value o comp(element, value) (que es el caso si el rango se ordena de acuerdo con el predicado binario).
• std::partition_point requiere que el rango se particione de acuerdo con el predicado (unario).

De hecho, puede crear un predicado para poder utilizar el otro algoritmo.

Con:

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

Puedes hacerlo con lower_bound :

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

o con 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

O bien, con el otro lado.

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

Puedes hacerlo con 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);

o con 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

Son básicamente equivalentes. Esta sería una implementación válida de 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);
    });
}

Los dos algoritmos se basan en encontrar el punto de partición de un rango particionado, simplemente toman diferentes argumentos con los que buscar (un predicado unario para partition_point , vs un valor o valor y un predicado binario para lower_bound ).

Por lo general, solo pensamos en lower_bound en el contexto de rango ordenado con un predicado binario, aunque un rango completamente ordenado con respecto a dicho predicado no es un requisito para ese algoritmo .

Mientras estamos en ello, upper_bound también se puede implementar en términos de partition_point , solo con los operandos volteados y el predicado negado:

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);
    });
}

Es extraño lo diferente que están redactados los dos.

devoluciones de lower_bound (la redacción de upper_bound es similar ):

El iterador más lejano i en el rango [first, last] , de manera que para cada iterador j en el rango [first, i) cumplen las siguientes condiciones correspondientes: *j < value o comp(*j, value) != false .

mientras partition_point devuelve

Un iterador mid tal que all_of(first, mid, pred) y none_of(mid, last, pred) son ambos true .

Esas frases son equivalentes ya que el requisito es que el rango esté particionado. Pero seguro que no parece ser así a primera vista.

Answer 3

Son más o menos equivalentes, excepto que lower_bound utilizará el operator< para buscar los elementos si no se proporciona un predicado. * partition_point es más genérico, ya que permite que el rango se particione según un predicado genérico en lugar de algún predicado contra un value .

Tenga en cuenta que lower_bound es anterior a la existencia de más conceptos de partición genéricos en C ++.

_{* y está fuertemente implícito que el predicado usado en lower_bound debe satisfacer una relación menor que, aunque no es obligatorio}

De [alg.partitions]

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

Requiere : ForwardIterator''s tipo de valor ForwardIterator''s será convertible al tipo de argumento Predicate''s . [first, last) se pred por pred , es decir, todos los elementos que satisfacen pred antes de los que no.

Devoluciones : un medio iterador tal que all_of(first, mid, pred) y none_of(mid, last, pred) son verdaderos.

Complejidad : O(log(last - first)) aplicaciones de pred .

Y desde [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);

Requiere : Los elementos e de [first, last) se particionarán con respecto a la expresión e < value o comp(e, value) .

Devoluciones : El iterador más avanzado i en el rango [first, last] modo que para cada iterador j en el rango [first, i) cumplen las siguientes condiciones correspondientes: *j < value o comp(*j, value) != false .

Complejidad : a lo sumo log2(last - first) + O(1) comparaciones.