std:: partial_sort

Reorganiza los elementos de modo que el rango [ first , middle ) contenga los middle − first elementos más pequeños ordenados en el rango [ first , last ) .

El orden de los elementos iguales no está garantizado que se preserve. El orden de los elementos restantes en el rango [ middle , last ) no está especificado.

Si se satisface cualquiera de las siguientes condiciones, el comportamiento es indefinido:

• [ first , middle ) o [ middle , last ) no es un rango válido .

Parámetros

Complejidad

Dado \(\scriptsize M\) M como middle - first , \(\scriptsize N\) N como last - first :

Excepciones

Las sobrecargas con un parámetro de plantilla llamado ExecutionPolicy reportan errores de la siguiente manera:

• Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y ExecutionPolicy es uno de los standard policies , std::terminate es llamado. Para cualquier otro ExecutionPolicy , el comportamiento está definido por la implementación.
• Si el algoritmo falla al asignar memoria, std::bad_alloc es lanzado.

Implementación posible

Consulte también las implementaciones en libstdc++ y libc++ .

template<typename RandomIt>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::value_type VT;
    std::partial_sort(first, middle, last, std::less<VT>());
}

namespace impl
{
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void sift_down(RandomIt first, RandomIt last, const Compare& comp)
    {
        // sift down element at “first”
        const auto length = static_cast<std::size_t>(last - first);
        std::size_t current = 0;
        std::size_t next = 2;
        while (next < length)
        {
            if (comp(*(first + next), *(first + (next - 1))))
                --next;
            if (!comp(*(first + current), *(first + next)))
                return;
            std::iter_swap(first + current, first + next);
            current = next;
            next = 2 * current + 2;
        }
        --next;
        if (next < length && comp(*(first + current), *(first + next)))
            std::iter_swap(first + current, first + next);
    }
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp)
    {
        std::make_heap(first, middle, comp);
        for (auto i = middle; i != last; ++i)
        {
            if (comp(*i, *first))
            {
                std::iter_swap(first, i);
                sift_down(first, middle, comp);
            }
        }
    }
} // namespace impl
template<typename RandomIt, typename Compare>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp)
{
    impl::heap_select(first, middle, last, comp);
    std::sort_heap(first, middle, comp);
}

Notas

Algoritmo

El algoritmo utilizado es típicamente heap select para seleccionar los elementos más pequeños, y heap sort para ordenar los elementos seleccionados en el montón en orden ascendente.

Para seleccionar elementos, se utiliza un montículo (consulte heap ). Por ejemplo, para operator < como función de comparación, max-heap se utiliza para seleccionar middle − first elementos más pequeños.

Ordenación por montículos se utiliza después de la selección para ordenar [ first , middle ) elementos seleccionados (ver std::sort_heap ).

Uso previsto

std::partial_sort los algoritmos están diseñados para ser utilizados con números constantes pequeños de elementos seleccionados en el rango [ first , middle ) .

Ejemplo

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
void print(const auto& s, int middle)
{
    for (int a : s)
        std::cout << a << ' ';
    std::cout << '\n';
    if (middle > 0)
    {
        while (middle-- > 0)
            std::cout << "--";
        std::cout << '^';
    }
    else if (middle < 0)
    {
        for (auto i = s.size() + middle; --i; std::cout << "  ")
        {}
        for (std::cout << '^'; middle++ < 0; std::cout << "--")
        {}
    }
    std::cout << '\n';
};
int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print(s, 0);
    std::partial_sort(s.begin(), s.begin() + 3, s.end());
    print(s, 3);
    std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend());
    print(s, -4);
    std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{});
    print(s, -5);
}

5 7 4 2 8 6 1 9 0 3
0 1 2 7 8 6 5 9 4 3
------^
4 5 6 7 8 9 3 2 1 0
          ^--------
4 3 2 1 0 5 6 7 8 9
        ^----------

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares de C++ publicados anteriormente.

Véase también