Talk:cpp/algorithm/rotate

Order of parameters

I'd propose to discuss the parameters in the order in which they are accepted by rotate(): first, n_first, last. Otherwise the reader may be tricked into thinking that the order of parameters would be first, last, n_first (as has happened to me). --Extensive 01:30, 25 July 2013 (PDT)

I agree that the ordering on this particular function is a little tricky, so it's worth being more explicit. I made the parameter description list match the function-call order. -Nate 07:42, 25 July 2013 (PDT)

Example

Technically, the std:: prefixes weren't needed in those lines where I didn't have them (generate_n(), copy(), etc), due to ADL. Not that I mind. --Cubbi 15:07, 17 August 2011 (PDT)

Several reasons:

• Consistency.
• Clearier code as it may not be instantly clear, why std:: is omitted.
• It may break code in some circumstances, such as when the type of the argument is changed and ADL no longer applies.
• Not usable in templates where the argument is not necessarily from std:: (or any other) namespace.
• Probably most important: the code highlighter engine here makes links that point to the description page for most of the functions/classes, but only if std:: is prefixed. The list of the identifiers to make links for can unfortunately be updated only manually, so not all links work. A copy of the list resides [removed].

I think I can be wrong for the ADL as I'm not used to exploit it, but still, other points IMO make a strong case to have std:: everywhere.P12 01:36, 18 August 2011 (PDT)

OK, I agree, will use them. --Cubbi 06:57, 18 August 2011 (PDT)

Weird example

Why the weird example? Can't rotate() be called just once to demonstrate that it is essentially a modulo-shift and leave it at that? The example makes it look like rotate() is something you use in the process of sorting a range...

The page already says exactly what rotate() does, I believe it is instructive to show how it may be used in programming. Added a trivial call to rotate anyway. --Cubbi 04:03, 9 March 2012 (PST)

Thanks. And... I started replying and it devolved in a longer post with philosophical undertones about where the value of cppreference.com's pages lie. :) Is there a better place than here to post that?

Maybe in Talk:cpp? This seems the best place for general discussions. -P12 16:02, 9 March 2012 (PST)

Possible implementation seems wrong for C++11

Example:

 std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
 auto iter = std::rotate(v.begin(), v.begin() + 7, v.end());
 assert(*iter == 0); /* assertion fails*/

Possible implementation fails on corner case (n_first == last && first != n_first)

Example:

 std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
 auto iter = std::rotate(v.begin(), v.end(), v.end()); // endless loop, Segmentation fault

Much better (and correct) suggested implementation

 template<class ForwardIt>
 ForwardIt rotate(ForwardIt first, ForwardIt n_first, ForwardIt last)
 {
    if(first == n_first) return last;
    if(n_first == last) return first;

    auto read      = n_first;
    auto write     = first;
    auto next_read = first; // read position for when "read" hits "last"
    auto ret_value = last;

    while(write != last) {
       if(write == next_read) next_read = read;
       iter_swap(write++, read++);
       if(read == last) {
          if(ret_value == last)
             ret_value = write; // The first time wrapping: save the return value
          read = next_read;     // continue rotate from this position
          if(read == ret_value) {
             // no need to continue. We've "wrapped" into the special case
             // where the remaining elements are already in order
             break;
          }
       }
    }

    return ret_value;
 }

I exhaustively tested the solution on all rotations of all sequences less than 20 in length. The proof for how it works relies on some group theory... proving that when the algorithm "wraps", the remaining sequence just needs another rotate for "next_read". Sounds like a fun math problem, but I've got a day job...

Amichaux (talk) 05:08, 3 December 2018 (PST)

The "possible implementation" shown on the page is what STL had (we changed names and rewrote swap(*x, *y) as iter_swap(x, y)). Actual production implementations are a lot more complex and it's unclear how useful it is to present original code that is neither trivial nor representative of any popular implementation. --Cubbi (talk) 10:16, 3 December 2018 (PST)

Library code is often optimized for the code it generates on a wide variety of compilers. Thus, it has different goals to showing or explaining an algorithm. Clang/trunk has slightly better looking code than the given example, but it still obviates how the algorithm actually works. Notice that the 2nd part of the algorithm is doing the first part over and over again. Duplicating the code is confusing for someone trying to _understand_ how an implementation works. Also, comments help. -- Amichaux (talk) 11:13, 3 December 2018 (PST)

I agree about comments, and your impl has the nice property of having one loop and one call to swap, but that loop seems more complex than STL's two loops.. or perhaps I'm used to it? Another vote would be nice. --Cubbi (talk) 12:13, 3 December 2018 (PST)

If you didn't care about the return value, then then if condition could simply be if(read == last) read = next_read;. It would be clearer still to show the recursive nature of the algorithm, and change the while loop to while(read != last) {, and then after the while loop call rotate(write, next_read, last); return write;. I think that clearly shows the structure of the algorithm. -- Amichaux (talk) 13:34, 3 December 2018 (PST)

A much better example

The example should, as clearly as possible, demonstrate what the algorithm does. For those who find it difficult to parse the text. This is my suggestion:

int main(int, char **)
{
      for(auto i = 0u; i <= 10; ++i) {
         std::vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  
         // Rotate (modulo shift) 'i' to the first position
         std::rotate(begin(v), std::next(begin(v), i), end(v));

         // Print the resulting vector
         for(auto x : v) std::cout << x << " ";
         std::cout << std::endl;
      }
}

And the output:

0 1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 0 
2 3 4 5 6 7 8 9 0 1 
3 4 5 6 7 8 9 0 1 2 
4 5 6 7 8 9 0 1 2 3 
5 6 7 8 9 0 1 2 3 4 
6 7 8 9 0 1 2 3 4 5 
7 8 9 0 1 2 3 4 5 6 
8 9 0 1 2 3 4 5 6 7 
9 0 1 2 3 4 5 6 7 8 
0 1 2 3 4 5 6 7 8 9 

Amichaux (talk) 05:20, 3 December 2018 (PST)

current example shows a simple rotation, answers a frequently-asked question (how to rotate right) and demonstrates a simple non-trivial yet idiomatic use. Replacing that with ten simple rotations isn't an improvement. --Cubbi (talk) 10:16, 3 December 2018 (PST)

Okay, but it's also _unclear_. You may already know what rotate does, but try to put yourself in the shoes of someone who doesn't. If you want to show insertion sort, then the simple algorithm first. -- Amichaux (talk) 11:13, 3 December 2018 (PST)

I wouldn't mind reordering the example a little and adding some extra simple rotations for more clarity. T. Canens (talk) 16:44, 7 December 2018 (PST)

What about this implementation. It's meant to be clear, pedagogical.

template<class ForwardIt> ForwardIt rotate(ForwardIt first, ForwardIt n_first, ForwardIt last) { if(first == n_first) return last; if(n_first == last) return first;   ForwardIt read = n_first; ForwardIt write = first; ForwardIt next_read = first; // read position for when "read" hits "last"   while(read != last) { 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; }

-- Amichaux (talk) 11:01, 6 December 2018 (PST)

neat. I'd finish with a tail-rec: return rotate(... (if that would be correct). I won't object to this one (dunno about other editors) --Cubbi (talk) 12:27, 6 December 2018 (PST)

Unfortunately, rotate cannot be tail-recursive, which is why there's two while loops in the clang/gcc implementations. The second while loop is the "recursive" call, and in between, they're saving the return value. I'm going to go ahead and update the main page in a few hours if I don't hear anything back. Amichaux (talk) 12:36, 10 December 2018 (PST)

Let's use ForwardIt instead of auto. LGTM with that change. T. Canens (talk) 14:50, 10 December 2018 (PST)

Update with ForwardIt. Amichaux (talk) 15:06, 10 December 2018 (PST)

Return value

The text says the return value is "Iterator to the new location of the element pointed by first. Equal to first + (last - n_first)". The formula seems correct, but the description does not in the special case where `first == n_first`; in that case the return value is `last`. Maybe instead of "new location of the element pointed by first", the description could be "iterator to one-past the new location of the last element in the range"? In most cases, this _is_ the new location of the first element, but not in the case of a "null rotation". --Itub (talk) 14:51, 25 December 2022 (PST)

✔ Sounds reasonable, but we also should handle another "null rotation" case – when n_first == last. So, I've updated the Return value in more straightforward way.) --Space Mission (talk) 08:05, 26 December 2022 (PST)