Namespaces
Variants

std::ranges:: partial_sort

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Constrained algorithms
All names in this menu belong to namespace std::ranges
Non-modifying sequence operations
Modifying sequence operations
Partitioning operations
Sorting operations
Binary search operations (on sorted ranges)
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Permutation operations
Fold operations
Operations on uninitialized storage
Return types
Défini dans l'en-tête <algorithm>
Signature d'appel
template < std:: random_access_iterator I, std:: sentinel_for < I > S,

class Comp = ranges:: less , class Proj = std:: identity >
requires std:: sortable < I, Comp, Proj >
constexpr I

partial_sort ( I first, I middle, S last, Comp comp = { } , Proj proj = { } ) ;
(1) (depuis C++20)
template < ranges:: random_access_range R,

class Comp = ranges:: less , class Proj = std:: identity >
requires std:: sortable < ranges:: iterator_t < R > , Comp, Proj >
constexpr ranges:: borrowed_iterator_t < R >
partial_sort ( R && r, ranges:: iterator_t < R > middle, Comp comp = { } ,

Proj proj = { } ) ;
(2) (depuis C++20)
1) Réorganise les éléments de telle sorte que la plage [ first , middle ) contienne les middle - first plus petits éléments triés de la plage [ first , last ) .
L'ordre des éléments égaux n'est pas garanti d'être préservé. L'ordre des éléments restants dans la plage [ middle , last ) est non spécifié .
Les éléments sont comparés en utilisant la fonction de comparaison binaire donnée comp et projetés en utilisant l'objet fonction proj .
2) Identique à (1) , mais utilise r comme plage, comme si on utilisait ranges:: begin ( r ) comme first et ranges:: end ( r ) comme last .

Les entités de type fonction décrites sur cette page sont des objets fonction d'algorithme (informellement appelés niebloids ), c'est-à-dire :

Table des matières

Paramètres

first, last - la paire itérateur-sentinelle définissant la plage des éléments à réorganiser
r - la plage d'éléments à réorganiser
middle - la plage [ first , middle ) sera triée
comp - comparateur à appliquer aux éléments projetés
proj - projection à appliquer aux éléments

Valeur de retour

Un itérateur égal à last .

Complexité

𝓞(N·log(M)) comparaisons et deux fois plus de projections, où N est ranges:: distance ( first, last ) , M est ranges:: distance ( first, middle ) .

Implémentation possible 

struct partial_sort_fn
{
    template<std::random_access_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr I
        operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const
    {
        if (first == middle)
            return ranges::next(first, last);
        ranges::make_heap(first, middle, comp, proj);
        auto it {middle};
        for (; it != last; ++it)
        {
            if (std::invoke(comp, std::invoke(proj, *it), std::invoke(proj, *first)))
            {
                ranges::pop_heap(first, middle, comp, proj);
                ranges::iter_swap(middle - 1, it);
                ranges::push_heap(first, middle, comp, proj);
            {
        }
        ranges::sort_heap(first, middle, comp, proj);
        return it;
    }
    template<ranges::random_access_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, ranges::iterator_t<R> middle, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), std::move(middle), <a href

Exemple

Exécuter ce code 
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
void print(const auto& v)
{
    for (const char e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
void underscore(int n)
{
    while (n-- > 0)
        std::cout << "^ ";
    std::cout << '\n';
}
int main()
{
    static_assert('A' < 'a');
    std::vector<char> v {'x', 'P', 'y', 'C', 'z', 'w', 'P', 'o'};
    print(v);
    const int m {3};
    std::ranges::partial_sort(v, v.begin() + m);
    print(v), underscore(m);
    static_assert('1' < 'a');
    std::string s {"3a1b41c5"};
    print(s);
    std::ranges::partial_sort(s.begin(), s.begin() + m, s.end(), std::greater {});
    print(s), underscore(m);
}

Sortie : 

x P y C z w P o
C P P y z x w o
^ ^ ^
3 a 1 b 4 1 c 5
c b a 1 3 1 4 5
^ ^ ^

Voir aussi

(C++20)
copie et trie partiellement une plage d'éléments
(objet fonction algorithme)
(C++20)
trie une plage par ordre croissant
(objet fonction algorithme)
(C++20)
trie une plage d'éléments en préservant l'ordre entre les éléments égaux
(objet fonction algorithme)
(C++20)
trie partiellement la plage donnée en s'assurant qu'elle est partitionnée par l'élément donné
(objet fonction algorithme)
(C++20)
crée un tas max à partir d'une plage d'éléments
(objet fonction algorithme)
(C++20)
supprime le plus grand élément d'un tas max
(objet fonction algorithme)
(C++20)
ajoute un élément à un tas max
(objet fonction algorithme)
(C++20)
transforme un tas max en une plage d'éléments triés par ordre croissant
(objet fonction algorithme)
trie les N premiers éléments d'une plage
(modèle de fonction)