Two-Dimensional Dynamic Arrays

P

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.lang.c++/msg/db577c43260a5310?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
 
G

Gianni Mariani

Peter said:
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.lang.c++/msg/db577c43260a5310?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.lang.c/msg/909f01d9b4f1d9bd?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_elem_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";

}
 
P

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 said:
Peter said:
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.lang.c++/msg/db577c43260a5310?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.lang.c/msg/909f01d9b4f1d9bd?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_elem_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";

}
 
P

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 said:
Peter said:
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.lang.c++/msg/db577c43260a5310?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.lang.c/msg/909f01d9b4f1d9bd?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_elem_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";

}
 
G

Gianni Mariani

Peter said:
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_intype, 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_intype, 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";
}
 
P

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 said:
Peter said:
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.lang.c++/msg/db577c43260a5310?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.lang.c/msg/909f01d9b4f1d9bd?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_elem_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";

}
 
P

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.GetPixel(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 said:
Peter said:
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.lang.c++/msg/db577c43260a5310?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.lang.c/msg/909f01d9b4f1d9bd?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_elem_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";

}
 
G

Gianni Mariani

Peter said:
#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.GetPixel(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).
 
P

Peter Olcott

Gianni Mariani said:
Peter said:
#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.GetPixel(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.
 
P

Peter Olcott

Gianni Mariani said:
// 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.)

//
// Array2D.h 2005-11-26 9:32 AM
//
#define UINT unsigned int
//
class ArrayType2D {
private:
int Size;
int Width;
int Height;
UINT* Array;
bool Allocated;
void Copy(ArrayType2D& Array2);
public:
ArrayType2D();
ArrayType2D(ArrayType2D& Array2) { Copy(Array2); };
~ArrayType2D() { if (Allocated) delete [] Array; };
UINT operator[](int N) { return Array[N]; };
ArrayType2D& operator=(ArrayType2D& Array2) { Copy(Array2); return *this; };
UINT* operator&() { return Array; };
UINT Get(int ROW, int COL) { return Array[ROW * Width + COL]; };
void Set(int ROW, int COL, UINT DATA) { Array[ROW * Width + COL] = DATA; }
const int size() { return Size; };
const int width() { return Width; };
const int height() { return Height; };
void Allocate(int Height, int Width);
};

void ArrayType2D::Copy(ArrayType2D& Array2) {
if (this->Allocated)
delete [] Array;
this->Width = Array2.Width;
this->Height = Array2.Height;
this->Size = Array2.Size;;
this->Array = new UINT [this->Size];
}

ArrayType2D::ArrayType2D() {
Size = 0;
Width = 0;
Height = 0;
Array = NULL;
Allocated = false;
}

inline void ArrayType2D::Allocate(int Height, int Width) {
if (Allocated)
delete [] Array;
this->Width = Width;
this->Height = Height;
this->Size = Width * Height;
this->Array = new UINT [Size];
}
 
P

Peter Olcott

This was very helpful. Not only did it provide an excellent solution,
it also analyzed all of my alternatives. If you want very high speed
and ease of use, on creating a multi-dimensional array from dynamic
memory, operator() is the way to go. I will post my latest update
shortly.

Gianni said:
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-lite/operator-overloading.html#faq-13.11

See also 13.10 right above it.
 
P

Peter Olcott

I goofed your code works perfectly.
I could not get the last function to compile on MSVC++ 6.0,
but after I stripped this function out and properly benchmarked
the speed it was superb. It exactly matched a statically defined
matrix. Also I got to use the double operator[], that I wanted.
Because of these reasons, I must say that your code is the best
possible code according to any possible criterion measure of
a method to create a dynamically allocated two-dimensional array.

matrix.cpp
matrix.cpp(27) : error C2265: '<Unknown>' : reference to a zero-sized array is illegal
matrix.cpp(34) : see reference to class template instantiation 'matrix<w_elem_type>' being compiled
matrix.cpp(27) : error C2265: '<Unknown>' : reference to a zero-sized array is illegal
matrix.cpp(47) : see reference to class template instantiation 'matrix<float>' being compiled
matrix.cpp(27) : error C2087: '<Unknown>' : missing subscript
matrix.cpp(47) : see reference to class template instantiation 'matrix<float>' being compiled
matrix.cpp(49) : error C2664: '__thiscall matrix<float>::matrix<float>(int,int)' : cannot convert parameter 1 from 'double [3][4]'
to 'int'
This conversion requires a reinterpret_cast, a C-style cast or function-style cast
matrix.cpp(55) : warning C4508: 'main' : function should return a value; 'void' return type assumed


#include <vector> // Line (1) of matrix.cpp identical copy of your code

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

t_Size m_columns;
t_Size m_rows;

std::vector<w_elem_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";

}
 
P

Peter Olcott

Gianni Mariani said:
MSCV6 is ancient. Do you "have to" use it ?

Currently yes. The performance of your code is superb and
allows me to accomplish my execution well within my real-time
constraints. I am posting my adaptations to your code below.
All that I did is add a little more functionality.
but after I stripped this function out and properly benchmarked

It seems like it's picking the wrong vector constructor. I think there is another constructor vector( pointer, size ) that you
could use.
the speed it was superb. It exactly matched a statically defined
matrix. Also I got to use the double operator[], that I wanted.
Because of these reasons, I must say that your code is the best
possible code according to any possible criterion measure of
a method to create a dynamically allocated two-dimensional array.

Good luck !

//
// Matrix.h 2005-11-27 11:45 AM Dynamic Two-Dimensional Array Template
//
// comp.lang.c++ message from Gianni Mariani Nov 24, 2005 at 9:21 pm
// http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a
// Adapted by Peter Olcott resize() and operator&() added.
//
#include <vector>

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

t_Size m_rows;
t_Size m_columns;

std::vector<w_elem_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&(){ return &m_data[0]; };

void resize( t_Size i_columns, t_Size i_rows );

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

};

template <typename w_elem_type>
void matrix<w_elem_type>::resize( t_Size i_columns, t_Size i_rows ) {
m_rows = i_rows;
m_columns = i_columns;
m_data.resize(i_columns * i_rows );
}
 
G

Gianni Mariani

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-lite/operator-overloading.html#faq-13.11

See also 13.10 right above it.

That FAQ is a classic case of premature optimization.

It's quite easy to turn [A] into (A,B) with no loss of performance
(on a good optimizing compiler). Also, the compiler probably has built
in optimizations that know how to deal with stride and may get confused
when dealing with (A,B) like functor calls.

Give me an example where [A] is slower than (A,B) (using an decent
optimizer) and we'll see if we can fix it. Otherwise I declare the FAQ
hogwash.
 
G

Gianni Mariani

Peter said:
I goofed your code works perfectly.
I could not get the last function to compile on MSVC++ 6.0,

MSCV6 is ancient. Do you "have to" use it ?
but after I stripped this function out and properly benchmarked

It seems like it's picking the wrong vector constructor. I think there
is another constructor vector( pointer, size ) that you could use.
the speed it was superb. It exactly matched a statically defined
matrix. Also I got to use the double operator[], that I wanted.
Because of these reasons, I must say that your code is the best
possible code according to any possible criterion measure of
a method to create a dynamically allocated two-dimensional array.

Good luck !
 
R

roberts.noah

Gianni said:
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-lite/operator-overloading.html#faq-13.11

See also 13.10 right above it.

That FAQ is a classic case of premature optimization.

It's quite easy to turn [A] into (A,B) with no loss of performance
(on a good optimizing compiler).


Oh really??!! Tell me then, how exactly is the compiler going to hide
the internal representiation of the matrix when you have exposed it
with the first [] operator??!! How is the compiler going to decide to
use column major instead of row major, or visa-versa, when it is the
better way to represent the matrix for the particular needs, when you
have created a dependency on row major by using the [] operator to
return rows??!!

Hint: the compiler cannot do anything to change your algorithms to a
more optomized nature for the problem you want to solve, especially
when you have created such dependencies. In fact, with your function
there not even the programmer can. Since this is perfectly laid out in
the FAQ I have to assume you never read it and/or totally missed the
point.

Also, the compiler probably has built
in optimizations that know how to deal with stride and may get confused
when dealing with (A,B) like functor calls.

Hogwash. Assuming that op[][] and (x,y) would operate in the same
manner (meaning () just returned [][]) then at worst you have an inline
function call to [A+B] on your internal array. There is 0 performance
hit there (unless maybe you are in debug mode on some compilers) and
there is absolutely no difference to the compiler whatsoever.

As the FAQ says, there is never a time when () is worst than [][].

What exactly do you think the diff is between [] and () that would make
you think the compiler would get more confused over one vs. the other?
Give me an example where [A] is slower than (A,B) (using an decent
optimizer) and we'll see if we can fix it.


Go back and read the FAQ - it gives just such an example. Also keep
the definition of the word, "encapsulation," in mind as you read it and
try to realize what you have done by tossing out &vector[x] to
artificially create [x][y]. I mean, why even offer the protection of
the class boundary if you are going to bypass it like that??!!

Hint: not only have you created a dependency on the internals of your
own class in a rather icky way you have created a dependency on how the
std::vector class is implemented. It is highly unlikely to be
implemented in any other way but the standard does not guarantee that
behavior. Point is that dependencies now exist that never should exist
in a well structured program; these are the things that create code rot
right off the bat.

Otherwise I declare the FAQ

That is of course your own perogative. A smarter person, however,
might decide to learn from it. I really doubt you actually read that
FAQ and comprehended what it was saying because the things you are
saying don't leave much doubt.
 
K

Kai-Uwe Bux

Gianni said:
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-lite/operator-overloading.html#faq-13.11

See also 13.10 right above it.

That FAQ is a classic case of premature optimization.

It's quite easy to turn [A] into (A,B) with no loss of performance
(on a good optimizing compiler).


Oh really??!! Tell me then, how exactly is the compiler going to hide
the internal representiation of the matrix when you have exposed it
with the first [] operator??!! How is the compiler going to decide to
use column major instead of row major, or visa-versa, when it is the
better way to represent the matrix for the particular needs, when you
have created a dependency on row major by using the [] operator to
return rows??!!


The FAQ makes the claim that the [][] interface is less flexible. This is
*not* true in general. The FAQ somehow seems to assume that the only way of
realizing the [][] interface is that operator[] returns an array or
something similar that exposes the internal representation of the matrix
class. However, you do not need to expose the internal representation at
all. The most easy way of doing this, would probably be a proxy:

struct matrix {

typedef unsigned long size_type;

int& operator() ( size_type row, size_type col ) {
return ( whatever(row,col) );
}

struct row_proxy {

matrix & the_matrix;
size_type the_row;

row_proxy ( matrix & A, size_type r )
: the_matrix ( A )
, the_row ( r )
{}

int& operator[] ( size_type col ) {
return( the_matrix.whatever(the_row,col) );
}

};

row_proxy operator[] ( size_type row ) {
return( row_proxy( *this, row ) );
}

// some internal representation to implement whatever goes here:
// ...

}; // matrix


Note that in expressions like A[row][col], the proxy should be optimized
away be a moderately smart optimizing compiler.


Best

Kai-Uwe Bux
 
R

roberts.noah

Kai-Uwe Bux said:
Gianni said:
(e-mail address removed) wrote:
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-lite/operator-overloading.html#faq-13.11

See also 13.10 right above it.


That FAQ is a classic case of premature optimization.

It's quite easy to turn [A] into (A,B) with no loss of performance
(on a good optimizing compiler).


Oh really??!! Tell me then, how exactly is the compiler going to hide
the internal representiation of the matrix when you have exposed it
with the first [] operator??!! How is the compiler going to decide to
use column major instead of row major, or visa-versa, when it is the
better way to represent the matrix for the particular needs, when you
have created a dependency on row major by using the [] operator to
return rows??!!


The FAQ makes the claim that the [][] interface is less flexible. This is
*not* true in general. The FAQ somehow seems to assume that the only way of
realizing the [][] interface is that operator[] returns an array or
something similar that exposes the internal representation of the matrix
class.


As is done in the above code.

However, you do not need to expose the internal representation at
all. The most easy way of doing this, would probably be a proxy:

struct matrix {

typedef unsigned long size_type;

int& operator() ( size_type row, size_type col ) {
return ( whatever(row,col) );
}

struct row_proxy {

matrix & the_matrix;
size_type the_row;

row_proxy ( matrix & A, size_type r )
: the_matrix ( A )
, the_row ( r )
{}

int& operator[] ( size_type col ) {
return( the_matrix.whatever(the_row,col) );
}

};

row_proxy operator[] ( size_type row ) {
return( row_proxy( *this, row ) );
}

// some internal representation to implement whatever goes here:
// ...

}; // matrix

That is an aweful lot of work just to get a particular syntax that just
ends up using the equivilant of (x,y).
Note that in expressions like A[row][col], the proxy should be optimized
away be a moderately smart optimizing compiler.

Are you sure? Have you tested this theory of yours with your own
compiler? I think you are expecting rather a lot from your compiler if
you expect that it will actually optimize out objects you tell it to
create; even more if you expect all compilers to do so. You could be
right but honestly that seems like a lot to expect, especially when the
alternative answer (different syntax, no proxy) is much more easily
optimized away and is already much more optimized than your answer
without any intelligence on behalf of the compiler.

IMO there is a balance that you need to achieve between being overly
agressive with your optimizations and depending on the compiler to do
your work for you. Adding a bunch of unnecissary code and objects to
create a specific syntax and expecting the compiler to just magically
get rid of it all is a little to far into the later area for me.
 
K

Kai-Uwe Bux

Kai-Uwe Bux said:
Gianni Mariani wrote:
(e-mail address removed) wrote:
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-lite/operator-overloading.html#faq-13.11

See also 13.10 right above it.


That FAQ is a classic case of premature optimization.

It's quite easy to turn [A] into (A,B) with no loss of performance
(on a good optimizing compiler).

Oh really??!! Tell me then, how exactly is the compiler going to hide
the internal representiation of the matrix when you have exposed it
with the first [] operator??!! How is the compiler going to decide to
use column major instead of row major, or visa-versa, when it is the
better way to represent the matrix for the particular needs, when you
have created a dependency on row major by using the [] operator to
return rows??!!


The FAQ makes the claim that the [][] interface is less flexible. This is
*not* true in general. The FAQ somehow seems to assume that the only way
of realizing the [][] interface is that operator[] returns an array or
something similar that exposes the internal representation of the matrix
class.


As is done in the above code.


True, but somewhat irrelevant. The FAQ item 13.11 does not specifically talk
about the *above code*. Also, I do not read the claim
It's quite easy to turn [A] into (A,B) with no loss of performance
(on a good optimizing compiler).


as a claim about the particular implementation given up the thread.

However, you do not need to expose the internal representation at
all. The most easy way of doing this, would probably be a proxy:

struct matrix {

typedef unsigned long size_type;

int& operator() ( size_type row, size_type col ) {
return ( whatever(row,col) );
}

struct row_proxy {

matrix & the_matrix;
size_type the_row;

row_proxy ( matrix & A, size_type r )
: the_matrix ( A )
, the_row ( r )
{}

int& operator[] ( size_type col ) {
return( the_matrix.whatever(the_row,col) );
}

};

row_proxy operator[] ( size_type row ) {
return( row_proxy( *this, row ) );
}

// some internal representation to implement whatever goes here:
// ...

}; // matrix

That is an aweful lot of work just to get a particular syntax that just
ends up using the equivilant of (x,y).

Actually, one would need to do a little more to support const correct
programming. I just wanted to illustrate the concept.

However, that does not invalidate the point that [][] does not, in itself,
make a commitment to exposing the internals of a matrix class.

Note that in expressions like A[row][col], the proxy should be
optimized away be a moderately smart optimizing compiler.

Are you sure? Have you tested this theory of yours with your own
compiler?

As I discovered, this is not a theory of mine: actually it is a theory in
the FAQ. See 13.12, last paragraph. (It so happens, that the FAQ actually
covers the proxy approach. I did realize that after writing the message. So
the FAQ is not really off base. I guess, its author chose a policy of
stepwise refinement in the exposition.)
I think you are expecting rather a lot from your compiler if
you expect that it will actually optimize out objects you tell it to
create; even more if you expect all compilers to do so. You could be
right but honestly that seems like a lot to expect, especially when the
alternative answer (different syntax, no proxy) is much more easily
optimized away and is already much more optimized than your answer
without any intelligence on behalf of the compiler.

I think that optimizing away redundant temporary object presents no problem
if the functions returning/creating these objects are inlined. After
inlining, everything boils down to a local data flow analysis problem
essentially on par with any other redundant code removal, e.g., removing
unused local variables.

IMO there is a balance that you need to achieve between being overly
agressive with your optimizations and depending on the compiler to do
your work for you. Adding a bunch of unnecissary code and objects to
create a specific syntax and expecting the compiler to just magically
get rid of it all is a little to far into the later area for me.

Now, we are down to real design considerations. I tend to agree with you.
Personally, I would provide [][] only for interfacing with other code that
needs it.


Best

Kai-Uwe Bux
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,997
Messages
2,570,239
Members
46,827
Latest member
DMUK_Beginner

Latest Threads

Top