c++ 如何将动态数组向右旋转?

h9a6wy2h  于 2023-01-22  发布在  其他
关注(0)|答案(2)|浏览(146)

我有一个自定义数组对象,它有两个主要变量:
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

i86rm4rw

i86rm4rw1#

要进行右循环(借用您的说法),您希望范围是数组中的所有元素,* 除了 * 最后一个元素。我将让您修改此代码以处理可变大小的数组。

#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
sgtfey8w

sgtfey8w2#

std::rotate(v.rbegin(), v.rbegin() + 1, v.rend())工作的原因是它使用了反向迭代器,这意味着v.rbegin() + 1实际上是在递减数组中的位置,等于v.begin() + v.size() - 1
当使用原始指针算法时,无法获得相同的反向迭代行为。您必须手动将左旋转转换为右旋转。这可以通过围绕数组中心翻转旋转位置并执行左旋转来轻松完成。
左旋转或右旋转可以归结为将数组分为2个部分,然后交换它们。无论是左旋转还是右旋转,只是规定了划分的位置。对于左旋转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; }

相关问题