std::ranges::rotate
Объявлен в заголовочном файле <algorithm> | ||
|---|---|---|
| Сигнатура вызова | ||
template< std::permutable I, std::sentinel_for<I> S >
constexpr ranges::subrange<I>
rotate( I first, I middle, S last );
| (1) | (начиная с 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) | (начиная с C++20) |
1) Выполняет циклический сдвиг влево диапазона элементов. В частности,
ranges::rotate меняет местами элементы диапазона [first, last) таким образом, что элемент *middle становится первым элементом нового диапазона, а *(middle - 1) — последним элементом.
Поведение не определено, если
[first, last) не является допустимым диапазоном или middle не находится в [first, last).
2) То же, что и (1), но в качестве диапазона используется
r, как если бы ranges::begin(r) использовался в качестве first, а ranges::end(r) — в качестве last.Описанные на этой странице функциональные объекты являются объектами-функциями алгоритмов (неофициально известными как niebloids), то есть:
- При вызове любого из них нельзя указывать явные списки аргументов шаблона.
- Ни один из них не виден при поиске, зависящем от аргументов.
- Если любой из них найден при обычном неквалифицированном поиске в качестве имени слева от оператора вызова функции, поиск, зависящий от аргументов, подавляется.
Параметры
| first, last | - | пара итератора и сентинела, задающая диапазон элементов для циклического сдвига |
| r | - | диапазон элементов для циклического сдвига |
| middle | - | итератор на элемент, который должен стать первым в диапазоне после циклического сдвига |
Возвращаемое значение
{new_first, last}, где new_first сравнивается с ranges::next(first, ranges::distance(middle, last)) и указывает новое положение элемента, на который указывает first.
Сложность
В худшем случае линейная: ranges::distance(first, last) обменов.
Примечания
ranges::rotate обычно работает эффективнее, если I моделирует bidirectional_iterator или (что предпочтительнее) random_access_iterator.
Реализации (например, MSVC STL) могут включать векторизацию, если тип итератора моделирует contiguous_iterator, а обмен значениями его типа не вызывает ни одну нетривиальную специальную функцию-член и ни один swap, найденный посредством ADL.
Возможная реализация
См. также реализации в libstdc++ и 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 is merely a forward_iterator
auto next_it = middle;
do
{ // rotate the first 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)
{ // rotate subsequent cycles
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 {};
|
Пример
ranges::rotate — распространённый строительный блок многих алгоритмов. В этом примере демонстрируется сортировка вставками.
#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';
}
Вывод:
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!
См. также
|
(C++20) | копирует диапазон элементов и выполняет его циклический сдвиг (функциональный объект алгоритма) |
|
(C++20) | изменяет порядок элементов диапазона на обратный (функциональный объект алгоритма) |
| выполняет циклический сдвиг элементов диапазона (шаблон функции) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/rotate
