Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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:

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading