Thread: Array Shifting C++

std::copy is wrong here, though, since it does a forward copy. You need std::reverse_copy.

Originally Posted by CornedBee

std::copy is wrong here, though, since it does a forward copy. You need std::reverse_copy.

I think std::copy() is correct for the example though.

EDIT:
Okay, I thought that it should be std::backward_copy(), but apparently not: it should be std::copy_backward() as the alternative. std::reverse_copy() would reverse the order of elements.

Doh! I misread the question. I thought Flaug wanted to shift to the left...
So I think Laserlight is right, std::copy_backward() is the right one to shift to the right.

But try this code out:

Code:

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void)
{
	string end = "";

	const int length = 6;
	char temp[length] = {'a','b','c','d','e','f'};
	for(int i=length-1; i>1; i--)
	{
		temp[i] = temp[i-1];
	}
	temp[1] = ' ';

	cout << "Original:" << endl;
	cout << "abcdef" << endl;

	cout << "\nCurrent:" << endl;
	for(int i=0; i<=length-1; i++)
	{
		cout << temp[i];
	}

	cout << endl << endl;

	/////////////////////////////////////////
	cout << "----------------------------------" << endl << endl;
	/////////////////////////////////////////

	const int length2 = 6;
	char chars[length2] = {'a','b','c','d','e','f'};

	cout << "Original set:" << endl;
	for (int i=0; i<=length2-1; i++)
	{
		cout << chars[i];
	}

	copy(&chars[1], &chars[length2-1], &chars[2]);
	chars[1] = 0;

	cout << endl << "\nNew set:" << endl;
	for (int i=0; i<=length2-1; i++)
	{
		cout << chars[i];
	}

	cin>>end;

return 0;
}

OUTPUT:

Original:
abcdef

Current:
a bcde

----------------------------------

Original set:
abcdef

New set:
a bcde


The above output is exactly what I need.

This reference says that you shouldn't use neither copy or copy_backward since the destination must not be within the range to be copied. (One might want to look up what the standard says.)

In any case the algorithm for such more specific shifting seems to be rotate and the previous example should look more like:

Code:

rotate(&chars[1], &chars[length2 - 1], &chars[length2]);
chars[1] = ' ';

BTW, the reason copy can work in this case is because std::copy for random access iterators and POD types can be implemented in terms of memmove (as GCC does) which allows for overlaps. However, memmove won't be used in other cases and the code wouldn't work if the type to be moved around was something like std::string etc.

Originally Posted by anon

This reference says that you shouldn't use neither copy or copy_backward since the destination must not be within the range to be copied. (One might want to look up what the standard says.)

Interesting, the standard says almost the same, except that the requirements are even more strict (no "if ... designate regions of storage" clause).

Originally Posted by anon

In any case the algorithm for such more specific shifting seems to be rotate and the previous example should look more like:

However, rotate does more work than necessary, and hence does not correctly describe what the algorithm intends to do.

EDIT:
On second thought, maybe rotate can correctly describe the algorithm, if we start by "chopping" the last element in the range off by setting it to be a "blank".

Probably the best idea would be to use a container that has the erase and insert methods (and an container of structs/classes over two-dimensional arrays).

Depending on why you're shifting the array you mightn't have to shift it at all... It all depends on what you take as your reference. It's a matter of perspective...

Code:

class rotateHandler {
private:
  int *arrayPointer;
  int arraySize;
  int root;

public:
  rotateHandler( int *array, int size )
    : arrayPointer(array), arraySize(size), root(0) {
  }

  void rotateRight( int offset=1 ) {
    root-=offset;
  }
  void rotateLeft( int offset=1 ) {
    root+=offset;
  }
  void centreArray( void ) {
    root = 0;
  }

  int &operator [] ( int offset ) {
    int position(root+offset);
    if ( root<0 )
      position += arraySize;

    return arrayPointer[ position % arraySize ];
  }
};

int main( void ) {
  const int arraySize( 6 );
  int array[arraySize] = { 4, 8, 15, 16, 23, 42 };
  std::cout<< "Original array: ";
  for ( int j=0; j<arraySize; j++ )
    std::cout<< array[j] << " ";

  rotateHandler cyclicArray( array, arraySize );

  // rotate left
  std::cout<< "\n\nRotating left...";
  for ( int i=0; i<arraySize; i++ ) {
    std::cout<< "\nShifted left " << i << " times - ";
    for ( int j=0; j<arraySize; j++ )
      std::cout<< cyclicArray[j] << " ";
    cyclicArray.rotateLeft();
  }

  // rotate right
  cyclicArray.centreArray();
  std::cout<< "\n\nShifting right...";
  for ( int i=0; i<arraySize; i++ ) {
    std::cout<< "\nRotated right " << i << " times - ";
    for ( int j=0; j<arraySize; j++ )
      std::cout<< cyclicArray[j] << " ";
    cyclicArray.rotateRight();
  }

  return 0;
}

My output:

Code:

Original array: 4 8 15 16 23 42

Rotating left...
Shifted left 0 times - 4 8 15 16 23 42
Shifted left 1 times - 8 15 16 23 42 4
Shifted left 2 times - 15 16 23 42 4 8
Shifted left 3 times - 16 23 42 4 8 15
Shifted left 4 times - 23 42 4 8 15 16
Shifted left 5 times - 42 4 8 15 16 23

Shifting right...
Rotated right 0 times - 4 8 15 16 23 42
Rotated right 1 times - 42 4 8 15 16 23
Rotated right 2 times - 23 42 4 8 15 16
Rotated right 3 times - 16 23 42 4 8 15
Rotated right 4 times - 15 16 23 42 4 8
Rotated right 5 times - 8 15 16 23 42 4

(if you're using this you'll have to check that root isn't less than -arraySize (can handle in the rotateLeft/Right functions)

Edit: I realise it's not what you're looking for, but thought of it when I read your question so thought I'd post it.