如何将动态数组向右旋转？

Question

我有一个自定义数组对象。它有两个主要变量：

m_array = 指向动态数组的指针。

m_size - 数组的大小。该数组的大小为 10。

当我向左旋转时，效果很好：

 std::rotate(m_array + 0, m_array + 1, m_array + m_size);

这相当于：

// simple rotation to the left
std::rotate(v.begin(), v.begin() + 1, v.end());

当我尝试向右旋转时，出现运行时错误。

我需要相当于这个的：

// simple rotation to the right
std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());

我试过这个：

std::rotate(m_array + m_size, m_array + m_size + 1, m_array + 0);

我收到错误：无效的迭代器范围

所以，我以为这是 m_size，所以我尝试了这个：

std::rotate(m_array + m_size - 1, m_array + (m_size - 1) + 1, m_array + 0);

我也遇到同样的错误。

欢迎提出想法。

我尝试遵循的来源： http://en.cppreference.com/w/cpp/algorithm/rotate

Answer 1

要进行右旋转（借用您的短语），您希望范围是除数组中最后一个元素之外的所有内容。我将让您调整此代码以使其适用于可变大小的数组。

#include <algorithm>
#include <iostream>

int main() {
    int data[10] = { 0, 1, 2, 3, 4,
                     5, 6, 7, 8, 9 };
    auto print_all = [&data]() {
        for(auto v: data) {
            std::cout << v << ' ';
        }
        std::cout << '\n';
    };
    print_all();

    // rotate elements to the left
    std::rotate(data, data + 1, data + 10);
    print_all();

    // rotate element to the right, back to the original position
    std::rotate(data, data + 9, data + 10);
    print_all();
    return 0;
}

我的输出如下所示：

./rotate 
0 1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 0 
0 1 2 3 4 5 6 7 8 9 

Answer 2

std::rotate(v.rbegin(), v.rbegin() + 1, v.rend())

起作用的原因是它使用反向迭代器。这意味着

v.rbegin() + 1

实际上是在递减数组中的位置，并且等于

v.begin() + v.size() - 1

。 使用原始指针算术时，无法获得相同的反向迭代行为。您必须手动将左旋转转换为右旋转。这可以通过围绕阵列中心翻转旋转位置并执行左旋转来轻松完成。

左旋转或右旋转可以归结为将数组分成两部分，然后交换它们。左旋转还是右旋转只是决定了划分的位置。对于左旋转

k

，旋转点位于

k mod N

。对于右旋转，旋转点位于

-k mod N

，其中

N

是数组的总长度。这会选择原始数组中您希望位于新旋转数组的索引

0

处的索引。 所以下面右旋1，

std::rotate(v.rbegin(), v.rbegin() + 1, v.rend())

相当于按以下方式使用原始指针：

int* p = &v[0];
int n = v.size();
int k = -1;
std::rotate(p, p + mod(k, n), p + n);

其中 

mod()

是模运算（基本上是始终换行为正数的

%

运算符）：int mod(int x, int y) { return ((x % y) + y) % y; }

Answer 3