c++algorithm

What is the reason why std::rotate() is implemented this way?


According to cppreference the return value of std::rotate() is

The iterator to the element originally referenced by *first, i.e. the std::distance(middle, last) th next iterator of first.

And this is the possible implementation:

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;
}

if (first == middle) || (middle == last), there is nothing useful to do with a container, thus the function returns immediately. That makes sense. But why are different iterators returned in that case? Why return last if first == middle and return first if middle == last? Why not return first in either case? Just curious. If it is implemented this way, there should be a reason for this. What is the point?


Solution

  • Here is a rotation. The caret ^ indicates middle of the input (left) and the returned iterator in the result (right).

    AABBB  ->   BBBAA
      ^            ^
    

    Now let's vary the input and look at the results.

    In the first case, shrink the AA part down to the empty sequence:

    AABBB  ->   BBBAA
      ^            ^
    ABBBB  ->   BBBBA
     ^              ^
    BBBBB  ->   BBBBB
    ^                ^
    

    As you can see, when middle == first, it makes sense that the returned iterator is last.

    In the second case, let the BBB part shrink to the empty sequence:

    AABBB  ->   BBBAA
      ^            ^
    AAABB  ->   BBAAA
       ^          ^
    AAAAB  ->   BAAAA
        ^        ^
    AAAAA  ->   AAAAA
         ^      ^
    

    And here it makes sense that the returned iterator is first when middle == last.