Two-Dimensional Dynamic Arrays

[Peter Olcott]

I need to know how to get the solution mentioned below to work. The
solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:

http://groups.google.com/group/comp....c43260a5310?hl

Another way is to create a one dimensional array and handle the
indexing yourself (index = row * row_size + col). This is readily
implemented in template classes that can create dynamically allocated
multi-dimensional arrays of any element type and number of
dimensions.

What would be the syntax for created a template that allowed a
one dimensional dynamic array, to be addressed using the conventional
syntax for accessing a two dimensional array? I am thinking that this
must be some sort of operator[] overloading.

Thanks,
Peter Olcott

[Gianni Mariani]

Peter Olcott wrote:

I need to know how to get the solution mentioned below to work. The
solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:

http://groups.google.com/group/comp....c43260a5310?hl

Another way is to create a one dimensional array and handle the
indexing yourself (index = row * row_size + col). This is readily
implemented in template classes that can create dynamically allocated
multi-dimensional arrays of any element type and number of
dimensions.

What would be the syntax for created a template that allowed a
one dimensional dynamic array, to be addressed using the conventional
syntax for accessing a two dimensional array? I am thinking that this
must be some sort of operator[] overloading.

http://groups.google.com/group/comp....4f1d9bd?hl=en&

I knew I answered this once before - I think there is an FAQ as well..

Here is the example code from that posting.

#include <vector>

template <typename w_elem_type>
class matrix
{
public:
typedef int t_Size;

t_Size m_columns;
t_Size m_rows;

std::vector<w_e lem_type> m_data;

matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
: m_columns( i_columns ),
m_rows( i_rows ),
m_data( i_columns * i_rows )
{
}

w_elem_type * operator[]( t_Size i_index )
{
return & ( m_data[ i_index * m_rows ] );
}

template <typename w_Type, int w_columns, int w_rows>
matrix( const w_Type (&i_array)[w_columns][w_rows] )
: m_columns( w_columns ),
m_rows( w_rows ),
m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
{
}

};

#include <iostream>

double array[3][4] = {
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.5 },

};

int main()
{
matrix<float> mat1( 3, 4 );
matrix<float> mat2;
matrix<float> mat3( array );

mat2 = mat3;

std::cout << mat2[2][3] << "\n";

}

[Peter Olcott]

That looks like an excellent solution. I need absolutely top performance.
You mentioned :

some extensive matrix libraries you could use
and ones that are very efficient if the dimensions
are known.

Could you provide me a link or other reference to these?
Thanks again for your top notch assistance.

"Gianni Mariani" <gi*******@mari ani.ws> wrote in message
news:q4******** *************** *******@speakea sy.net...

Peter Olcott wrote:

I need to know how to get the solution mentioned below to work. The
solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:

http://groups.google.com/group/comp....c43260a5310?hl

Another way is to create a one dimensional array and handle the
indexing yourself (index = row * row_size + col). This is readily
implemente d in template classes that can create dynamically allocated
multi-dimensional arrays of any element type and number of
dimensions .

What would be the syntax for created a template that allowed a
one dimensional dynamic array, to be addressed using the conventional
syntax for accessing a two dimensional array? I am thinking that this
must be some sort of operator[] overloading.

http://groups.google.com/group/comp....4f1d9bd?hl=en&

I knew I answered this once before - I think there is an FAQ as well..

Here is the example code from that posting.

#include <vector>

template <typename w_elem_type>
class matrix
{
public:
typedef int t_Size;

t_Size m_columns;
t_Size m_rows;

std::vector<w_e lem_type> m_data;

matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
: m_columns( i_columns ),
m_rows( i_rows ),
m_data( i_columns * i_rows )
{
}

w_elem_type * operator[]( t_Size i_index )
{
return & ( m_data[ i_index * m_rows ] );
}

template <typename w_Type, int w_columns, int w_rows>
matrix( const w_Type (&i_array)[w_columns][w_rows] )
: m_columns( w_columns ),
m_rows( w_rows ),
m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
{
}

};

#include <iostream>

double array[3][4] = {
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.5 },

};

int main()
{
matrix<float> mat1( 3, 4 );
matrix<float> mat2;
matrix<float> mat3( array );

mat2 = mat3;

std::cout << mat2[2][3] << "\n";

}

[Peter Olcott]

Oh yeah, I only need very fast addressing of the elements
of the Matrix. I will likely be moving up or down matrix rows
about five times as often as moving across matrix columns.

"Gianni Mariani" <gi*******@mari ani.ws> wrote in message
news:q4******** *************** *******@speakea sy.net...

Peter Olcott wrote:

I need to know how to get the solution mentioned below to work. The
solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:

http://groups.google.com/group/comp....c43260a5310?hl

Another way is to create a one dimensional array and handle the
indexing yourself (index = row * row_size + col). This is readily
implemente d in template classes that can create dynamically allocated
multi-dimensional arrays of any element type and number of
dimensions .

What would be the syntax for created a template that allowed a
one dimensional dynamic array, to be addressed using the conventional
syntax for accessing a two dimensional array? I am thinking that this
must be some sort of operator[] overloading.

http://groups.google.com/group/comp....4f1d9bd?hl=en&

I knew I answered this once before - I think there is an FAQ as well..

Here is the example code from that posting.

#include <vector>

template <typename w_elem_type>
class matrix
{
public:
typedef int t_Size;

t_Size m_columns;
t_Size m_rows;

std::vector<w_e lem_type> m_data;

matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
: m_columns( i_columns ),
m_rows( i_rows ),
m_data( i_columns * i_rows )
{
}

w_elem_type * operator[]( t_Size i_index )
{
return & ( m_data[ i_index * m_rows ] );
}

template <typename w_Type, int w_columns, int w_rows>
matrix( const w_Type (&i_array)[w_columns][w_rows] )
: m_columns( w_columns ),
m_rows( w_rows ),
m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
{
}

};

#include <iostream>

double array[3][4] = {
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.5 },

};

int main()
{
matrix<float> mat1( 3, 4 );
matrix<float> mat2;
matrix<float> mat3( array );

mat2 = mat3;

std::cout << mat2[2][3] << "\n";

}

[Gianni Mariani]

Peter Olcott wrote:

That looks like an excellent solution. I need absolutely top performance.
You mentioned :

some extensive matrix libraries you could use
and ones that are very efficient if the dimensions
are known.

Could you provide me a link or other reference to these?

Google "C++ matrix" gives a plethora of answers. Quite a while ago I
looked at some of these but I didn't get involved with the project so I
can't give you any real feedback.

What I mean by "dimensions are known" is "known at compile time". If
they are known at compile time, you don't need to perform dynamic memory
allocation and you can enable some usual compiler optimizations (like
loop unrolling).

For somthing like a 3D graphics library, this would be ideal since it
predominantly uses a 4x4 matrices (Homogeneous Coordinates) and 1x4
vectors and so much of the code can be unrolled and the compiler has a
much better chance of optimizing it.

See below, the matrix example now with the row and column sizes known.

template <typename w_elem_type, unsigned w_rows, unsigned w_columns>
class matrix
{
public:

typedef w_elem_type value_type;
static const unsigned m_columns = w_columns;
static const unsigned m_rows = w_rows;

value_type m_data[ m_rows ][ m_columns ];

typedef w_elem_type row_value_type[ m_columns ];

matrix()
: m_data()
{
}

row_value_type & operator[]( unsigned i_index )
{
return m_data[ i_index ];
}

template <typename w_elem_intype>
matrix(
const w_elem_intype (&i_array)[m_rows][m_columns]
)
{
copy_matrix( i_array );
}

template <typename w_elem_intype>
matrix(
const matrix<w_elem_i ntype, m_rows, m_columns > & i_array
)
{
copy_matrix( i_array.m_data );
}

template <typename w_elem_intype>
matrix & operator=(
const w_elem_intype (&i_array)[m_rows][m_columns]
)
{
copy_matrix( i_array );
return * this;
}

template <typename w_elem_intype>
matrix & operator=(
const matrix<w_elem_i ntype, m_rows, m_columns > & i_array
)
{
copy_matrix( i_array.m_data );
return * this;
}

private:

template <typename w_elem_intype>
void copy_matrix( w_elem_intype (&i_array)[m_rows][m_columns] )
{
w_elem_type * l_elem = & m_data[ 0 ][ 0 ];
w_elem_intype * l_from = & i_array[ 0 ][ 0 ];

for ( unsigned l_i = 0; l_i < m_columns * m_rows; ++ l_i )
{
l_elem[ l_i ] = l_from[ l_i ];
}
}

};

#include <iostream>

double array[3][4] = {
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.5 },
};

int main()
{
matrix<float, 3, 4> mat1;
matrix<float, 3, 4> mat2;
matrix<float, 3, 4> mat3( array );

mat2 = mat3;

matrix<double, 3, 4> mat2d = mat2;
mat2d = mat3;

std::cout << mat2[2][3] << "\n";
}

[Peter Olcott]

I tested the performance of the code below and it took 150 ms,
as opposed to 4.5 ms for a conventional two dimensional array.
I am going to work on making a faster version tonight. I am
guessing that it might have to have a kludge interface:
void SetData(int ROW, int COL, UINT Data);
UINT GetData(int ROW, int COL);

"Gianni Mariani" <gi*******@mari ani.ws> wrote in message
news:q4******** *************** *******@speakea sy.net...

Peter Olcott wrote:

I need to know how to get the solution mentioned below to work. The
solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:

http://groups.google.com/group/comp....c43260a5310?hl

Another way is to create a one dimensional array and handle the
indexing yourself (index = row * row_size + col). This is readily
implemente d in template classes that can create dynamically allocated
multi-dimensional arrays of any element type and number of
dimensions .

What would be the syntax for created a template that allowed a
one dimensional dynamic array, to be addressed using the conventional
syntax for accessing a two dimensional array? I am thinking that this
must be some sort of operator[] overloading.

http://groups.google.com/group/comp....4f1d9bd?hl=en&

I knew I answered this once before - I think there is an FAQ as well..

Here is the example code from that posting.

#include <vector>

template <typename w_elem_type>
class matrix
{
public:
typedef int t_Size;

t_Size m_columns;
t_Size m_rows;

std::vector<w_e lem_type> m_data;

matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
: m_columns( i_columns ),
m_rows( i_rows ),
m_data( i_columns * i_rows )
{
}

w_elem_type * operator[]( t_Size i_index )
{
return & ( m_data[ i_index * m_rows ] );
}

template <typename w_Type, int w_columns, int w_rows>
matrix( const w_Type (&i_array)[w_columns][w_rows] )
: m_columns( w_columns ),
m_rows( w_rows ),
m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
{
}

};

#include <iostream>

double array[3][4] = {
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.5 },

};

int main()
{
matrix<float> mat1( 3, 4 );
matrix<float> mat2;
matrix<float> mat3( array );

mat2 = mat3;

std::cout << mat2[2][3] << "\n";

}

[Peter Olcott]

#define UINT unsigned int
const int Width = 3000;
const int Height = 2000;
UINT Array01[Width][Height];
ArrayType2D Array02;
UINT Array03[Width][Height];
class ArrayType2D {
private:
UINT* Array;
int last_row;
public:
ArrayType2D(){ Array = new UINT [Width * Height]; };
~ArrayType2D(){ delete [] Array; };
UINT operator[](int N){ return Array[N]; };
void SetRow(int ROW) { last_row = ROW * Width; };
UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
UINT GetPixel(int COL){ return Array[last_row + COL]; }
void SetPixel(int COL, UINT DATA){ Array[last_row + COL] = DATA; }
void SetPixel(int ROW, int COL, UINT DATA){ Array[(ROW * Width) + COL] = DATA; }
};

void Test04(int HEIGHT, int WIDTH) {
for (int ROW = 0; ROW < HEIGHT; ROW++) {
Array02.SetRow( ROW);
for (int COL = 0; COL < WIDTH; COL++)
Array03[ROW][COL] = Array02.GetPixe l(COL);
}
}

The above code accesses a dynamic two-dimensional array
about fifteen percent faster than a conventional two-dimensional
array is accessed, if the data is to be accessed in the order
specified, moving through all the columns in a row, and then
moving to the next row. If the data is to accessed in a different
order such as moving through all the rows, and then moving to
the next column, the above code would need to be adapted.
Also one must make sure that the data is stored in the single
dimension array in the order corresponding to this different
access order.

Now if I could only have the following function
UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
work with conventional Array02[ROW][COL] syntax, and find a way
to make it at least as fast as conventional array access (right now it is only
57% as fast), then I would be happier.

"Gianni Mariani" <gi*******@mari ani.ws> wrote in message news:q4******** *************** *******@speakea sy.net...

Peter Olcott wrote:

I need to know how to get the solution mentioned below to work. The
solution is from gbayles Jan 29 2001, 12:50 pm, link is provided below:

http://groups.google.com/group/comp....c43260a5310?hl

Another way is to create a one dimensional array and handle the
indexing yourself (index = row * row_size + col). This is readily
implemente d in template classes that can create dynamically allocated
multi-dimensional arrays of any element type and number of
dimensions .

What would be the syntax for created a template that allowed a
one dimensional dynamic array, to be addressed using the conventional
syntax for accessing a two dimensional array? I am thinking that this
must be some sort of operator[] overloading.

http://groups.google.com/group/comp....4f1d9bd?hl=en&

I knew I answered this once before - I think there is an FAQ as well..

Here is the example code from that posting.

#include <vector>

template <typename w_elem_type>
class matrix
{
public:
typedef int t_Size;

t_Size m_columns;
t_Size m_rows;

std::vector<w_e lem_type> m_data;

matrix( t_Size i_columns = 0, t_Size i_rows = 0 )
: m_columns( i_columns ),
m_rows( i_rows ),
m_data( i_columns * i_rows )
{
}

w_elem_type * operator[]( t_Size i_index )
{
return & ( m_data[ i_index * m_rows ] );
}

template <typename w_Type, int w_columns, int w_rows>
matrix( const w_Type (&i_array)[w_columns][w_rows] )
: m_columns( w_columns ),
m_rows( w_rows ),
m_data( & (i_array[0][0]), & (i_array[w_columns-1][w_rows]) )
{
}

};

#include <iostream>

double array[3][4] = {
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.4 },
{ 1.0, 2.0, 3.3, 4.5 },

};

int main()
{
matrix<float> mat1( 3, 4 );
matrix<float> mat2;
matrix<float> mat3( array );

mat2 = mat3;

std::cout << mat2[2][3] << "\n";

}

[Gianni Mariani]

Peter Olcott wrote:

#define UINT unsigned int Use a typedef here - avoid macros where possible
typedef unsigned int UINT; const int Width = 3000;
const int Height = 2000; these could be template parameters.
UINT Array01[Width][Height];
ArrayType2D Array02;
UINT Array03[Width][Height];
class ArrayType2D {
private:
UINT* Array;
int last_row;
public:
// oops - using the default copy constructor - will cause
// delete [] Array to be called multiple times (and leak)
// if the array is ever copied. (same goes for assignment
// operator.)
ArrayType2D(){ Array = new UINT [Width * Height]; };
~ArrayType2D(){ delete [] Array; };
UINT operator[](int N){ return Array[N]; };
void SetRow(int ROW) { last_row = ROW * Width; };
UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
UINT GetPixel(int COL){ return Array[last_row + COL]; }
void SetPixel(int COL, UINT DATA){ Array[last_row + COL] = DATA; }
void SetPixel(int ROW, int COL, UINT DATA){ Array[(ROW * Width) + COL] = DATA; }
};

void Test04(int HEIGHT, int WIDTH) {
for (int ROW = 0; ROW < HEIGHT; ROW++) {
Array02.SetRow( ROW);
for (int COL = 0; COL < WIDTH; COL++)
Array03[ROW][COL] = Array02.GetPixe l(COL);
}
}

The above code accesses a dynamic two-dimensional array
about fifteen percent faster than a conventional two-dimensional
array is accessed, if the data is to be accessed in the order
specified, moving through all the columns in a row, and then
moving to the next row. If the data is to accessed in a different
order such as moving through all the rows, and then moving to
the next column, the above code would need to be adapted.
Also one must make sure that the data is stored in the single
dimension array in the order corresponding to this different
access order.

Now if I could only have the following function
UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
work with conventional Array02[ROW][COL] syntax, and find a way
to make it at least as fast as conventional array access (right now it is only
57% as fast), then I would be happier.

Did you check out the last example I posted ? Since you know the size
of your array at compile time, you can use somthing like that. On a
good optimizing compiler, this one would be just about as fast at copies
as you can get.

Is the Test04 function the only test you want ?

SetRow buys you very little in terms of performance (as implemented).

[roberts.noah]

Gianni Mariani wrote:

w_elem_type * operator[]( t_Size i_index )
{
return & ( m_data[ i_index * m_rows ] );
}

This FAQ entry might be of interest:
http://www.parashift.com/c++-faq-lit...html#faq-13.11

See also 13.10 right above it.

[Peter Olcott]

"Gianni Mariani" <gi*******@mari ani.ws> wrote in message news:Oc******** ************@sp eakeasy.net...

Peter Olcott wrote:

#define UINT unsigned int Use a typedef here - avoid macros where possible
typedef unsigned int UINT;

const int Width = 3000;
const int Height = 2000;

these could be template parameters.

UINT Array01[Width][Height];
ArrayType2D Array02;
UINT Array03[Width][Height];
class ArrayType2D {
private:
UINT* Array;
int last_row;
public:

// oops - using the default copy constructor - will cause
// delete [] Array to be called multiple times (and leak)
// if the array is ever copied. (same goes for assignment
// operator.)

ArrayType2D(){ Array = new UINT [Width * Height]; };
~ArrayType2D(){ delete [] Array; };
UINT operator[](int N){ return Array[N]; };
void SetRow(int ROW) { last_row = ROW * Width; };
UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
UINT GetPixel(int COL){ return Array[last_row + COL]; }
void SetPixel(int COL, UINT DATA){ Array[last_row + COL] = DATA; }
void SetPixel(int ROW, int COL, UINT DATA){ Array[(ROW * Width) + COL] = DATA; }
};

void Test04(int HEIGHT, int WIDTH) {
for (int ROW = 0; ROW < HEIGHT; ROW++) {
Array02.SetRow( ROW);
for (int COL = 0; COL < WIDTH; COL++)
Array03[ROW][COL] = Array02.GetPixe l(COL);
}
}

The above code accesses a dynamic two-dimensional array
about fifteen percent faster than a conventional two-dimensional
array is accessed, if the data is to be accessed in the order
specified, moving through all the columns in a row, and then
moving to the next row. If the data is to accessed in a different
order such as moving through all the rows, and then moving to
the next column, the above code would need to be adapted.
Also one must make sure that the data is stored in the single
dimension array in the order corresponding to this different
access order.

Now if I could only have the following function
UINT GetPixel(int ROW, int COL){ return Array[(ROW * Width) + COL]; }
work with conventional Array02[ROW][COL] syntax, and find a way
to make it at least as fast as conventional array access (right now it is only
57% as fast), then I would be happier.

Did you check out the last example I posted ? Since you know the size of your array at compile time, you can use somthing like
that. On a

I know it at run time, not compile time. I will take your other
suggestion (above) and repost an updated copy. The current
version seems to work just as fast as the build-in matrix, and
only lacks conventional double operator[] syntax~~~~>Data[row][col]
the next poster posted material that I will study on this. Thanks for all
your help.

good optimizing compiler, this one would be just about as fast at copies as you can get.

Is the Test04 function the only test you want ?

SetRow buys you very little in terms of performance (as implemented).