Movatterモバイル変換


[0]ホーム

URL:


cppreference.com
Namespaces
Variants
    Actions

      std::ranges::rotate

      From cppreference.com
      <cpp‎ |algorithm‎ |ranges
       
       
      Algorithm library
      Constrained algorithms and algorithms on ranges(C++20)
      Constrained algorithms, e.g.ranges::copy,ranges::sort, ...
      Execution policies(C++17)
      Sorting and related operations
      Partitioning operations
      Sorting operations
      Binary search operations
      (on partitioned ranges)
      Set operations (on sorted ranges)
      Merge operations (on sorted ranges)
      Heap operations
      Minimum/maximum operations
      (C++11)
      (C++17)
      Lexicographical comparison operations
      Permutation operations
      C library
      Numeric operations
      Operations on uninitialized memory
       
      Constrained algorithms
      All names in this menu belong to namespacestd::ranges
      Non-modifying sequence operations
      Modifying sequence operations
      Partitioning operations
      Sorting operations
      Binary search operations (on sorted ranges)
             
             
      Set operations (on sorted ranges)
      Heap operations
      Minimum/maximum operations
      Permutation operations
      Fold operations
      Operations on uninitialized storage
      Return types
       
      Defined in header<algorithm>
      Call signature
      template<std::permutable I,std::sentinel_for<I> S>

      constexprranges::subrange<I>

          rotate( I first, I middle, S last);
      (1)(since C++20)
      template<ranges::forward_range R>

      requiresstd::permutable<ranges::iterator_t<R>>
      constexprranges::borrowed_subrange_t<R>

          rotate( R&& r,ranges::iterator_t<R> middle);
      (2)(since C++20)
      1) Performs aleft rotation on a range of elements. Specifically,ranges::rotate swaps the elements in the range[firstlast) in such a way that the element*middle becomes the first element of the new range and*(middle-1) becomes the last element.
      The behavior is undefined if[firstlast) is not a valid range ormiddle is not in[firstlast).
      2) Same as(1), but usesr as the range, as if usingranges::begin(r) asfirst andranges::end(r) aslast.

      The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:

      Contents

      [edit]Parameters

      first, last - the iterator-sentinel pair defining therange of elements to rotate
      r - the range of elements to rotate
      middle - the iterator to the element that should appear at the beginning of the rotated range

      [edit]Return value

      {new_first, last}, wherenew_first compares equal toranges::next(first,ranges::distance(middle, last)) and designates a new location of the element pointed byfirst.

      [edit]Complexity

      Linear at worst:ranges::distance(first, last) swaps.

      [edit]Notes

      ranges::rotate has better efficiency on common implementations ifI modelsbidirectional_iterator or (better)random_access_iterator.

      Implementations (e.g.MSVC STL) may enable vectorization when the iterator type modelscontiguous_iterator and swapping its value type calls neither non-trivial special member function norADL-foundswap.

      [edit]Possible implementation

      See also the implementations inlibstdc++ andMSVC STL.

      struct rotate_fn{template<std::permutable I,std::sentinel_for<I> S>constexprranges::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)}; ifconstexpr(std::bidirectional_iterator<I>){ranges::reverse(first, middle);auto last_it=ranges::next(first, last);ranges::reverse(middle, last_it); ifconstexpr(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)};elsereturn{std::move(first), std::move(last_it)};}}else{// I is merely a forward_iteratorauto next_it= middle;do{// rotate the first cycleranges::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>    requiresstd::permutable<ranges::iterator_t<R>>constexprranges::borrowed_subrange_t<R>        operator()(R&& r,ranges::iterator_t<R> middle)const{return(*this)(ranges::begin(r), std::move(middle),ranges::end(r));}}; inlineconstexpr rotate_fn rotate{};

      [edit]Example

      ranges::rotate is a common building block in many algorithms. This example demonstratesinsertion sort.

      Run this code
      #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';}

      Output:

      Rotate left (0): ABCDEFGHIJKLMNOPRotate left (1): BCDEFGHIJKLMNOPARotate left (2): CDEFGHIJKLMNOPABRotate left (3): DEFGHIJKLMNOPABCRotate left (4): EFGHIJKLMNOPABCD Rotate right (0): ABCDEFGHIJKLMNOPRotate right (1): PABCDEFGHIJKLMNORotate right (2): OPABCDEFGHIJKLMNRotate right (3): NOPABCDEFGHIJKLMRotate right (4): MNOPABCDEFGHIJKL Insertion sort using `rotate`, step-by-step:i = 0: 2420597371i = 1: 2420597371i = 2: 2240597371i = 3: 0224597371i = 4: 0224597371i = 5: 0224597371i = 6: 0224579371i = 7: 0223457971i = 8: 0223457791i = 9: 0122345779Sorted!

      [edit]See also

      copies and rotate a range of elements
      (algorithm function object)[edit]
      reverses the order of elements in a range
      (algorithm function object)[edit]
      rotates the order of elements in a range
      (function template)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/ranges/rotate&oldid=180522"

      [8]ページ先頭

      ©2009-2025 Movatter.jp