Two Dimensional Array Template

[Daniel T.]

(2) that any implementation of [][] with similar capabilities will
inevitably be a "wrapper" (via proxies or whatever) for a (,) interface.

This is the point that has been repeated ad nauseam in this thread, but
nobody proved it nor explained his meaning. What will be the way to
establish if some implementation is a wrapper or other or not, other than
see it explicitly done that way in the code?

Julián, please see earlier in the thread where Gianni provided the [][]
interface that was a wrapper for the (,) interface. Alternatively, you
can follow the explanation for that interface given in the FAQ at the
bottom of question 13.12

And even supposing the claim were true, that is not a reason to ban the
usage of other syntax. There are many cases in C++ where alternative syntax
peacefully coexist.

I'm not looking to ban anything, nor does the FAQ attempt to ban
anything. Some people have taken exception to FAQ questions 13.10-12
while not denying anything claimed in them. That is irrational.

If you care to deny any of the claims made in the FAQ questions 13.10-12
(and their justifications,) then please do so. If there is a problem
with the FAQ in this area, I would like to know what it is.

 

[Simon G Best]

Interesting...

So, you're deciding what should go in the interface on the
basis of implementation?
Close. I'm deciding on what should go in the interface on the
basis of its flexibility in hiding the details of the
implementation. I.E., on its ability to abstract the problem
space.

Since, as you've pointed out so many times, []-style subscripting
can be implemented in terms of (,), []-style subscripting must be
at least as flexible "in hiding the details of the implementation"
as (,). (That was the whole point of all that proxy stuff!!!)

As flexible, but no more so. See below...

In the following, I note that you'd previously said, "the more flexible
interface actually requires *less* effort".

You now say:-

I do not dispute that the [][] interface provided by both the FAQ and
Gianni is as flexible as the (,) interface provided by the FAQ.

So, when it comes to flexibility *"in hiding the details of the
implementation"*, you do now accept that the (,)-style interface is no
more flexible than the []-style.

However, the [][] interface provided does not add flexibility and it
requires *more* effort to create than the (,) interface provided
(except in legacy code situations.) As I say above, when comparing
two equally flexible interfaces, the one that requires less effort is
the better interface.

It certainly adds no extra flexibility *"in hiding the details of the
implementation"*, but /it is a more general interface/ - something
you've conveniently snipped and ignored. Unsnipping it, I'd said:-

Also, something you seem to be stuck on is the idea that the two []s
have to go together. They don't. The first can be in one function,
and the second in another. And, as you /can/ use them together,
[][]-style, the []-style interface is actually /more/ general than
(,), and no less flexible.

That's "/more/ general" *not* in the sense of /implementation/
flexibility, but in the sense of *use.*

 

[Noah Roberts]

Also, something you seem to be stuck on is the idea that the two []s
have to go together. They don't. The first can be in one function,
and the second in another. And, as you /can/ use them together,
[][]-style, the []-style interface is actually /more/ general than
(,), and no less flexible.

That's "/more/ general" *not* in the sense of /implementation/
flexibility, but in the sense of *use.*

No it isn't. It is less flexible because you can't directly access any
given data coordinate without the unnecissary 2nd call and possible
creation of an extraneous proxy instance. It is also incapable of
expressing the function of both column and row but instead limited to
one or the other.

Without f(,) and f() the [][] interface is incomplete. With them the
[][] interface is just extra fluf. When and if the [][] is necissary
and the dependency can't be fixed you can wrap your abstraction in
something that provides it with minor work as Gianni showed (with the
minor modification that the first op[] doesn't have to be in the main
interface):

template < typename T >
class RowMjr
{
T & abstraction;
public:
RowMjr(T & t) : abstraction(t) {}

row_proxy operator[] (int x) { return abstraction.row(x); }
};

similarly for ColMjr. Now "legacy code" (that likely needs changes to
work with templates instead of assuming arrays now anyway) can be used
with a little less modification.

Any raw array of arrays can also be easily wrapped to adhere to the
abstraction's interface.

The fact is, the legacy issue is a non-issue. If you aren't worried
about the extra proxy class then you can't exactly be too worried about
tiny wrapper either. You can use adapters for either interface. It's
all a case of what is simpler. When starting from scratch there is no
need for the extra complexity and vagueness of your [] overloads. When
working with legacy issues it's a balancing act...there is no reason to
believe that [] overloads are any better without knowing the specifics
of the problem.

 

[Simon G Best]

:-(

Simon G Best wrote: ....

No, they are one or the other, not both. Common convention says they
are arrays of rows.

xxxxx
xxxxx
xxxxx
xxxxx

It's both. It can be viewed both ways, but it's still the same thing.

and they should be presented as such. It's conventional to subcript
arrays through operator[], so operator[] should be provided for the
array-of-rows and array-of-colums views of two-dimensional arrays.

You can only do it once. You can't do it for both. Why should one get
preference over the other?

Once for each view. Base classes and proxies would both work for that.

In general, there's no reason to provide it for one view
and not the other, or to give preference to one view over the other.
(This is, I think, a much better argument against operator[] /as
considered in this thread/ than many of the other arguments offered.)

Yeah, I made it a long time ago. I guess you're not paying attention.

Perhaps I missed it.

One way we could solve this problem is to derive our two-dimensional
array class from two interface-providing bases, one for the
array-of-rows view and one for the array-of-columns view. Each base
would then provide its own operator[] accordingly, as would the proxies
likely to be returned.

Yeah because calling mtx.(ColMjr:perator[])(5)[4], or
static_cast<ColMjr&>(mtx)[5][4] is so much more convenient than
mtx.row(5).value(4)

I've already suggested row(), col(), and the like, in previous posts.
What was that about not paying attention?

You guys are just too operator happy for your own good.

array_of_columns &a(mtx); // Taking the array-of-columns view.
foo(a);
bar(a[5]);
baz(a.begin(), a.end());
qux(a[3].begin(), a[3].end());
for (array_of_columns::size_type i(0); i < a.size(); ++i) quux(a);
....

 

[Simon G Best]

Also, something you seem to be stuck on is the idea that the two []s
have to go together. They don't. The first can be in one function,
and the second in another. And, as you /can/ use them together,
[][]-style, the []-style interface is actually /more/ general than
(,), and no less flexible.

That's "/more/ general" *not* in the sense of /implementation/
flexibility, but in the sense of *use.*

No it isn't. It is less flexible because you can't directly access any
given data coordinate without the unnecissary 2nd call and possible
creation of an extraneous proxy instance. It is also incapable of
expressing the function of both column and row but instead limited to
one or the other.

Okay. Fortunately I'm already in favour of including (,) in the
interface

....

If you aren't worried
about the extra proxy class then you can't exactly be too worried about
tiny wrapper either.

....

Wrappers sound fine to me

 

[Daniel T.]

Simon,

Let me put this in a simple manor with a code example.

class array {
public:
// constructor(s) as necessary
int& operator[]( unsigned i );
};

class array2Da {
public:
// constructor(s) as necessary
array& operator[]( unsigned i );
array& col( unsigned i );
};

class array2Db {
public:
// constructor(s) as necessary
array& row( unsigned i );
array& col( unsigned i );
int& operator()( unsigned i, unsigned j );
};

Which of the two interfaces (array2Da or array2Db) are better, or is
neither better than the other?

IMO and according to the FAQ, array2Db is the better interface and
frankly, no one, AFAICT and despite all the protestations, has claimed
that array2Da is better except for Peter (the OP of this thread) in his
initial post, and he never justified his reasons for believing so.

Even Gianni, when pressed to actually show an implementation, provided
one that had array2Db as its interface (though he maintained the name
op[] rather than switch to "row".)

class array2Dc {
public:
// constructor(s) as necessary
array& operator[]( unsigned i );
array& col( unsigned i );
int& operator()( unsigned i, unsigned j );
};

The above is Gianni's interface proposal (and the one outlined in FAQ
13.12.) Now, given the above interface, if you want to access a single
element in the array, what is the best method in doing so?

Again IMO, and according to the FAQ, calling op(,) is a better method of
accessing a single element of the array (as opposed to calling op[] and
then op[] on the result.) Now this is something that several seem to be
disagreeing with, but frankly I don't understand why.

 

[Simon G Best]

Wow, I think you've really misunderstood me.

Daniel T. wrote:
....

Again IMO, and according to the FAQ, calling op(,) is a better method of
accessing a single element of the array (as opposed to calling op[] and
then op[] on the result.) Now this is something that several seem to be
disagreeing with, but frankly I don't understand why.

No, I really think you've got that wrong. Just because there are some
of us who disagree with your reasons for objecting to the inclusion of
[]s, it doesn't mean that we're objecting to the inclusion and use of
(,). Indeed, as I'm sure I've already said in this thread, I'm in
favour of (,). Just because you think it has to be either [][] or (,),
it doesn't mean the rest of us do, too.

 

[Daniel T.]

Daniel T. wrote:

Again IMO, and according to the FAQ, calling op(,) is a better method of
accessing a single element of the array (as opposed to calling op[] and
then op[] on the result.) Now this is something that several seem to be
disagreeing with, but frankly I don't understand why.

No, I really think you've got that wrong. Just because there are some
of us who disagree with your reasons for objecting to the inclusion of
[]s, it doesn't mean that we're objecting to the inclusion and use of
(,).

I have not objected to the inclusion of []s in the interface. The FAQ
also doesn't object to the inclusion of []s in the interface (it even
mentions it as an option.) What I, and the FAQ, object to is people who
think [][] should be the only method provided to access a single element
of a 2D array.

Just because you think it has to be either [][] or (,), it doesn't
mean the rest of us do, too.

When the user of the array wants to access one element of a 2D array, he
must either use [][] or (,) (assuming both are available,) so yes it has
to be either [][] or (,). In that case, the (,) is the best choice for
the user. To deny him that choice (the best choice) is silly.

Let me ask you directly. After reading the FAQs 13.10-12, is there
anything you spicifically object to? There has been a lot of heat in
this thread about those FAQs yet *no one*, not even Gianni has pointed
to any paragraph in any of those questions and said, "this is wrong."

The question above goes out to everybody. If no one objects to any part
of the FAQs in question, I don't see why there is so much heat over them.

 

[Simon G Best]

Daniel T. wrote:

Again IMO, and according to the FAQ, calling op(,) is a better method of
accessing a single element of the array (as opposed to calling op[] and
then op[] on the result.) Now this is something that several seem to be
disagreeing with, but frankly I don't understand why.

No, I really think you've got that wrong. Just because there are some
of us who disagree with your reasons for objecting to the inclusion of
[]s, it doesn't mean that we're objecting to the inclusion and use of
(,).

I have not objected to the inclusion of []s in the interface.

Who are you trying to kid?

If you're objecting to having [][] in the interface, you /are/ objecting
to the inclusion of the []s, *because that's all that [][] is!* And you
most certainly have objected, as you've previously given the extra
complexity of implementing them as a reason for not having them.

The FAQ
also doesn't object to the inclusion of []s in the interface (it even
mentions it as an option.) What I, and the FAQ, object to is people who
think [][] should be the only method provided to access a single element
of a 2D array.

Again, who are you trying to kid?

What you've done, in previous posts, is to argue against /including/
[][]. That's not the same as merely objecting to the idea that [][]
should be the /only/ method.

Just because you think it has to be either [][] or (,), it doesn't
mean the rest of us do, too.

When the user of the array wants to access one element of a 2D array, he
must either use [][] or (,) (assuming both are available,) so yes it has
to be either [][] or (,). In that case, the (,) is the best choice for
the user. To deny him that choice (the best choice) is silly.

Oh, come on! Do you /really/ think that's what I meant? That it's
possible to use [][] and (,) simultaneously for the same, single access
operation? Huh?

 

[Daniel T.]

Daniel T. wrote:

I have not objected to the inclusion of []s in the interface.

Who are you trying to kid?

Quotes from me:
(Jan 1)
Read the following two FAQs before making such a mistake. [The FAQs
in question are 13.10-12 and the mistake in question was to create a
class that didn't have any means to access a single element except
through [][] ].

(Jan 4)
...there is no reason to use the [][] interface when the (,)
interface is available. [Note: I said "use", not "include".]

(Jan 5)
I'm not looking to ban anything, nor does the FAQ attempt to ban
anything.

However, I have no interest in arguing with you about what I really
meant. I'm willing to accept that I have been unable to articulate my
position well enough. Hence the reason I kept trying to clarify it.

 

[Gianni Mariani]

(2) that any implementation of [][] with similar capabilities will
inevitably be a "wrapper" (via proxies or whatever) for a (,) interface.

This is the point that has been repeated ad nauseam in this thread, but
nobody proved it nor explained his meaning. What will be the way to
establish if some implementation is a wrapper or other or not, other than
see it explicitly done that way in the code?

Julián, please see earlier in the thread where Gianni provided the [][]
interface that was a wrapper for the (,) interface. Alternatively, you
can follow the explanation for that interface given in the FAQ at the
bottom of question 13.12

You seem to have a very narrow perspective of the example. Why do you
insist on believing that [][] must be a wrapper to (,) ?

 

[Daniel T.]

Lionel B wrote:

(2) that any implementation of [][] with similar capabilities
will inevitably be a "wrapper" (via proxies or whatever) for a
(,) interface.

This is the point that has been repeated ad nauseam in this
thread, but nobody proved it nor explained his meaning. What
will be the way to establish if some implementation is a wrapper
or other or not, other than see it explicitly done that way in
the code?

Julián, please see earlier in the thread where Gianni provided the
[][] interface that was a wrapper for the (,) interface.
Alternatively, you can follow the explanation for that interface
given in the FAQ at the bottom of question 13.12

You seem to have a very narrow perspective of the example. Why do
you insist on believing that [][] must be a wrapper to (,) ?

If you care to deny any of the claims made in the FAQ questions 13.10-12
(and their justifications,) then please do so. If there is a problem
with the FAQ in this area, I would like to know what it is.

Up to this point, you have not denied any spcific claim made by the FAQ,
you have simply said you don't like it, while at the same time you
posted code that specifically conforms to the FAQ.

 

[Simon G Best]

Daniel T. wrote:

I have not objected to the inclusion of []s in the interface.

Who are you trying to kid?

Quotes from me: ....

(Jan 4)
...there is no reason to use the [][] interface when the (,)
interface is available. [Note: I said "use", not "include".]

Yet you'd previously given the extra effort of implementing the []s as a
reason against them. At least, that appeared to be the case, such as in
the following:-

(Jan 5)

> So, you're deciding what should go in the interface on the basis
> of implementation?

Close. I'm deciding on what should go in the interface on the basis
of its flexibility in hiding the details of the implementation.
I.E., on its ability to abstract the problem space.

The interface that allows the most implementation flexibility with
the least effort is the better interface. Now in many cases, there
may be some tension between "flexibility" and "effort" (i.e., a
question as to whether the extra effort is worth the extra
flexibility,) but in this case (with the exception of legacy code
situations) the more flexible interface actually requires *less*
effort.

And:-

(Also Jan 5)
I do not dispute that the [][] interface provided by both the FAQ
and Gianni is as flexible as the (,) interface provided by the FAQ.
However, the [][] interface provided does not add flexibility and it
requires *more* effort to create than the (,) interface provided
(except in legacy code situations.) As I say above, when comparing
two equally flexible interfaces, the one that requires less effort
is the better interface.

All the extra effort is in the implementing, /not/ the use.

I'm done with this.

 

[Noah Roberts]

Wow, I think you've really misunderstood me.

Daniel T. wrote:
...

Again IMO, and according to the FAQ, calling op(,) is a better method of
accessing a single element of the array (as opposed to calling op[] and
then op[] on the result.) Now this is something that several seem to be
disagreeing with, but frankly I don't understand why.

No, I really think you've got that wrong. Just because there are some
of us who disagree with your reasons for objecting to the inclusion of
[]s, it doesn't mean that we're objecting to the inclusion and use of
(,). Indeed, as I'm sure I've already said in this thread, I'm in
favour of (,). Just because you think it has to be either [][] or (,),
it doesn't mean the rest of us do, too.

There is no reason to have two functions that do the same thing. You
should really pick one or the other. If there is a legacy issue it
should be deemed deprecated and only included for backwards compat.
All code using the function in question should be changed.

 

[Kai-Uwe Bux]

Julián Albo wrote:
Noah Roberts wrote:

Since [][] is a chaining of function calls, and not a single
call, it requires an additional object which (,) does not.
[][] requires this extra object while (,) simply does not
preclude it. Since it requires less and imposes no more it is
the more abstract solution.

This is a detail of the implementation that has no relation with
the level of abstraction.

The extra object is exposed in the interface. If it has no
relation to the abstraction it has no business in the interface
and again (,) is the better alternative.

But of course row proxies have a relation to the matrix abstraction.
What makes a matrix a 2-dimensional array is that it has rows and
columns. Any interface that does not provide a way of addressing
these important sum-matrices as some type of vector is very
low-level.

The matrix class I use has row and column proxies. You can get a row
by the row() method and a column by the column() method. It happens
that operator[] returns a row proxy. The main advantage of the proxy
classes is not that they allow [][] notation but lies in the way
they enrich the interface.

From the FAQ:
In particular, if these inner array-like objects end up allocating
their own block of memory for their row [or column] of the matrix,
the performance overhead for creating / destroying your matrix
objects can grow dramatically.

If I want to access just one element in the array, must I create a row
or column proxy?

Note the "if" in the FAQ. In reasonable implementations, there is no
overhead for accessing a single element via a proxy. The proxy gets
optimized away by any modern compiler. Please have a look at my exchange
with Alf Steinbach on this matter:

http://groups.google.com/group/comp...q=Bux+Steinbach+proxy&rnum=1#cecce09e32c2dfc6


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Julián Albo wrote:
Noah Roberts wrote:

Since [][] is a chaining of function calls, and not a single call,
it
requires an additional object which (,) does not. [][] requires
this
extra object while (,) simply does not preclude it. Since it
requires less and imposes no more it is the more abstract solution.

This is a detail of the implementation that has no relation with the
level of abstraction.

The extra object is exposed in the interface. If it has no relation to
the abstraction it has no business in the interface and again (,) is
the better alternative.

But of course row proxies have a relation to the matrix abstraction. What
makes a matrix a 2-dimensional array is that it has rows and columns. Any
interface that does not provide a way of addressing these important
sum-matrices as some type of vector is very low-level.

The matrix class I use has row and column proxies. You can get a row by
the row() method and a column by the column() method. It happens that
operator[] returns a row proxy. The main advantage of the proxy classes
is not that they allow [][] notation but lies in the way they enrich the
interface. For instance, I can say

swap( A.row(i), A.row(j) );

Yes, accessing row and column objects is likely needed in a matrix.
You are likely to want both at different times. For instance,
multiplying two matrices involves taking a row from one site, a column
from another, multiplying them and repeating. So there should be a
column vector object as well. Since there are two, and only one
operator[], it makes more sense to do what you have done above and not
pick one to get the [] interface.

Like Daniel said as well, there if there is no need you shouldn't have
to pay the cost. This is rather fundamental to C++. If you don't need
row/column objects you shouldn't have to allocate them.

In my experience, compilers optimize away the proxy objects if you just use
them to access a matrix coefficient. See

http://groups.google.com/group/comp...q=Bux+Steinbach+proxy&rnum=1#cecce09e32c2dfc6

for some measurements.

Yes, this can
be sped up quite a bit through even more complexity and become a rather
negligable cost in runtime but the principles still hold.

The test code I used in that thread is totally straight forward. In my
experience, there is no runtime overhead for [][] even for the most
straight forward implementations of row and column proxies.


Best

Kai-Uwe Bux

 

[Gianni Mariani]

Daniel T. wrote:
....

If you care to deny any of the claims made in the FAQ questions 13.10-12
(and their justifications,) then please do so. If there is a problem
with the FAQ in this area, I would like to know what it is.

I already have - multiple times - go re-read the posts. I picked them
apart in a previous post. The only justification the FAQ make is
blatantly false and then it's also debunked by the FAQ itself.

Up to this point, you have not denied any spcific claim made by the FAQ,
you have simply said you don't like it, while at the same time you
posted code that specifically conforms to the FAQ.

What are you smoking, really! I want some.

 

[Daniel T.]

From the FAQ:
In particular, if these inner array-like objects end up allocating
their own block of memory for their row [or column] of the matrix,
the performance overhead for creating / destroying your matrix
objects can grow dramatically.

If I want to access just one element in the array, must I create a row
or column proxy?

Note the "if" in the FAQ. In reasonable implementations, there is no
overhead for accessing a single element via a proxy.

The "all true Scotsman" fallacy, you are giving "reasonable" a special
definition.

(from FAQ 13.12)
If you have a decent compiler and if you judiciously use inlining,
the compiler should optimize away the temporary objects. In other
words, the operator[]-approach above will hopefully not be slower
than what it would have been if you had directly called
Matrix:perator()(unsigned row, unsigned col) in the first place. Of
course you could have made your life simpler and avoided most of the
above work by directly calling Matrix:perator()(unsigned row,
unsigned col) in the first place. So you might as well directly call
Matrix:perator()(unsigned row, unsigned col) in the first place.

Is there anything in FAQs 13.10-12 that you specifically object to? If
yes, what is it and why?

 

[Kai-Uwe Bux]

From the FAQ:
In particular, if these inner array-like objects end up allocating
their own block of memory for their row [or column] of the matrix,
the performance overhead for creating / destroying your matrix
objects can grow dramatically.

If I want to access just one element in the array, must I create a row
or column proxy?

Note the "if" in the FAQ. In reasonable implementations, there is no
overhead for accessing a single element via a proxy.

The "all true Scotsman" fallacy, you are giving "reasonable" a special
definition.

Please note that I do not give any definition for "reasonable".

I responded by observing that what you quote from the FAQ is a conditional
statement starting with an "if". Such a statement does not apply whenever
the hypothesis is false.

I also commented, that in reasonable implementations, the proxies are
optimized away. To deal with your contention that there might be an
overhead in using [][] for element access, a much weaker statement would
suffice, namely the existence of implementation that do no incur overhead.

In short, I do not see any "true Scotsman" fallacy in my reasoning.


Now that the fallacy comment is out of the way, I just would like to
reiterate the point that the fear of overhead in [][] over (,) is
unfounded. I provided a reference for a post where I backed up that claim
with empirical data. Of course, such claims and measurements are compiler
specific. I would appreciate if someone could show an optimizing compiler
that makes [][] slower than (,) given the simple implementation from

http://groups.google.com/group/comp...q=Bux+Steinbach+proxy&rnum=1#cecce09e32c2dfc6

   (from FAQ 13.12)
   If you have a decent compiler and if you judiciously use inlining,
   the compiler should optimize away the temporary objects. In other
   words, the operator[]-approach above will hopefully not be slower
   than what it would have been if you had directly called
   Matrix:perator()(unsigned row, unsigned col) in the first place. Of
   course you could have made your life simpler and avoided most of the
   above work by directly calling Matrix:perator()(unsigned row,
   unsigned col) in the first place. So you might as well directly call
   Matrix:perator()(unsigned row, unsigned col) in the first place.

Is there anything in FAQs 13.10-12 that you specifically object to? If
yes, what is it and why?

I did not address the FAQ. I addressed the virtues of proxies. I think that

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

is much more suggestive notation than

row_of( A, i, j, factor );

Only my refutation of your claim that proxies incur an overhead and
therefore should be avoided for simple element access got us into FAQ area,
and I only responded to the part of the FAQ you quoted.

To me the situation looks as follows:

a) proxies provide very useful syntactic sugar for linear algebra.
b) even with very simple minded proxy implementations, [][] is not slower
than (,).

So what would be the reason, not to provide [][]? Please note that I do not
claim that one should not provide (,).


Best

Kai-Uwe Bux

 

[=?ISO-8859-15?Q?Juli=E1n?= Albo]

Now that the fallacy comment is out of the way, I just would like to
reiterate the point that the fear of overhead in [][] over (,) is
unfounded. I provided a reference for a post where I backed up that claim
with empirical data.

By the way, the usage of a class that provides a [ ] [ ] interface
implemented with proxies together with other way without proxies does not
harm even in the case of people with compilers unable to do a good
optimization of the proxies used. They are not forced to use the [ ] [ ]
syntax just because exists.