Operator [][]?

[Michael DeWulf]

I am trying to make a 2D matrix class. The data in the matrix will be of
type int and so the underlying data structure will be a 2D array (int **
matrix). To make the data easy to modify, I would like to be able to
modify this private array in the class with the operator [][]. I know
that the operator[] can be overloaded. However, is there away to overload
[][]?

Thanks,
Michael

 

[Alf P. Steinbach]

* Michael DeWulf:

I am trying to make a 2D matrix class. The data in the matrix will be of
type int and so the underlying data structure will be a 2D array (int **
matrix). To make the data easy to modify, I would like to be able to
modify this private array in the class with the operator [][]. I know
that the operator[] can be overloaded. However, is there away to overload
[][]?

Not directly, but it can be done by letting operator[] return a proxy
object, or letting it return a pointer or a reference to something
indexable.

However, the proxy idea generally means reduced performance, and the
pointer and reference ideas expose the implementation so it can't be
changed (and a pointer to a raw array is very unsafe).

For more about the latter point, and how you should be doing this
(namely, using operator()), see the FAQ item titled "Why shouldn't my
Matrix class's interface look like an array-of-array?", currently at
<url:
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.11>.

Btw., it's always a good idea to look in the FAQ before posting.

And do consider using a std::vector as the representation, rather than a
raw pointer to dynamically allocated array.

It's more safe and yields less code and more clear code.

Hth.,

- Alf

 

[Kai-Uwe Bux]

* Michael DeWulf:

To the OP: don't---use one of those that are around.

The data in the matrix will be of
type int and so the underlying data structure will be a 2D array (int **
matrix). To make the data easy to modify, I would like to be able to
modify this private array in the class with the operator [][]. I know
that the operator[] can be overloaded. However, is there away to
overload
[][]?

Not directly, but it can be done by letting operator[] return a proxy
object, or letting it return a pointer or a reference to something
indexable.

However, the proxy idea generally means reduced performance,

Do you have actual data to back up that theory? I just whipped up the
following quickly:

#include <vector>
#include <algorithm>

class Matrix {

typedef std::vector<double> array;

public:

typedef array::size_type size_type;

private:

array the_data;
size_type num_rows;
size_type num_cols;

struct EntryProxy;
struct ConstEntryProxy;
friend class EntryProxy;
friend class ConstEntryProxy;

struct EntryProxy {

Matrix & ref;
size_type row;

EntryProxy ( Matrix & m, size_type r )
: ref ( m )
, row ( r )
{}

double & operator[] ( size_type col ) {
return ( ref.the_data[ row * ref.num_cols + col ] );
}

};

struct ConstEntryProxy {

Matrix const & ref;
size_type row;

ConstEntryProxy ( Matrix const & m, size_type r )
: ref ( m )
, row ( r )
{}

double const & operator[] ( size_type col ) const {
return ( ref.the_data[ row * ref.num_cols + col ] );
}

};



public:

Matrix ( size_type n_rows = 0, size_type n_cols = 0 )
: the_data ()
, num_rows ( n_rows )
, num_cols ( n_cols )
{
the_data.resize( num_rows * num_cols );
}

void swap ( Matrix & other ) {
std::swap( this->the_data, other.the_data );
std::swap( this->num_rows, other.num_rows );
std::swap( this->num_cols, other.num_cols );
}

double & operator() ( size_type row, size_type col ) {
return ( the_data[ row*num_cols + col ] );
}

double const & operator() ( size_type row, size_type col ) const {
return ( the_data[ row*num_cols + col ] );
}

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

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

size_type rows ( void ) const {
return ( num_rows );
}

size_type cols ( void ) const {
return ( num_cols );
}

};


void multiply_no_proxy ( Matrix const & A,
Matrix const & B,
Matrix & result ) {
Matrix dummy ( A.rows(), B.cols() );
for ( Matrix::size_type r = 0; r < dummy.rows(); ++r ) {
for ( Matrix::size_type c = 0; c < dummy.cols(); ++c ) {
double inner_prod = 0;
for ( Matrix::size_type k = 0; k < A.cols(); ++k ) {
inner_prod += A(r,k)*B(k,c);
}
dummy( r, c ) = inner_prod;
}
}
result.swap( dummy );
}

void multiply_proxy ( Matrix const & A,
Matrix const & B,
Matrix & result ) {
Matrix dummy ( A.rows(), B.cols() );
for ( Matrix::size_type r = 0; r < dummy.rows(); ++r ) {
for ( Matrix::size_type c = 0; c < dummy.cols(); ++c ) {
double inner_prod = 0;
for ( Matrix::size_type k = 0; k < A.cols(); ++k ) {
inner_prod += A[r][k]*B[k][c];
}
dummy[r][c] = inner_prod;
}
}
result.swap( dummy );
}

#include <iostream>

int main ( void ) {
Matrix A ( 200, 3000 );
Matrix B ( 3000, 200 );
Matrix C;
#ifdef USE_PROXY
multiply_proxy( A, B, C );
std::cout << "used proxy " << C(2,2);
#else
multiply_no_proxy( A, B, C );
std::cout << "did not use proxy " << C(2,2);
#endif
std::cout << '\n';
}

I got:

news_group> cc++ -O3 -DUSE_PROXY alf_008.cc
news_group> time a.out
used proxy 0

real 0m2.374s
user 0m1.540s
sys 0m0.076s
news_group> time a.out
used proxy 0

real 0m3.151s
user 0m1.920s
sys 0m0.088s
news_group> time a.out
used proxy 0

real 0m3.137s
user 0m1.936s
sys 0m0.116s
news_group> time a.out
used proxy 0

real 0m2.723s
user 0m1.756s
sys 0m0.076s

news_group> cc++ -O3 alf_008.cc
news_group> time a.out
did not use proxy 0

real 0m2.343s
user 0m1.564s
sys 0m0.056s
news_group> time a.out
did not use proxy 0

real 0m2.474s
user 0m1.584s
sys 0m0.064s
news_group> time a.out
did not use proxy 0

real 0m2.924s
user 0m1.856s
sys 0m0.084s
news_group> time a.out
did not use proxy 0

real 0m3.166s
user 0m1.812s
sys 0m0.096s


Doesn't look like a significant difference to me. I wouldn't be surprised if
a compiler would generate identical code for both programs.

and the
pointer and reference ideas expose the implementation so it can't be
changed (and a pointer to a raw array is very unsafe).

Agreed.

For more about the latter point, and how you should be doing this
(namely, using operator()), see the FAQ item titled "Why shouldn't my
Matrix class's interface look like an array-of-array?", currently at
<url:
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-13.11>.

Btw., it's always a good idea to look in the FAQ before posting.

This particular point of the FAQ is highly contested: The interface design
suggested by the FAQ may make sense from the point of view of the
implementer. However, libraries are to be designed from the point of view
of the user. In that case, you want to have proxies for rows and columns
anyway so that you could do, e.g., row-operations like so:

A.row(i) += some_scalar* A.row(j);

Of course, such proxies require some amount of magic. A good matrix
interface is not for the faint of heart.

And do consider using a std::vector as the representation, rather than a
raw pointer to dynamically allocated array.

It's more safe and yields less code and more clear code.

I took the liberty to illustrate that in the code.


Best

Kai-Uwe Bux

 

[Alf P. Steinbach]

* Kai-Uwe Bux:

Do you have actual data to back up that theory?

Nope, just hearsay (although from competent folks), the expectation that
added code and longer call chains means reduced performence, and my own
experience /many/ years ago -- it was probably with Turbo C++...

I just whipped up the following quickly:

[example showing no significant performance difference, snipped]

I stand (or actually, to be honest, sit) corrected -- thanks.

news_group> cc++ -O3 -DUSE_PROXY alf_008.cc

I only have one program from you that I've tested, and you've already
reached number 8 on me! :-o)

Cheers,

- Alf

 

[Gianni Mariani]

Alf P. Steinbach wrote: ....

This particular point of the FAQ is highly contested:...

Just want to add my $0.02 worth. I agree with you. I think we had this
discussion 6 months ago. Maybe it is time to get the FAQ changed.

G

 

[Noah Roberts]

I am trying to make a 2D matrix class. The data in the matrix will be of
type int and so the underlying data structure will be a 2D array (int **
matrix). To make the data easy to modify, I would like to be able to
modify this private array in the class with the operator [][]. I know
that the operator[] can be overloaded. However, is there away to overload
[][]?

No, but [,] is "overloadable":

By Jack Saalweachter

struct MagicInt {
// operator overloads, constructors, etc, to make this class behave
// as an integer.

};

std:air<MagicInt, MagicInt> operator , (const MagicInt &a, const
MagicInt& b) { return std::make_pair(a, b); }

class Array2d {
public:
value& operator[](const std:air<MagicInt, MagicInt> &a) {
// use a.first and a.second to find the value...
}

};

int main() {
Array2d M(X, Y);

for (MagicInt a = 0; a < X; ++a)
for (MagicInt b = 0; b < Y; ++b)
M[a, b] = i + j;

}

Of course, overloading (,) works better and is a lot easier.

 

[Earl Purple]

Just want to add my $0.02 worth. I agree with you. I think we had this
discussion 6 months ago. Maybe it is time to get the FAQ changed.

G

My matrix template allows both notations. operator[] returns a row and
from the row you can also use operator[] to get an element. operator()
gets the element directly.

The row is of a buffer type that I use throughout my code that is
effectively a weak pointer and a size. It also has begin() and end()
methods that return pointers and can be used in algorithms. It has
several constructors including an implicit one from vector and it does
not take ownership of its pointer. There are two versions, one for
const and one for non-const and the const one has an implicit
constructor from the non-const one.