Offset of elements in a C ++ array

Question

I developed a method called "rotate" for my class of class objects. I did what if there are elements in the stack: {0,2,3,4,5,6,7}, I would have to rotate the elements back and forth.

Where, if I need to turn forward 2 elements, then we get {3,4,5,6,7,0,2} in the array. And if I need to turn back or -3 elements, then, looking at the original array, it will be {5,6,7,0,2,3,4}

So the method that I developed works fine. Its just terribly ineffective IMO. I was wondering if I can combine an array using a mod statement? Or, if their useless code hanged around something that I did not understand yet, and so on.

I think my question is: how can I simplify this method? for example using less code .:-)

void stack::rotate(int r)
{
    int i = 0;
    while ( r > 0 ) // rotate postively.
    {
        front.n = items[top+1].n;
        for ( int j = 0; j < bottom; j++ )
        {
            items[j] = items[j+1];                                  
        }
        items[count-1].n = front.n;
        r--;
    }

    while ( r < 0 )  // rotate negatively.
    {
        if ( i == top+1 )
        {
            front.n = items[top+1].n;  
            items[top+1].n = items[count-1].n; // switch last with first
        }

        back.n = items[++i].n; // second element is the new back
        items[i].n = front.n; 
        if ( i == bottom )
        {
            items[count-1].n = front.n; // last is first
            i = 0;  
            r++;   
            continue;
        }
        else
        {
            front.n = items[++i].n;
            items[i].n  = back.n;
            if ( i == bottom )
            {
                i = 0;
                r++; 
                continue;
            }
        }
    }
}

Answer 1

rotate ( "mod"?)

.

// Helper function.
// Finds GCD. 
// See http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

// Number of assignments of elements in algo is
// equal to (items.size() + gcd(items.size(),r)).
void rotate(std::vector<int>& items, int r) {
  int size = (int)items.size();
  if (size <= 1) return; // nothing to do
  r = (r % size + size) % size; // fits r into [0..size)
  int num_cycles = gcd(size, r);
  for (int first_index = 0; first_index < num_cycles; ++first_index) {
    int mem = items[first_index]; // assignment of items elements
    int index = (first_index + r) % size, index_prev = first_index;
    while (index != first_index) {
      items[index_prev] = items[index]; // assignment of items elements
      index_prev = index;
      index = (index + r) % size;
    };
    items[index_prev] = mem; // assignment of items elements
  }
}

, , , .

Answer 2

"". , , 0 , , .

, , ( , ...).

Answer 3

, , "" . ...

class WrappedArray
{
  int length;
  int first;
  T *array;

  T get(int index)
  {
    return array[(first + index) % length];
  }

  int rotateForwards()
  {
    first++;
    if (first == length)
      first = 0;
  }
}

Answer 4

, , , . , std:: deque, (O (1)).

Answer 5

, , - .
, . , , (, ). , (ala std:: list) , O (n).

Answer 6

, " Boost" : " Boost.CircularBuffer

Answer 7

- , "Programming Pearls" ( 2, 2.3 " " ). - Rotating Algorithms 'Programming Pearls' . , , .

, -. , " " , " ". :)

,

• . . . .

, , abcdefg 2

abcde fg → → gf edcba → → fg abcde

P.S. "Programming Pearls". , Bentley ( ).

Answer 8

, front back, .n. , , , , Bentley.

#include <algorithm>

std::reverse(array    , array + r   );
std::reverse(array + r, array + size);
std::reverse(array    , array + size);