std::ranges::rotate
| 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) |
ranges::rotate échange les éléments dans la plage [first, last) de telle sorte que l'élément *middle devient le premier élément de la nouvelle plage et *(middle - 1) devient le dernier élément.[first, last) n'est pas une plage valide ou middle n'est pas dans [first, last).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 fonctions algorithmes (informellement appelés niebloïdes), 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'elles.
- Aucune d'elles n'est visible par recherche dépendante des arguments.
- Lorsque l'une d'elles est trouvée par recherche non qualifiée normale comme nom à gauche de l'opérateur d'appel de fonction, recherche dépendante des arguments est inhibée.
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
.
#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
|
(C++20)
|
copie et fait pivoter une plage d'éléments
(objet fonction algorithme) |
|
(C++20)
|
inverse l'ordre des éléments dans une plage
(objet fonction algorithme) |
|
fait pivoter l'ordre des éléments dans une plage
(modèle de fonction) |