|
|
|
|
调用签名
|
|
|
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 。
此页面上描述的仿函数实体是 niebloid，即：
实际上，它们能以函数对象，或者某些特殊编译器扩展实现。
参数
| 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 仅为 forward_iterator
auto next_it = middle;
do
{ // rotate 第一循环
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 后继循环
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 {};
|
示例
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 << "\n" "Insertion 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!
参阅
|
|
复制并旋转元素范围
(niebloid) |
|
|
逆转范围中的元素顺序
(niebloid) |
|
|
旋转范围中的元素顺序
(函数模板) |