原地旋转C++实践

Question

对于我的“item”int数组，我有一个有效的旋转函数。下面的代码实现了这一点，除了im不必要地将值传出。我正在尝试实现“原地”旋转。我的意思是ptrs会在哪里递增或递减，而不是从array..By中获取值，我需要以这种方式为这个method..Any建议“提升”效率水平？

void quack::rotate(int nRotations)
{
 if ( count <= 1 ) return;
 else  // make sure our ptrs are where we want them.
 {
  intFrontPtr = &items[0].myInt;
  intBackPtr  = &items[count-1].myInt;
 }
 for (int temp = 0; nRotations != 0;)
 {
  if ( nRotations > 0 )
  {
     temp = *intFrontPtr;
    *intFrontPtr = *intBackPtr;
    *intBackPtr  = temp; // Connect temps for the rotation
   --intBackPtr; // Move left [...<-] into the array
  }
  else if ( nRotations < 0 ) 
  {
   temp = *intBackPtr;
   *intBackPtr  = *intFrontPtr;
   *intFrontPtr = temp; // Connect temps for the rotation
   ++intFrontPtr; // Move right [->...] into the array
  }
  if ( intBackPtr  == &items[0].myInt  || 
    intFrontPtr == &items[count-1].myInt ) 
  {
   intFrontPtr = &items[0].myInt; 
   intBackPtr  = &items[count-1].myInt; // need to re-set
   if ( nRotations > 0 ) nRotations--;  // Which ways did we rotate?
   else nRotations++;
  }
 }
 }

哦，是的，我正在尝试练习c++，我知道他们有很多浮动的函数，它们被编程来做这个already...Im试图“构建我自己的”。我想我已经从语法上把它写下来了，但效率始终是我努力的地方。作为一个新手，我非常感谢对这方面的批评..

Answer 1

旋转数组中的元素有一个古老的技巧(我第一次看到它是在编写Pearls程序时)

假设您想将一个数组向左旋转三个元素。

首先颠倒前三个元素，然后颠倒其余元素，然后颠倒整个数组。

Starting Array:
1 2 3 4 5 6 7

After reversing the first three elements
3 2 1 4 5 6 7

After reversing the remaining elements
3 2 1 7 6 5 4

Finally reverse the entire array to get the final rotated array
4 5 6 7 1 2 3

数组的反转部分可以就地完成，因此您不需要任何额外的内存。

Answer 2

您可以将数据保留在适当的位置，并有一个“基本索引”成员来指示数组应该从哪里开始。然后，您需要在访问数组时使用它来调整索引。数组本身应该是私有的，并且只能通过执行调整的访问器函数进行访问。如下所示：

class quack
{
public:
    explicit quack(int size) : items(new Item[size]), size(size), base(0) {}
    ~quack() {delete [] items;}

    void rotate(int n)      {base = (base + n) % size;}
    Item &operator[](int i) {return items[(base + i) % size];}

private:
    quack(quack const&) = delete;          // or implement these if you want
    void operator=(quack const&) = delete; // the container to be copyable

    Item *items;
    int   size;
    int   base;
};

虽然我称它为RotatableArray，而不是quack。

Answer 3

一个接一个地做旋转真的不是一种方法。如果你做的任何事情超过2到3次旋转，它就会变得非常慢，非常快。

编辑:作为最后的想法...将元素放在一个(双)链接的“循环”列表中(以便最后一个元素指向第一个元素)，只需要旋转几个元素就可以将头指针移动几个元素。(头指针是指示循环列表中的哪个元素是开始的指针)。

这是迄今为止对元素列表进行旋转的最快(也是最简单)的方法