std::ranges:: rotate
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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
定义于头文件
<algorithm>
|
||
|
调用签名
|
||
|
template
<
std::
permutable
I,
std::
sentinel_for
<
I
>
S
>
constexpr
ranges::
subrange
<
I
>
|
(1) | (C++20 起) |
|
template
<
ranges::
forward_range
R
>
requires
std::
permutable
<
ranges::
iterator_t
<
R
>>
|
(2) | (C++20 起) |
ranges::rotate
交换范围
[
first
,
last
)
中的元素，使得元素
*
middle
成为新范围的第一个元素，而
*
(
middle
-
1
)
成为最后一个元素。
[
first
,
last
)
不是有效范围，或
middle
不在
[
first
,
last
)
范围内，则行为未定义。
本页面描述的函数式实体是 算法函数对象 （非正式称为 niebloids ），即：
目录 |
参数
| first, last | - | 定义待旋转元素范围的 区间 的迭代器-哨位对 |
| r | - | 待旋转的元素范围 |
| middle | - | 指向旋转后应出现在范围起始位置的元素的迭代器 |
返回值
{
new_first, last
}
，其中
new_first
等价于
ranges::
next
(
first,
ranges::
distance
(
middle, last
)
)
并指向原由
first
所指向元素的新位置。
复杂度
最坏情况为 线性 ： ranges:: distance ( first, last ) 次交换。
注释
当
I
满足
bidirectional_iterator
或（更优情况下）
random_access_iterator
要求时，
ranges::rotate
在常见实现中具有更优效率。
实现（例如
MSVC STL
）可在迭代器类型满足
contiguous_iterator
概念且交换其值类型时既不调用非平凡特殊成员函数、也不通过
ADL
查找
swap
时启用向量化优化。
可能实现
另请参阅 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 仅为前向迭代器 auto next_it = middle; do { // 旋转第一个循环 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) { // 旋转后续循环 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)
|
反转范围中元素的顺序
(算法函数对象) |
|
旋转范围中元素的顺序
(函数模板) |