std::ranges:: rotate

From cppreference.net

헤더 파일에 정의됨 `<algorithm>`
함수 시그니처
template < std:: permutable I, std:: sentinel_for < I > S > constexpr ranges:: subrange < I > rotate ( I first, I middle, S last ) ;	(1)	(C++20부터)
template < ranges:: forward_range R > requires std:: permutable < ranges:: iterator_t < R >> constexpr ranges:: borrowed_subrange_t < R > rotate ( R && r, ranges:: iterator_t < R > middle ) ;	(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 로 사용하는 것과 같습니다.

이 페이지에서 설명하는 함수형 개체들은 algorithm function objects (일반적으로 niebloids 로 알려진)입니다. 즉:

명시적 템플릿 인수 목록은 이들 중 어느 것을 호출할 때도 지정할 수 없습니다.
이들 중 어느 것도 인수 의존 이름 검색 에 보이지 않습니다.
이들 중 어느 것이 함수 호출 연산자의 왼쪽 이름으로 일반 비한정 이름 검색 에 의해 발견될 때, 인수 의존 이름 검색 이 억제됩니다.

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
            { // 첫 번째 사이클을 회전합니다
                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)
            { // 후속 사이클 회전
                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 {};

예제

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!

참고 항목

ranges::rotate_copy (C++20)	요소 범위를 복사하고 회전시킴 (알고리즘 함수 객체)
ranges::reverse (C++20)	범위 내 요소들의 순서를 반전시킴 (알고리즘 함수 객체)
rotate	범위 내 요소들의 순서를 회전시킴 (함수 템플릿)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

first, last	-	range 를 정의하는 iterator-sentinel 쌍으로, 회전할 요소들의 범위를 나타냅니다
r	-	회전할 요소들의 범위
middle	-	회전된 범위의 시작 부분에 나타나야 할 요소를 가리키는 iterator

cppreference.net

Namespaces

Variants

std::ranges:: rotate

목차

매개변수

반환값

복잡도

참고 사항

가능한 구현

예제

참고 항목