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) 中則行為未定義。此頁面上描述的函數式實體是算法函數對象（非正式地稱為 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 = 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 << "向左旋转 (" << 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 << "向右旋转 (" << k << "): " << s << '\n'; } std::cout << "\n" "用 `rotate` 实现插入排序，逐步运行:\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) ? "已排序!" : "未排序.") << '\n'; }
輸出：
向左旋转 (0): ABCDEFGHIJKLMNOP 向左旋转 (1): BCDEFGHIJKLMNOPA 向左旋转 (2): CDEFGHIJKLMNOPAB 向左旋转 (3): DEFGHIJKLMNOPABC 向左旋转 (4): EFGHIJKLMNOPABCD 向右旋转 (0): ABCDEFGHIJKLMNOP 向右旋转 (1): PABCDEFGHIJKLMNO 向右旋转 (2): OPABCDEFGHIJKLMN 向右旋转 (3): NOPABCDEFGHIJKLM 向右旋转 (4): MNOPABCDEFGHIJKL 用 `rotate` 实现插入排序，逐步运行: 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 已排序!
[編輯] 參閱
| (C++20) |
複製並旋轉元素範圍 (算法函數對象) |
| (C++20) |
逆轉範圍中的元素順序 (算法函數對象) |
| 旋轉範圍中的元素順序 (函數模板) |
