std::rotate
來自 cppreference.com
| 定義於標頭檔案 <algorithm> |
||
| template< class ForwardIt > ForwardIt rotate( ForwardIt first, ForwardIt middle, ForwardIt last ); |
(1) | (C++20 起為 constexpr) |
| template< class ExecutionPolicy, class ForwardIt > ForwardIt rotate( ExecutionPolicy&& policy, |
(2) | (C++17 起) |
1) 對元素範圍執行左旋轉。
具體來說，`std::rotate` 會交換範圍 `[first, last)` 中的元素，使得 `[first, middle)` 中的元素被放置在 `[middle, last)` 中的元素之後，同時保持兩個範圍中元素的順序。
2) 同 (1)，但根據 policy 執行。
僅當滿足以下所有條件時，此過載才參與過載決議
|
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 為 true。 |
(C++20 前) |
|
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 為 true。 |
(C++20 起) |
如果滿足以下任何條件，則行為是未定義的：
-
[first,middle)或[middle,last)不是有效範圍。
|
(C++11 前) |
|
(C++11 起) |
目錄 |
[編輯] 引數
| first, last | - | 定義要旋轉的元素範圍的迭代器對 |
| middle | - | 應該出現在旋轉範圍開頭的元素 |
| policy | - | 要使用的 執行策略 |
| 型別要求 | ||
-ForwardIt 必須滿足 LegacyForwardIterator 的要求。 | ||
[編輯] 返回值
指向最初由 *first 引用的元素的迭代器，即 first 的第 std::distance(middle, last) 個後繼迭代器。
[編輯] 複雜度
最多 std::distance(first, last) 次交換。
[編輯] 異常
帶有名為 ExecutionPolicy 的模板引數的過載會按如下方式報告錯誤：
- 如果作為演算法一部分呼叫的函式丟擲異常，並且 `ExecutionPolicy` 是標準策略之一，則呼叫 std::terminate。對於任何其他 `ExecutionPolicy`，行為是實現定義的。
- 如果演算法未能分配記憶體，則丟擲 std::bad_alloc。
[編輯] 可能的實現
另請參閱 libstdc++、libc++ 和 MSVC STL 中的實現。
template<class ForwardIt> constexpr // since C++20 ForwardIt rotate(ForwardIt first, ForwardIt middle, ForwardIt last) { if (first == middle) return last; if (middle == last) return first; ForwardIt write = first; ForwardIt next_read = first; // read position for when “read” hits “last” for (ForwardIt read = middle; read != last; ++write, ++read) { if (write == next_read) next_read = read; // track where “first” went std::iter_swap(write, read); } // rotate the remaining sequence into place rotate(write, next_read, last); return write; } |
[編輯] 注意
如果 `ForwardIt` 滿足 LegacyBidirectionalIterator 或（更好）LegacyRandomAccessIterator，`std::rotate` 在常見實現上具有更好的效率。
當迭代器型別滿足 LegacyContiguousIterator 並且其值型別的交換不呼叫非平凡的特殊成員函式或透過 ADL 找到的 `swap` 時，實現（例如 MSVC STL）可能會啟用向量化。
[編輯] 示例
`std::rotate` 是許多演算法中常見的構建塊。此示例演示了插入排序。
執行此程式碼
#include <algorithm> #include <iostream> #include <vector> auto print = [](const auto remark, const auto& v) { std::cout << remark; for (auto n : v) std::cout << n << ' '; std::cout << '\n'; }; int main() { std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1}; print("before sort:\t\t", v); // insertion sort for (auto i = v.begin(); i != v.end(); ++i) std::rotate(std::upper_bound(v.begin(), i, *i), i, i + 1); print("after sort:\t\t", v); // simple rotation to the left std::rotate(v.begin(), v.begin() + 1, v.end()); print("simple rotate left:\t", v); // simple rotation to the right std::rotate(v.rbegin(), v.rbegin() + 1, v.rend()); print("simple rotate right:\t", v); }
輸出
before sort: 2 4 2 0 5 10 7 3 7 1 after sort: 0 1 2 2 3 4 5 7 7 10 simple rotate left: 1 2 2 3 4 5 7 7 10 0 simple rotate right: 0 1 2 2 3 4 5 7 7 10
[編輯] 缺陷報告
下列更改行為的缺陷報告追溯地應用於以前出版的 C++ 標準。
| 缺陷報告 | 應用於 | 釋出時的行為 | 正確的行為 |
|---|---|---|---|
| LWG 488 | C++98 | 未返回由 `first` 指向的元素的新位置。 | 已返回 |
[編輯] 另請參閱
| 複製並旋轉一個範圍的元素 (函式模板) | |
| (C++20) |
旋轉一個範圍中元素的順序 (演算法函式物件) |
