std::ranges::rotate
来自cppreference.com
定义于头文件 <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 起) |
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
时启用向量化。
可能的实现
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{std::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(fist, 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!
参阅
(C++20) |
复制并旋转元素范围 (niebloid) |
(C++20) |
逆转范围中的元素顺序 (niebloid) |
旋转范围中的元素顺序 (函数模板) |