How can I rotate like this in 2d array?

[Slade316]

Rotate the content of the rows by 1 in the forward direction as shown below
Befo re Rotatmg
56 15 1 7
0 0 0 0
0 0 0 0
After Rotating
0 0 0 0
56 15 I 7
0 0 0 0

[Duthomhas]

Are you talking about straight-forward up/down rotation, as in:

row1     row3
row2 --> row1
row3     row2

?

Use std::rotate()
http://www.cplusplus.com/reference/algorithm/rotate/

Hope this helps.

[andywestken]

If you're in the pre-algorithm phase of your C++ education...

You just have to iterate through the columns of the 2D array and rotate the values in each column. For up you need to (1) set value in first row (index (i) = 0) aside, (2) set value for row 1 (i = 0) = value for row 2 (i = 1), etc, using a loop, and (3) use the set-aside value to set last row. Or the other way round if you want to rotate down.

Andy

[Slade316]

Thanks for the help.. I got it.. :)

[andywestken]

Cool!

Actually, rotating a 2d array with std::rotate is something I'd never tried to do...

My first naive attempt was:

std::rotate(arr[0], arr[0] + 1, arr[0] + col_count);

where my int array is row_count = 3 by col_count = 4. As C++ uses row-major storage for arrays, I knew arr[0] would be the first row...

Unfortunately the first row is also an array (a 1D array), and so decays to a pointer (an int* here) when passed to std::rotate(). So what happened is that I rotated most of the elements in the first row (row_count < col_count for my test.)

 11 12 13 14
 21 22 23 24
 31 32 33 34

rotate rows!

 12 13 11 14
 21 22 23 24
 31 32 33 34

But I did get it to work! :-)

 11 12 13 14
 21 22 23 24
 31 32 33 34

rotate rows!

 21 22 23 24
 31 32 33 34
 11 12 13 14

by using the address-of operator when I passed the (address of the) first row of the 2d array to std::rotate (thereby avoiding the array decay.)

std::rotate(&arr[0], &arr[0] + 1, &arr[0] + row_count); // no decay

Hmmm... the mistake was prob. due to the habit of passing 1d arrays by name e.g. func(arr); to function when you really mean func(&arr[0]);, thanks to array decay.

Andy

[JLBorges]

The type of a row of int arr[3][4] is the array int[4].
Arrays are not Copyable or Moveable; std::rotate() can't be used to rotate the rows directly.
http://coliru.stacked-crooked.com/a/ca3e55e1f687ffb0

We can use std::rotate() if we consider the array as a single sequence of integers. (int is Copyable and Moveable)

#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
    const int NROWS = 3 ;
    const int NCOLS = 4 ;
    int arr[NROWS][NCOLS] = { { 11, 12, 13, 14 }, { 21, 22, 23, 24 }, { 31, 32, 33, 34 } };

    std::rotate( std::begin( arr[0] ), std::begin( arr[0] ) + NCOLS, std::end( arr[NROWS-1] ) );

    for( const auto& row : arr )
    {
        for( int v : row ) std::cout << v << ' ' ;
        std::cout << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/65ee5d00717b1a9b

[andywestken]

std::rotate() can't be used to rotate the rows directly.

Unless, it seems, it's the version provided with Visual Studio... (The output I posted before was from unexpectedly running code.)

I have to admit I was a bit doubtful that it would work, and a bit surprised when it did. Which is why I posted about it here.

Edit:

I'm curious how it works (though haven't delved into it yet) when Microsoft's compiler chokes on:

    int a[2] = {0, 0};
    int b[2] = {1, 2};
    a = b; // error C2106: '=' : left operand must be l-value 

as expected.

And I've just checked that Visual Studio 2013's compiler is in agreement (the original result came from '2010.)

Andy

#include <iostream>
#include <algorithm>

template<int row_count, int col_count>
void dump(int (&arr)[row_count][col_count]) {
    std::cout << "[dump]\n\n";
    for(int r = 0; row_count > r; ++r) {
        for(int c = 0; col_count > c; ++c) {
            std::cout << " " << arr[r][c];
        }
        std::cout << "\n";
    }
    std::cout << "\n";
}

template<int row_count, int col_count>
void dump_flat(int (&arr)[row_count][col_count]) {
    std::cout << "[dump flat]\n\n";
    int elem_count = row_count * col_count;
    int* p = &arr[0][0];
    for(int e = 0; e < elem_count; ++e) {
        std::cout << " " << p[e];
    }
    std::cout << "\n\n";
}

int main() {
    int arr[][4] = { {11, 12, 13, 14}
                   , {21, 22, 23, 24}
                   , {31, 32, 33, 34} };

    const int elem_count = sizeof(arr)/sizeof(arr[0][0]);
    const int row_count  = sizeof(arr)/sizeof(arr[0]);
    const int col_count  = elem_count / row_count;

    std::cout << "elems = " << elem_count << "\n";
    std::cout << "rows  = " << row_count  << "\n";
    std::cout << "cols  = " << col_count  << "\n";
    std::cout << "\n";

    dump(arr);
    dump_flat(arr);

    std::cout << "rotate rows! (take 1 - failed!)\n";
    // arr[r] is a pointer to the first row, which is an
    // array of 4 ints here, which decays to an int* when passed
    // to std::rotate(), so it's the elements of the first row
    // that end up rotating rather than the rows.
    std::rotate(arr[0], arr[0] + 1, arr[0] + row_count);
    std::cout << "\n";

    dump(arr);
    dump_flat(arr);

    std::cout << "rotate back\n";
    std::rotate(arr[0], arr[0] + (row_count - 1), arr[0] + row_count);
    std::cout << "\n";

    dump(arr);
    dump_flat(arr);

    std::cout << "rotate cols!\n";
    for(int r = 0; r < row_count; ++r) {
        std::rotate(arr[r], arr[r] + 1, arr[r] + col_count);
    }
    std::cout << "\n";

    dump(arr);
    dump_flat(arr);

    std::cout << "rotate back!\n";
    for(int r = 0; r < row_count; ++r) {
        std::rotate(arr[r], arr[r] + (col_count - 1), arr[r] + col_count);
    }
    std::cout << "\n";

    dump(arr);
    dump_flat(arr);

    std::cout << "rotate rows! (take 2 - works!)\n";
    std::rotate(&arr[0], &arr[0] + 1, &arr[0] + row_count);
    std::cout << "\n";

    dump(arr);
    dump_flat(arr);

    return 0;
}

elems = 12
rows  = 3
cols  = 4

[dump]

 11 12 13 14
 21 22 23 24
 31 32 33 34

[dump flat]

 11 12 13 14 21 22 23 24 31 32 33 34

rotate rows! (take 1 - failed!)

[dump]

 12 13 11 14
 21 22 23 24
 31 32 33 34

[dump flat]

 12 13 11 14 21 22 23 24 31 32 33 34

rotate back

[dump]

 11 12 13 14
 21 22 23 24
 31 32 33 34

[dump flat]

 11 12 13 14 21 22 23 24 31 32 33 34

rotate cols!

[dump]

 12 13 14 11
 22 23 24 21
 32 33 34 31

[dump flat]

 12 13 14 11 22 23 24 21 32 33 34 31

rotate back!

[dump]

 11 12 13 14
 21 22 23 24
 31 32 33 34

[dump flat]

 11 12 13 14 21 22 23 24 31 32 33 34

rotate rows! (take 2 - works!)

[dump]

 21 22 23 24
 31 32 33 34
 11 12 13 14

[dump flat]

 21 22 23 24 31 32 33 34 11 12 13 14

[andywestken]

I've now looked into the mystery of why the Microsoft (Dinkum?) version of std::rotate is perfectly happy with 2D arrays.

It seems the solution is an overload of the swap() funtion that understands how to deal with arrays (from <algorithm>).

template<class _Ty,
	size_t _Size> inline
	void swap(_Ty (&_Left)[_Size], _Ty (&_Right)[_Size])
	{	// exchange arrays stored at _Left and _Right
	if (&_Left != &_Right)
		_Swap_ranges(&_Left[0], &_Left[0] + _Size, &_Right[0]);
	}

which allows the compiler to deduce that it needs to expand the templates to the following call sequence, ending up with copying of int values.

temp_test.exe!std::_Move<int &>(int & _Arg)
temp_test.exe!std::swap<int>(int & _Left, int & _Right)
temp_test.exe!std::iter_swap<int *,int *>(int * _Left, int * _Right)
temp_test.exe!std::_Swap_ranges<int *,int *>(int * _First1, int * _Last1, int * _Dest)
temp_test.exe!std::swap<int,4>(int [4]& _Left, int [4]& _Right)
temp_test.exe!std::iter_swap<int (*)[4],int (*)[4]>(int [4]* _Left, int [4]* _Right)
temp_test.exe!std::_Rotate<int (*)[4],int,int [4]>(int [4]* _First, int [4]* _Mid,
    int [4]* _Last, int *, int *)
temp_test.exe!std::_Rotate<int (*)[4]>(int [4]* _First, int [4]* _Mid, int [4]* _Last,
    std::random_access_iterator_tag)
temp_test.exe!std::rotate<int (*)[4]>(int [4]* _First, int [4]* _Mid, int [4]* _Last)
temp_test.exe!main()

I'm now wondering if this is non-conformant. Does the C++ Standard mandate that std::rotate is not allowed to handle arrays?

Andy

PS When I changed the array to a 2d array of char buffers (aka a 3d array of chars) the call sequence ended up as:

temp_test.exe!std::_Move<char &>(char & _Arg)
temp_test.exe!std::swap<char>(char & _Left, char & _Right)
temp_test.exe!std::iter_swap<char *,char *>(char * _Left, char * _Right)
temp_test.exe!std::_Swap_ranges<char *,char *>(char * _First1, char * _Last1, char * _Dest)
temp_test.exe!std::swap<char,8>(char [8]& _Left, char [8]& _Right)
temp_test.exe!std::iter_swap<char (*)[8],char (*)[8]>(char [8]* _Left, char [8]* _Right)
temp_test.exe!std::_Swap_ranges<char (*)[8],char (*)[8]>(char [8]* _First1,
    char [8]* _Last1, char [8]* _Dest)
temp_test.exe!std::swap<char [8],4>(char [4][8]& _Left, char [4][8]& _Right)
temp_test.exe!std::iter_swap<char (*)[4][8],char (*)[4][8]>(char [4][8]* _Left,
    char [4][8]* _Right)
temp_test.exe!std::_Rotate<char (*)[4][8],int,char [4][8]>(char [4][8]* _First,
     char [4][8]* _Mid, char [4][8]* _Last, int *, int *)
temp_test.exe!std::_Rotate<char (*)[4][8]>(char [4][8]* _First, char [4][8]* _Mid,
    char [4][8]* _Last, std::random_access_iterator_tag)
temp_test.exe!std::rotate<char (*)[4][8]>(char [4][8]* _First, char [4][8]* _Mid,
    char [4][8]* _Last)
temp_test.exe!main()

ending up with swapping of chars.

[Duthomhas]

The swap()/iter_swap() algorithms should be used in rotate(). So the following should properly compile just fine.

#include <algorithm>
#include <iostream>

int main()
{
    const int NROWS = 3 ;
    const int NCOLS = 4 ;
    int arr[NROWS][NCOLS] = { { 11, 12, 13, 14 }, { 21, 22, 23, 24 }, { 31, 32, 33, 34 } };

    std::rotate( arr[0], arr[1], arr[NROWS] );

    for( const auto& row : arr )
    {
        for( int v : row ) std::cout << v << ' ' ;
        std::cout << '\n' ;
    }
}

Unless there's something I don't understand. Or hysterical stuff gumming up the works.

[andywestken]

Cool, it does.

I made the mistake of using:

std::rotate( arr[0], arr[0] + 1, arr[0] + NROWS );

which compiles, but just rotates the columns of the first row, i.e.

12 13 11 14
21 22 23 24
31 32 33 34

and then attempting to "fix" it by using:

std::rotate( &arr[0], &arr[0] + 1, &arr[0] + NROWS );

which works with MSVC but not GCC:

... error: array must be initialized with a brace-enclosed initializer
... error: invalid array assignment

(or Clang, according to JLBorges's post.)

Andy

PS Call stacks for:

std::rotate( arr[0], arr[1], arr[NROWS] );

end up as

MSVC

std::_Move<int &>(int & _Arg)
std::swap<int>(int & _Left, int & _Right)
std::iter_swap<int *,int *>(int * _Left, int * _Right)
std::_Rotate<int *,int,int>(int * _First, int * _Mid, int * _Last,
    int * __formal, int * __formal)
std::_Rotate<int *>(int * _First, int * _Mid, int * _Last,
    std::random_access_iterator_tag __formal)
std::rotate<int *>(int * _First, int * _Mid, int * _Last)
main()

GCC

std::move<int&>
std::swap<int>
std::iter_swap<int*, int*>
std::__rotate<int*>
std::rotate<int*>
main()