std::rotate
| ヘッダー <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以降) |
std::rotate は範囲 [first, last) 内の要素を、[first, middle) 内の要素が [middle, last) 内の要素の後に配置されるように交換します。このとき、両方の範囲内の要素の順序は保持されます。|
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以降) |
目次 |
[edit] パラメータ
| first, last | - | 回転させる要素の範囲を定義するイテレータのペア |
| middle | - | 回転された範囲の先頭に来るべき要素 |
| policy | - | 使用する 実行ポリシー |
| 型要件 | ||
-ForwardIt は LegacyForwardIterator の要件を満たさなければなりません。 | ||
[edit] 戻り値
*first が元々参照していた要素へのイテレータ、つまり first から std::distance(middle, last)番目進んだイテレータ。
[edit] 計算量
std::distance(first, last) 回以下のスワップ。
[edit] 例外
テンプレートパラメータ ExecutionPolicy を持つオーバーロードは、次のようにエラーを報告します。
- アルゴリズムの一部として呼び出された関数の実行が例外をスローし、
ExecutionPolicyが 標準ポリシー のいずれかである場合、std::terminate が呼び出されます。その他のExecutionPolicyの場合、動作は実装定義です。 - アルゴリズムがメモリの割り当てに失敗した場合、std::bad_alloc がスローされます。
[edit] 実装例
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; } |
[edit] 注記
一般的な実装では、ForwardIt が LegacyBidirectionalIterator を満たす場合、または（さらに良いことに）LegacyRandomAccessIterator を満たす場合、std::rotate はより効率的です。
実装（例：MSVC STL）は、イテレータの型がLegacyContiguousIteratorを満たし、その値型のスワップが自明でない特殊メンバ関数もADLで見つかるswapも呼び出さない場合、ベクトル化を有効にできます。
[edit] 例
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
[edit] 不具合報告
以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。
| DR | 適用対象 | 公開された動作 | 正しい動作 |
|---|---|---|---|
| LWG 488 | C++98 | first が指す要素の新しい位置が返されませんでした。 |
返されます |
[edit] 関連項目
| 要素の範囲をコピーして回転させる (関数テンプレート) | |
| (C++20) |
範囲内の要素の順序を回転させる (アルゴリズム関数オブジェクト) |
