std::ranges:: rotate

From cppreference.net

Défini dans l'en-tête `<algorithm>`
Signature d'appel
template < std:: permutable I, std:: sentinel_for < I > S > constexpr ranges:: subrange < I > rotate ( I first, I middle, S last ) ;	(1)	(depuis C++20)
template < ranges:: forward_range R > requires std:: permutable < ranges:: iterator_t < R >> constexpr ranges:: borrowed_subrange_t < R > rotate ( R && r, ranges:: iterator_t < R > middle ) ;	(2)	(depuis C++20)

1) Effectue une rotation vers la gauche sur une plage d'éléments. Plus précisément,


        ranges::rotate

échange les éléments dans la plage

first

last

de telle manière que l'élément * middle devienne le premier élément de la nouvelle plage et * ( middle - 1 ) devienne le dernier élément.

Le comportement est indéfini si

first

last

n'est pas une plage valide ou si middle n'est pas dans

first

last

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 :

Les listes d'arguments de modèle explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
Aucune d'entre elles n'est visible pour la recherche dépendante des arguments .
Lorsque l'une d'entre elles est trouvée par la recherche non qualifiée normale comme nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.

Table des matières

Paramètres

first, last	-	la paire itérateur-sentinelle définissant la plage des éléments à faire pivoter
r	-	la plage d'éléments à faire pivoter
middle	-	l'itérateur vers l'élément qui doit apparaître au début de la plage pivotée

Valeur de retour

{ new_first, last } , où new_first est équivalent à ranges:: next ( first, ranges:: distance ( middle, last ) ) et désigne la nouvelle position de l'élément pointé par first .

Complexité

Linéaire au pire : ranges:: distance ( first, last ) échanges.

Notes

ranges::rotate a une meilleure efficacité sur les implémentations courantes si I modélise bidirectional_iterator ou (encore mieux) random_access_iterator .

Les implémentations (par exemple MSVC STL ) peuvent activer la vectorisation lorsque le type d'itérateur modélise contiguous_iterator et que l'échange de son type de valeur n'appelle ni fonction membre spéciale non triviale ni ADL -trouvée swap .

Implémentation possible

Voir également les implémentations dans libstdc++ et MSVC STL .

struct rotate_fn
{
    template<std::permutable I, std::sentinel_for<I> S>
    constexpr ranges::subrange<I>
        operator()(I first, I middle, S last) const
    {
        if (first == middle)
        {
            auto last_it = ranges::next(first, last);
            return {last_it, last_it};
        }
        if (middle == last)
            return {std::move(first), std::move(middle)};
        if constexpr (std::bidirectional_iterator<I>)
        {
            ranges::reverse(first, middle);
            auto last_it = ranges::next(first, last);
            ranges::reverse(middle, last_it);
            if constexpr (std::random_access_iterator<I>)
            {
                ranges::reverse(first, last_it);
                return {first + (last_it - middle), std::move(last_it)};
            }
            else
            {
                auto mid_last = last_it;
                do
                {
                    ranges::iter_swap(first, --mid_last);
                    ++first;
                }
                while (first != middle && mid_last != middle);
                ranges::reverse(first, mid_last);
                if (first == middle)
                    return {std::move(mid_last), std::move(last_it)};
                else
                    return {std::move(first), std::move(last_it)};
            }
        }
        else
        { // I est simplement un forward_iterator
            auto next_it = middle;
            do
            { // faire pivoter le premier cycle
                ranges::iter_swap(first, next_it);
                ++first;
                ++next_it;
                if (first == middle)
                    middle = next_it;
            }
            while (next_it != last);
            auto new_first = first;
            while (middle != last)
            { // faire pivoter les cycles suivants
                next_it = middle;
                do
                {
                    ranges::iter_swap(first, next_it);
                    ++first;
                    ++next_it;
                    if (first == middle)
                        middle = next_it;
                }
                while (next_it != last);
            }
            return {std::move(new_first), std::move(middle)};
        }
    }
    template<ranges::forward_range R>
    requires std::permutable<ranges::iterator_t<R>>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, ranges::iterator_t<R> middle) const
    {
        return (*this)(ranges::begin(r), std::move(middle), ranges::end(r));
    }
};
inline constexpr rotate_fn rotate {};

Exemple

ranges::rotate est un composant fondamental dans de nombreux algorithmes. Cet exemple démontre le tri par insertion .

Exécuter ce code

#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
int main()
{
    std::string s(16, ' ');
    for (int k {}; k != 5; ++k)
    {
        std::iota(s.begin(), s.end(), 'A');
        std::ranges::rotate(s, s.begin() + k);
        std::cout << "Rotation gauche (" << k << "): " << s << '\n';
    }
    std::cout << '\n';
    for (int k {}; k != 5; ++k)
    {
        std::iota(s.begin(), s.end(), 'A');
        std::ranges::rotate(s, s.end() - k);
        std::cout << "Rotation droite (" << k << "): " << s << '\n';
    }
    std::cout << "\nTri par insertion utilisant `rotate`, étape par étape:\n";
    s = {'2', '4', '2', '0', '5', '9', '7', '3', '7', '1'};
    for (auto i = s.begin(); i != s.end(); ++i)
    {
        std::cout << "i = " << std::ranges::distance(s.begin(), i) << ": ";
        std::ranges::rotate(std::ranges::upper_bound(s.begin(), i, *i), i, i + 1);
        std::cout << s << '\n';
    }
    std::cout << (std::ranges::is_sorted(s) ? "Trié !" : "Non trié.") << '\n';
}

Sortie :

Rotation gauche (0): ABCDEFGHIJKLMNOP
Rotation gauche (1): BCDEFGHIJKLMNOPA
Rotation gauche (2): CDEFGHIJKLMNOPAB
Rotation gauche (3): DEFGHIJKLMNOPABC
Rotation gauche (4): EFGHIJKLMNOPABCD
Rotation droite (0): ABCDEFGHIJKLMNOP
Rotation droite (1): PABCDEFGHIJKLMNO
Rotation droite (2): OPABCDEFGHIJKLMN
Rotation droite (3): NOPABCDEFGHIJKLM
Rotation droite (4): MNOPABCDEFGHIJKL
Tri par insertion utilisant `rotate`, étape par étape :
i = 0: 2420597371
i = 1: 2420597371
i = 2: 2240597371
i = 3: 0224597371
i = 4: 0224597371
i = 5: 0224597371
i = 6: 0224579371
i = 7: 0223457971
i = 8: 0223457791
i = 9: 0122345779
Trié !

Voir aussi

ranges::rotate_copy (C++20)	copie et fait pivoter une plage d'éléments (objet fonction algorithme)
ranges::reverse (C++20)	inverse l'ordre des éléments dans une plage (objet fonction algorithme)
rotate	fait pivoter l'ordre des éléments dans une plage (modèle de fonction)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std::ranges:: rotate

Table des matières

Paramètres

Valeur de retour

Complexité

Notes

Implémentation possible

Exemple

Voir aussi