Shifting elements in array C++

Question

Hello,

Im wondering why my data in 'intFront' does not stay the same. Im shifting the elements in my array left:

void stack::rotate(int nRotations)
{
    for (; nRotations > 0 ;) // Number of Rotations to the left
    {
     intFront = &items[top+1].n; 
        for ( int shiftL = 0; shiftL < count-1; shiftL++ )
        {
            items[shiftL] = items[shiftL+1]; // shift left from the front
     }   
        items[count-1].n = *intFront;
        nRotations--; // decrement=0 will indicate no more rotations left
    }
}

Whats happening is that the first value or "head" or "front" of the array is put into a varaible 'intFront'. I rotate everything left by the given number of rotations, hoping to just make a simple transfer at the end. Guess not..

Answer 1

1. You overrun your array: read of items[shiftL+1] goes beyond array bounds at last iteration,
2. You save a pointer to member of a structure into intFront and then override these structures by value in the inner loop - that'll sure change value intFront points to,
3. There's no need for doing multiple copies, i.e. no need for two embedded loops, since you know by how much you need to shift (nRotations).

Answer 2

You're storing a pointer to a memory address, not the value itself. Thus when you shift things around in the array, what used to be in that memory address is overwritten, but the memory address is still constant. What you really want to be doing is storing the value of items[top+1].n (w/o the & in front) and then reassign it (without the * for dereferencing).

void stack::rotate(int nRotations)
{
    for (; nRotations > 0 ;) // Number of Rotations to the left
    {
            intFront = items[top+1].n; 
        for ( int shiftL = 0; shiftL < count-2; shiftL++ )
        {
            items[shiftL] = items[shiftL+1]; // shift left from the front
            }    
        items[count-1].n = intFront;
        nRotations--; // decrement=0 will indicate no more rotations left
    }
}

Nikolai's tips are good as well - you don't really need to do this in two nested loops (which is O(N^2)); you could do it with just a single loop (or two sequential loops for simplicity) which would be O(N) time.

Answer 3

You might consider using a valarray, it would save you from manually having to implement a shift/rotate operation on the array. See member functions rotate/crotate.