std::ranges::rotate
From 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) <span class="t-v">(1)</span> と同じですが、<code>r</code> を範囲として使用します。これは <code>ranges::begin(r)</code> を <code>first</code> として、<code>ranges::end(r)</code> を <code>last</code> として使用するのと同等です。
このページで説明されている関数のようなエンティティは、アルゴリズム関数オブジェクト（非公式にはニーブロイドとして知られている）です。つまり、
- これらのいずれかを呼び出す際に、明示的なテンプレート引数リストを指定することはできません。
- これらのいずれも実引数依存の名前探索には見えません。
- これらのいずれかが関数呼び出し演算子の左側の名前として通常の非修飾名探索によって見つかった場合、実引数依存の名前探索は抑制されます。
目次 |
[編集] Parameters
| first, last | - | 回転する要素の範囲を定義するイテレータ-センチネルペア |
| r | - | 回転する要素の範囲 |
| middle | - | 回転された範囲の先頭に配置されるべき要素を指すイテレータ |
[編集] Return value
{new_first, last}。ここで、new_first は ranges::next(first, ranges::distance(middle, last)) と比較して等しく、first が指していた要素の新しい位置を示します。
[編集] Complexity
最悪の場合線形: ranges::distance(first, last) 回の交換。
[編集] Notes
ranges::rotateは、Iがbidirectional_iterator、または（より良い）random_access_iteratorをモデルとする場合、一般的な実装でより効率的です。
イテレータ型が contiguous_iterator をモデル化し、その値型のスワップが自明でない特殊メンバ関数も ADL で見つかった swap も呼び出さない場合、実装 (例: MSVC STL) はベクトル化を有効にできる。
[編集] Possible implementation
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 is merely a forward_iterator auto next_it = middle; do { // rotate the first cycle 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 subsequent cycles 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 {}; |
[編集] Example
ranges::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 << "\nInsertion 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!
[編集] See also
| (C++20) |
要素の範囲をコピーして回転させる (アルゴリズム関数オブジェクト) |
| (C++20) |
範囲内の要素の順序を逆にする (アルゴリズム関数オブジェクト) |
| 範囲内の要素の順序を回転させる (関数テンプレート) |
