std::rotate()这样实现的原因是什么？

Question

根据cppreference，

std::rotate()

的返回值为

最初由 *first 引用的元素的迭代器，即 std::distance(middle, last) 第一个的下一个迭代器。

这是可能的实现：

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)

，对容器没有任何用处，因此函数立即返回。这是有道理的。但为什么在这种情况下会返回不同的迭代器呢？为什么如果

last

则返回

first == middle

，如果

first

则返回

middle == last

？为什么在任何一种情况下都不返回

first

？只是好奇。如果这样实施的话，应该是有原因的。重点是什么？

Answer 1

这里是轮换。插入符号

^

表示输入（左）和结果中返回的迭代器（右）的

middle

。

AABBB  ->   BBBAA
  ^            ^

现在让我们将

AA

部分缩小到空序列：

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

如您所见，当

middle == first

时，结果是

last

是有道理的。

现在让

BBB

部分缩小到空序列：

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

在这里，如果

first

，则返回

middle == last

是有意义的。