std::ranges::rotate
| Definido en el encabezado <algorithm>
|
||
| Firma de llamada |
||
template< std::permutable I, std::sentinel_for<I> S >
constexpr ranges::subrange<I>
rotate( I first, I middle, S last );
|
(1) | (desde 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) | (desde C++20) |
ranges::rotate intercambia los elementos en el rango [first, last) de tal manera que el elemento *middle se convierte en el primer elemento del nuevo rango y *(middle - 1) se convierte en el último elemento.[first, last) no es un rango válido o middle no está en [first, last).r como el rango, como si usara ranges::begin(r) como first y ranges::end(r) como last.Las entidades similares a funciones descritas en esta página son objetos función de algoritmo (conocidos informalmente como niebloids), es decir:
- Las listas de argumentos de plantilla explícitas no se pueden especificar al llamar a ninguno de ellos.
- Ninguno de ellos es visible para la búsqueda dependiente de argumentos.
- Cuando cualquiera de ellos se encuentra mediante búsqueda no calificada normal como el nombre a la izquierda del operador de llamada a función, la búsqueda dependiente de argumentos se inhibe.
Parámetros
| first, last | - | el par iterador-centinela que define el rango de elementos a rotar |
| r | - | el rango de elementos a rotar |
| middle | - | el iterador al elemento que debe aparecer al inicio del rango rotado |
Valor de retorno
{
new_first, last
}
, donde
new_first
es igual a
ranges::
next
(
first,
ranges::
distance
(
middle, last
)
)
y designa una nueva ubicación del elemento apuntado por
first
.
Complejidad
Lineal en el peor caso: ranges:: distance ( first, last ) intercambios.
Notas
ranges::rotate
tiene mejor eficiencia en implementaciones comunes si
I
modela
bidirectional_iterator
o (mejor aún)
random_access_iterator
.
Las implementaciones (por ejemplo,
MSVC STL
) pueden habilitar la vectorización cuando el tipo de iterador modela
contiguous_iterator
y el intercambio de su tipo de valor no llama ni a funciones miembro especiales no triviales ni a
ADL
-encontrado
swap
.
Implementación posible
Consulte también las implementaciones en libstdc++ y 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 es simplemente un forward_iterator auto next_it = middle; do { // rotar el primer ciclo 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) { // rotar ciclos subsiguientes 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 {}; |
Ejemplo
ranges::rotate
es un bloque de construcción común en muchos algoritmos. Este ejemplo demuestra
ordenamiento por inserción
.
#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 << "Rotate left (" << 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 << "Rotate right (" << k << "): " << s << '\n'; } std::cout << "\nInsertion sort using `rotate`, step-by-step:\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) ? "Sorted!" : "Not sorted.") << '\n'; }
Salida:
Rotate left (0): ABCDEFGHIJKLMNOP Rotate left (1): BCDEFGHIJKLMNOPA Rotate left (2): CDEFGHIJKLMNOPAB Rotate left (3): DEFGHIJKLMNOPABC Rotate left (4): EFGHIJKLMNOPABCD Rotate right (0): ABCDEFGHIJKLMNOP Rotate right (1): PABCDEFGHIJKLMNO Rotate right (2): OPABCDEFGHIJKLMN Rotate right (3): NOPABCDEFGHIJKLM Rotate right (4): MNOPABCDEFGHIJKL Insertion sort using `rotate`, step-by-step: 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 Sorted!
Véase también
|
(C++20)
|
copia y rota un rango de elementos
(objeto función de algoritmo) |
|
(C++20)
|
invierte el orden de los elementos en un rango
(objeto función de algoritmo) |
|
rota el orden de los elementos en un rango
(plantilla de función) |