Two Dimensional Array Template

[Peter Olcott]

http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a

I think that the operator[]() member function does not work correctly, does
anyone else know how to make a template for making two dimensional arrays from
std::vectors ??? I want to use normal Array[ROW][COL] Syntax.

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a

I think that the operator[]() member function does not work correctly, does
anyone else know how to make a template for making two dimensional arrays from
std::vectors ??? I want to use normal Array[ROW][COL] Syntax.

In the code posted (which you could have included):

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

The 'i_index * m_rows'-part seems kind of fishy to me. It's quite late
right now and I wont spend time thinking much about it, but I think that
'i_index / m_rows' would be more correct, but I might be wrong. Draw a
3x3 matrix on paper and do the math.

 

[Peter Olcott]

http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a

I think that the operator[]() member function does not work correctly, does
anyone else know how to make a template for making two dimensional arrays
from std::vectors ??? I want to use normal Array[ROW][COL] Syntax.

In the code posted (which you could have included):

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

The 'i_index * m_rows'-part seems kind of fishy to me. It's quite late right
now and I wont spend time thinking much about it, but I think that 'i_index /
m_rows' would be more correct, but I might be wrong. Draw a 3x3 matrix on
paper and do the math.

I had partially converted everything over to Array[ROW][COL] order. I discovered
that I needed to convert the above function to

return & ( m_data[ i_index * m_columns ] );

I discovered this solution to my problem within a minute after I posted this
message. The code that I had linked to may still be correct.

Thanks for your help.

 

[Daniel T.]

http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a

I think that the operator[]() member function does not work
correctly, does anyone else know how to make a template for making
two dimensional arrays from std::vectors ?
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.10

I want to use normal Array[ROW][COL] Syntax.

Why?

 

[Peter Olcott]

http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a

I think that the operator[]() member function does not work
correctly, does anyone else know how to make a template for making
two dimensional arrays from std::vectors ?
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.10

I want to use normal Array[ROW][COL] Syntax.

Why?

To eliminate the humongous learning curve cost of violating a universal
standard.

 

[Daniel T.]

http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a

I think that the operator[]() member function does not work
correctly, does anyone else know how to make a template for making
two dimensional arrays from std::vectors ?
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.10

I want to use normal Array[ROW][COL] Syntax.

Why?

To eliminate the humongous learning curve cost of violating a universal
standard.

Read the following two FAQs before making such a mistake.

http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.11
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.12

 

[Peter Olcott]

http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a

I think that the operator[]() member function does not work
correctly, does anyone else know how to make a template for making
two dimensional arrays from std::vectors ?

http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.10

I want to use normal Array[ROW][COL] Syntax.

Why?

To eliminate the humongous learning curve cost of violating a universal
standard.

Read the following two FAQs before making such a mistake.

http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.11
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.12

For my purposes I like this one much better. It is very fast and uses the
standard interface.
I have tested this one, and it works consistently correctly.

// Dynamic Two-Dimensional Array Template
// Array2D.h 2007-01-01 3:02 PM
//
// comp.lang.c++ message from Gianni Mariani Nov 24, 2005 at 9:21 pm
// http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a
// The last three member functions were added by Peter Olcott .
// Other minor adaptations by Peter Olcott
//

#ifndef ARRAY2D_H
#define ARRAY2D_H
#include <vector>

template <typename w_elem_type>
class Array2D
{
typedef unsigned int t_Size;

private:
t_Size m_rows;
t_Size m_columns;
std::vector<w_elem_type> m_data;

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

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

t_Size height() { return m_rows; };
t_Size width() { return m_columns; };
void resize( t_Size i_rows, t_Size i_columns );
};

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

#endif

 

[Daniel T.]

http://groups.google.com/group/comp.lang.c++/msg/
a9092f0f6c9bf13a

I think that the operator[]() member function does not work
correctly, does anyone else know how to make a template for
making two dimensional arrays from std::vectors ?

http://www.parashift.com/c++-faq-lite/operator-overloading.
html#faq-13.10

I want to use normal Array[ROW][COL] Syntax.

Why?

To eliminate the humongous learning curve cost of violating a
universal standard.

Read the following two FAQs before making such a mistake.

http://www.parashift.com/c++-faq-lite/operator-overloading.html#
faq-13.11
http://www.parashift.com/c++-faq-lite/operator-overloading.html#
faq-13.12

For my purposes I like this one much better. It is very fast and
uses the standard interface. I have tested this one, and it works
consistently correctly.

// Dynamic Two-Dimensional Array Template
// Array2D.h 2007-01-01 3:02 PM
//
// comp.lang.c++ message from Gianni Mariani Nov 24, 2005 at 9:21 pm
// http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a
// The last three member functions were added by Peter Olcott .
// Other minor adaptations by Peter Olcott
//

WARNING: the code below will not work with a w_elem_type of bool

#ifndef ARRAY2D_H
#define ARRAY2D_H
#include <vector>

template <typename w_elem_type>
class Array2D
{
typedef unsigned int t_Size;

private:
t_Size m_rows;
t_Size m_columns;
std::vector<w_elem_type> m_data;

public:

The c_tor below should be made explicit.

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

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

t_Size height() { return m_rows; };
t_Size width() { return m_columns; };
void resize( t_Size i_rows, t_Size i_columns );
};

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

#endif

What happens when you decide you want to change your client code to use
a column major or sparse matrix? There goes your learning curve!

It would be better to have a single interface that can be used for row
major, column major, or sparse matrices. The users only need to learn
one interface, and you can change the implementation without modifying
the code that uses the class.

Really, read the FAQ on the subject.

 

[Noah Roberts]

For my purposes I like this one much better. It is very fast and uses the
standard interface.

There is nothing "standard" about [][].

I have tested this one, and it works consistently correctly.

// Dynamic Two-Dimensional Array Template
// Array2D.h 2007-01-01 3:02 PM
//
// comp.lang.c++ message from Gianni Mariani Nov 24, 2005 at 9:21 pm
// http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a
// The last three member functions were added by Peter Olcott .
// Other minor adaptations by Peter Olcott
//

#ifndef ARRAY2D_H
#define ARRAY2D_H
#include <vector>

template <typename w_elem_type>
class Array2D
{
typedef unsigned int t_Size;

private:
t_Size m_rows;
t_Size m_columns;
std::vector<w_elem_type> m_data;

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

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

You should at the least have a typedef for this return in order to
abstractify what you are returning. You don't need to know that you
are getting an elem_type* only that you can retrieve a reference to an
elem_type through [] on the returned data item.

There are numerous problems with the class as described but so long as
you stick to some rather narrowly defined requirements you should be
ok. Of course, letting too much code depend on it will only make
things harder to change later.

Lots of luck to you.

 

[Gianni Mariani]

Daniel T. wrote:
....

Really, read the FAQ on the subject.

I did read the FAQ on the subject a while ago and I disagree with the
assertions. IMHO, the FAQ has this one dead wrong.

If all you need is a simple 2D array, then this one provides most of
what you need. Admitedly, this particular implementation is a bit
sparse, but that is an asset too...

resize is also implemented incorrectly (IMHO), but that's a detail.

 

[Simon G Best]

Hello again!

I don't know if you remember me, but I remember you.

I want to use normal Array[ROW][COL] Syntax.

Why?

To eliminate the humongous learning curve cost of violating a universal
standard.

That's just silly. First of all, "Array[ROW][COL]" is most certainly
*not* a "universal standard". (If you think different, please refer us
to the relevant standard. You know, something like ISO/IEC blah blah
blah.) Secondly, and more importantly, if you find the "learning curve"
of doing 'm(i, j)' "humongous" (?) compared to doing 'm[j]', then I'm
lost as to how you even managed to learn the 'm[j]' type stuff in the
first place. Anyway...

What I like to do is something like this:-

[Start C++ snippet here.]

template< typename T, typename Alloc = ::std::allocator<T> >
class matrix {

public:

// Types

typedef T value_type;
typedef Alloc allocator_type; // (Thank goodness for rebind!)

typedef /* something */ row_size_type; // Size of a row.
typedef /* something */ col_size_type; // Size of a column.
typedef /* something */ row_difference_type; /* Difference between
row sizes. */
typedef /* something */ col_difference_type; /* Difference between
col_sizes. */

typedef /* something */ reference;
typedef /* something */ const_reference;
typedef /* something */ pointer;
typedef /* something */ const_pointer;

typedef /* something */ row_reference; // Reference to row.
typedef /* something */ const_row_reference;
typedef /* something */ col_reference; // Reference to column.
typedef /* something */ const_col_reference;
typedef /* something */ row_pointer; // Pointer to row.
typedef /* something */ const_row_pointer;
typedef /* something */ col_pointer; // Pointer to column.
typedef /* something */ const_col_pointer;

/* Note that the above reference and pointer types do not have to be
of the form 'sometype &' or 'sometype *'. They just need to be
types that can be used as references and pointers.
*/

typedef /* something */ row_iterator; /* Iterator over rows,
not over the elements
of a row. */
typedef /* something */ const_row_iterator;
typedef /* something */ col_iterator; // Iterator over columns.
typedef /* something */ const_col_iterator;
typedef /* something */ reverse_row_iterator;
typedef /* something */ const_reverse_row_iterator;
typedef /* something */ reverse_col_iterator;
typedef /* something */ const_reverse_col_iterator;

// Row, Column and Element Access

reference operator() (col_size_type i, row_size_type j);
/* Returns a reference to the element in row (not column) i and
column j. */
const_reference operator() (col_size_type i, row_size_type j) const;

row_reference row (col_size_type i);
// Returns a reference to row i.
const_row_reference row (col_size_type i) const;
col_reference col (row_size_type j);
const_col_reference col (row_size_type j) const;

row_reference operator[] (col_size_type i) { return row(i); }
const_row_reference operator[] (col_size_type i) const {
return row(i);
}
/* As long as row_references are subscriptable, the familiar (to C
programmers) 'm[j]' style subscripting can be done. With
suitable inlining, such subscripting can be optimized (by the
compiler) into something more efficient. And things like 'm'
can be used to get one-dimensional-array-like references and things
to be passed around to code that operates on
one-dimensional-array-like things.

But row() and col() are clearer, more explicit, than things like
'm[j]' (though my naming of the size and difference types could
be confusing!). Clarity is a good thing. And, as long as
row_references and col_references (and their const versions) have
their own col() and row() member functions, we can write code such
as 'm.row(i).col(j)' - very clear! And, again, with suitable
inlining, we can have it optimized away to something more
efficient.
*/

// Iterators

row_iterator row_begin ();
const_row_iterator const_row_begin ();
row_iterator row_end ();
const_row_iterator const_row_end ();
col_iterator col_begin ();
const_col_iterator const_col_begin ();
col_iterator col_end ();
const_col_iterator const_col_end ();

// (And similarly for reverse iterators.)

// ...
};

[End C++ snippet here.]

Ah, but how's it implemented? Well, I was focussing on the interface,
as that seems to be what you're bothered about. More importantly, the
interface /should not/ be dictated by the implementation. Neither is it
desirable to have the implementation needlessly restricted by the
interface. That's why there are all those "/* something */"s. They
don't necessarily all have to be typedefs, either. Basically, the idea
is to provide an interface that's consistent with the /concept/ of a
matrix, while keeping the /implementation/ behind the scenes.

As long as the interface is sufficiently independent of the
implementation, and the implementation's not needlessly restricted by
the interface, you should be able to have an interface that's clear and
reasonably intuitive to use, at the same time as having an
implementation that does the job well.



Simon

 

[Simon G Best]

Daniel T. wrote:
...

I did read the FAQ on the subject a while ago and I disagree with the
assertions. IMHO, the FAQ has this one dead wrong.

When I read the first FAQ mentioned, I, too, thought it wrong. But then
I read the second FAQ (which followed immediately after). That second
FAQ is not so disagreeable.

I think the real issue is proper separation of interface and implementation.



Simon

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Daniel T. wrote:
...

I did read the FAQ on the subject a while ago and I disagree with the
assertions. IMHO, the FAQ has this one dead wrong.

If all you need is a simple 2D array, then this one provides most of
what you need.

And your error is to assume that only a simple 2D array will ever be needed.

> Admitedly, this particular implementation is a bit
sparse, but that is an asset too...

What do you mean that it's sparse? The way I see it it's as dense as any
implementation I've ever seen.

 

[Simon G Best]

On 2007-01-02 12:55, Gianni Mariani wrote: ....

What do you mean that it's sparse? The way I see it it's as dense as any
implementation I've ever seen.

I think he meant there's not much to the implementation, rather than it
being for sparse matrices.

Simon

 

[Daniel T.]

I did read the FAQ on the subject a while ago and I disagree with
the assertions. IMHO, the FAQ has this one dead wrong.

If all you need is a simple 2D array, then this one provides most of
what you need. Admitedly, this particular implementation is a bit
sparse, but that is an asset too...

However, the OPs complaint has to do with the "humongous learning
curve". Requiring a different interface for row major, column major, and
sparse matrices, as well as a different interface for boolean matrices
as opposed to int matrices is much harder on the user.

resize is also implemented incorrectly (IMHO), but that's a detail.

Also, the class doesn't work for bool matrices.

 

[Noah Roberts]

However, the OPs complaint has to do with the "humongous learning
curve". Requiring a different interface for row major, column major, and
sparse matrices, as well as a different interface for boolean matrices
as opposed to int matrices is much harder on the user.

The OP didn't mention matrices at all. Admitedly a 2d array is pretty
much the same thing but the two titles have slightly different
meanings. A "matrix" is usually used in some linear algebra
calculations or other mathematical implementation....a 2d array is more
general. A matrix can be abstracted to hold any interface and so there
is no reason to use [][] over something else. A "2d array" isn't so
abstract so if you want a "2d array" class then you're pretty much
stuck doing something stupid and/or complex since the sole object of
such a class is to look like a 2d array. I think this is what the OP
is refering to, not what you are saying.

Why you should wrap a 2d array into a class that offers no abstractions
of course is a question. Seems to me there is usually a more
appropriate abstraction for the needs of the domain, and using the
basic data types much easier otherwise, but I don't usually take any
information not provided in my replies. Besides, this has all been
discussed to death and no ground made. If someone really feels they
need to do this to themselves, let them.

 

[Peter Olcott]

Daniel T. wrote:
...

I did read the FAQ on the subject a while ago and I disagree with the
assertions. IMHO, the FAQ has this one dead wrong.

If all you need is a simple 2D array, then this one provides most of what you
need. Admitedly, this particular implementation is a bit sparse, but that is
an asset too...

resize is also implemented incorrectly (IMHO), but that's a detail.

How would you improve how resize() is implemented?

 

[Peter Olcott]

For my purposes I like this one much better. It is very fast and uses the
standard interface.

There is nothing "standard" about [][].

I have tested this one, and it works consistently correctly.

// Dynamic Two-Dimensional Array Template
// Array2D.h 2007-01-01 3:02 PM
//
// comp.lang.c++ message from Gianni Mariani Nov 24, 2005 at 9:21 pm
// http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a
// The last three member functions were added by Peter Olcott .
// Other minor adaptations by Peter Olcott
//

#ifndef ARRAY2D_H
#define ARRAY2D_H
#include <vector>

template <typename w_elem_type>
class Array2D
{
typedef unsigned int t_Size;

private:
t_Size m_rows;
t_Size m_columns;
std::vector<w_elem_type> m_data;

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

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

You should at the least have a typedef for this return in order to
abstractify what you are returning. You don't need to know that you
are getting an elem_type* only that you can retrieve a reference to an
elem_type through [] on the returned data item.

I have no idea what you are talking about. You get a pointer to whatever type
formed the parameter to the template. Why is this not perfect the way that it
is?

There are numerous problems with the class as described but so long as
you stick to some rather narrowly defined requirements you should be
ok. Of course, letting too much code depend on it will only make
things harder to change later.

This class should provide a two dimensional array of anything, what
imperfections do you see with this?

 

[Peter Olcott]

Hello again!

I don't know if you remember me, but I remember you.

I want to use normal Array[ROW][COL] Syntax.
Why?

To eliminate the humongous learning curve cost of violating a universal
standard.

That's just silly. First of all, "Array[ROW][COL]" is most certainly *not* a
"universal standard". (If you think different, please refer us

This is the way that C/C++ are defined to work, it is a universal standard
within these two (and several other) languages.

to the relevant standard. You know, something like ISO/IEC blah blah blah.)
Secondly, and more importantly, if you find the "learning curve" of doing
'm(i, j)' "humongous" (?) compared to doing 'm[j]', then I'm lost as to how
you even managed to learn the 'm[j]' type stuff in the first place.
Anyway...

What I like to do is something like this:-

[Start C++ snippet here.]

template< typename T, typename Alloc = ::std::allocator<T> >
class matrix {

public:

// Types

typedef T value_type;
typedef Alloc allocator_type; // (Thank goodness for rebind!)

typedef /* something */ row_size_type; // Size of a row.
typedef /* something */ col_size_type; // Size of a column.
typedef /* something */ row_difference_type; /* Difference between
row sizes. */
typedef /* something */ col_difference_type; /* Difference between
col_sizes. */

typedef /* something */ reference;
typedef /* something */ const_reference;
typedef /* something */ pointer;
typedef /* something */ const_pointer;

typedef /* something */ row_reference; // Reference to row.
typedef /* something */ const_row_reference;
typedef /* something */ col_reference; // Reference to column.
typedef /* something */ const_col_reference;
typedef /* something */ row_pointer; // Pointer to row.
typedef /* something */ const_row_pointer;
typedef /* something */ col_pointer; // Pointer to column.
typedef /* something */ const_col_pointer;

/* Note that the above reference and pointer types do not have to be
of the form 'sometype &' or 'sometype *'. They just need to be
types that can be used as references and pointers.
*/

typedef /* something */ row_iterator; /* Iterator over rows,
not over the elements
of a row. */
typedef /* something */ const_row_iterator;
typedef /* something */ col_iterator; // Iterator over columns.
typedef /* something */ const_col_iterator;
typedef /* something */ reverse_row_iterator;
typedef /* something */ const_reverse_row_iterator;
typedef /* something */ reverse_col_iterator;
typedef /* something */ const_reverse_col_iterator;

// Row, Column and Element Access

reference operator() (col_size_type i, row_size_type j);
/* Returns a reference to the element in row (not column) i and
column j. */
const_reference operator() (col_size_type i, row_size_type j) const;

row_reference row (col_size_type i);
// Returns a reference to row i.
const_row_reference row (col_size_type i) const;
col_reference col (row_size_type j);
const_col_reference col (row_size_type j) const;

row_reference operator[] (col_size_type i) { return row(i); }
const_row_reference operator[] (col_size_type i) const {
return row(i);
}
/* As long as row_references are subscriptable, the familiar (to C
programmers) 'm[j]' style subscripting can be done. With
suitable inlining, such subscripting can be optimized (by the
compiler) into something more efficient. And things like 'm'
can be used to get one-dimensional-array-like references and things
to be passed around to code that operates on
one-dimensional-array-like things.

But row() and col() are clearer, more explicit, than things like
'm[j]' (though my naming of the size and difference types could
be confusing!). Clarity is a good thing. And, as long as
row_references and col_references (and their const versions) have
their own col() and row() member functions, we can write code such
as 'm.row(i).col(j)' - very clear! And, again, with suitable
inlining, we can have it optimized away to something more
efficient.
*/

// Iterators

row_iterator row_begin ();
const_row_iterator const_row_begin ();
row_iterator row_end ();
const_row_iterator const_row_end ();
col_iterator col_begin ();
const_col_iterator const_col_begin ();
col_iterator col_end ();
const_col_iterator const_col_end ();

// (And similarly for reverse iterators.)

// ...
};

[End C++ snippet here.]

Ah, but how's it implemented? Well, I was focussing on the interface, as that
seems to be what you're bothered about. More importantly, the interface
/should not/ be dictated by the implementation. Neither is it desirable to
have the implementation needlessly restricted by the interface. That's why
there are all those "/* something */"s. They don't necessarily all have to be
typedefs, either. Basically, the idea is to provide an interface that's
consistent with the /concept/ of a matrix, while keeping the /implementation/
behind the scenes.

As long as the interface is sufficiently independent of the implementation,
and the implementation's not needlessly restricted by the interface, you
should be able to have an interface that's clear and reasonably intuitive to
use, at the same time as having an implementation that does the job well.



Simon

 

[Peter Olcott]

And your error is to assume that only a simple 2D array will ever be needed.

That is the specified scope of the problem, within this specified scope, the
solution (as far as I can tell) is perfect. If one does not restrict oneself to
the specified scope, then any possible solution to any possible problem becomes
totally lacking and woefully inadequate simply because the solution does not
solve EVERY POSSIBLE problem.