Two Dimensional Array Template

[Noah Roberts]

Peter Olcott wrote

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?

I'll answer that question by asking another....why do you think
std::vector (for example, all of them do) has a "reference_type"
typedef embedded in the class and returns that instead of value_type&
even though they are quite often the same thing?

 

[Simon G Best]

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.

C, maybe, but not C++. *C++ is not C.* Certainly C++ has C-style
arrays, but C++ *does not* constrain or require you to give your own
array classes that C-style kind of interface. So, no, it simply isn't
true that C++ is "defined to work" that way.

(I'm also wondering why you call it a "universal standard" when it's
only /some/ languages that do it that way. In what way is it
"universal"? What do you mean by "universal standard within these ...
languages"?)

Anyway, the idea with C++ is that you generally *don't* do things in
C-style ways. As is so often said, *C++ is not C.* Yes, C++ has
inherited C-style arrays, but you're generally not supposed to use them,
or do things in that style. (If you want to do things that way, there's
already a perfectly good language for it - C.) Instead, you're supposed
to use safer classes, with suitable interfaces. That includes using
operator() for subscripting when that's what's appropriate.

But let me ask you a question. If you use C-style subscripting, with
operator[], to access a whole row, then what do you use to access a
whole column?

Simon

 

[Daniel T.]

That is the specified scope of the problem, within this specified
scope, the solution (as far as I can tell) is perfect.

"Simple 2D array" should be able to handle a 2D array of booleans, but
your class cannot. There is nothing in the definition of "simple 2D
array" that requires a particular memory layout, yet your interface
makes such a requirement.

These are just two ways in which your class is more restrictive than the
specified scope of the problem. Unless you want to change the
specification to "2D array of things other than bools in row major form
with each row laid out in contiguous RAM."

 

[Peter Olcott]

"Simple 2D array" should be able to handle a 2D array of booleans, but
your class cannot. There is nothing in the definition of "simple 2D
array" that requires a particular memory layout, yet your interface
makes such a requirement.

These are just two ways in which your class is more restrictive than the
specified scope of the problem. Unless you want to change the
specification to "2D array of things other than bools in row major form
with each row laid out in contiguous RAM."

Yes, the same as the native code definition, they both seem to work fine with
bool, too.

 

[Gianni Mariani]

How would you improve how resize() is implemented?

Resize should (IMHO) preserve the rows/columns as far as possible

3x3 array
A B C
D E F
G H I

when resized should do:

resize to 2x2 array
A B
D E

resize to 4x4
A B C 0
D E F 0
G H I 0
0 0 0 0

The resize implementation in a previous post does:

resize to 2x2
A B
C D

resize to 4x4
A B C D
E F G H
I 0 0 0
0 0 0 0

Anyhow, if the resize implementation you have works for you, then don't
listen to me. Personally, I wouldn't even provide one until I needed one
since it looks like we're going for the minimal solution anyway.

Also, to placate Daniel T, I would specialize Array2D<bool> like so:

template <>
class Array2D<bool>;

.... and then fill in the blanks whenever you need Array2D<bool>, if ever.

 

[Daniel T.]

Yes, the same as the native code definition,

There is no "native code definition" for 2D arrays. I believe the
standard makes no mention of multi-dimensional arrays at all. (Can
someone back me up on this?)

As the FAQ posits: "Now everybody knows that you are different. You are
clairvoiant with perfect knowledge of the future..." Somehow, you just
know that nobody who uses your class will want to switch to a sparse
array or a column major array. Or maybe you just want to punish them if
they do want to make such a change, because your code will force them to
change every line that uses your class. If you were willing to be more
reasonable, then your users could change out 2DArrays without having to
chanage anything but the point of construction.

they both seem to work fine with bool, too.

The code you posted doesn't work fine with bool.

Assuming a standards conforming compiler, when w_elem_type is a bool,
the op[] function doesn't compile. If your op[] is compiling when
w_elem_type is a bool, your compiler is not standards conforming (or you
are not using the code you posted.)

The reason this is the case is because vector<bool> :perator[] doesn't
return a bool& as your code assumes. You are taking the address of a
temporary and that is simply not allowed.

 

[Gianni Mariani]

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.

OK, so it appears to have changed to what I read a while ago.
Unfortunately the change does not address the issue I raised and why (,)
syntax is not appropriate.

Firstly, the [][] syntax is directly equivalent to the (,) syntax as has
been shown in many prior posts. At this point, much of the impetus
behind the stance of the FAQ is gone.

The biggest reason I stick to [][] is that this IS the native syntax of
the language and hence array[][] (native) or Array2D class will work
almost interchangeably allowing for templates that are appropriate.

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

If "interface separation" is an issue, implement a proxy class. The OP
does not seem to have any need for "interface separation".

I believe this next issue is done to death. This is often rebutted that
a proxy class will significantly detrimentally affect. Do the
benchmark, I think you'll find there is NO difference in performance
between the two approaches. Compilers today do an excellent job of
optimization such that there is no significant difference.

It's purely a syntax issue.

One side of the argument is: "this syntax is better", and the other is:
"don't invent new syntax where none is needed".

I think it's a no brainer personally. Go figure.

 

[Peter Olcott]

Yes, the same as the native code definition,

There is no "native code definition" for 2D arrays. I believe the
standard makes no mention of multi-dimensional arrays at all. (Can
someone back me up on this?)

As the FAQ posits: "Now everybody knows that you are different. You are
clairvoiant with perfect knowledge of the future..." Somehow, you just
know that nobody who uses your class will want to switch to a sparse
array or a column major array. Or maybe you just want to punish them if
they do want to make such a change, because your code will force them to
change every line that uses your class. If you were willing to be more
reasonable, then your users could change out 2DArrays without having to
chanage anything but the point of construction.

they both seem to work fine with bool, too.

The code you posted doesn't work fine with bool.

Assuming a standards conforming compiler, when w_elem_type is a bool,
the op[] function doesn't compile. If your op[] is compiling when
w_elem_type is a bool, your compiler is not standards conforming (or you
are not using the code you posted.)

So what exactly is this issue with this is the official standard for bool, to
make sure no official standard exists? Just make the official standard that a
bool is always implemented as some consistent thing such as char, and with some
consistent value such as one for true, and zero for false. Why did anyone ever
make it more complicated than this?

The reason this is the case is because vector<bool> :perator[] doesn't
return a bool& as your code assumes. You are taking the address of a
temporary and that is simply not allowed.

 

[Peter Olcott]

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.

OK, so it appears to have changed to what I read a while ago. Unfortunately
the change does not address the issue I raised and why (,) syntax is not
appropriate.

Firstly, the [][] syntax is directly equivalent to the (,) syntax as has been
shown in many prior posts. At this point, much of the impetus behind the
stance of the FAQ is gone.

The biggest reason I stick to [][] is that this IS the native syntax of the
language and hence array[][] (native) or Array2D class will work almost
interchangeably allowing for templates that are appropriate.

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

If "interface separation" is an issue, implement a proxy class. The OP does
not seem to have any need for "interface separation".

I believe this next issue is done to death. This is often rebutted that a
proxy class will significantly detrimentally affect. Do the benchmark, I
think you'll find there is NO difference in performance between the two
approaches. Compilers today do an excellent job of optimization such that
there is no significant difference.

It's purely a syntax issue.

One side of the argument is: "this syntax is better", and the other is: "don't
invent new syntax where none is needed".

I think it's a no brainer personally. Go figure.

I still like yours the best. I made sure to give you credit in my source code.

 

[Gianni Mariani]

Peter Olcott wrote:
....

So what exactly is this issue with this is the official standard for bool, to
make sure no official standard exists?

vector<bool> is specialized. It stores bits not bools. the [] operator
on a vector<bool> produces a proxy class that will perform the correct
bitwise operations to set/clear the bits.

 

[Peter Olcott]

Resize should (IMHO) preserve the rows/columns as far as possible

3x3 array
A B C
D E F
G H I

when resized should do:

resize to 2x2 array
A B
D E

resize to 4x4
A B C 0
D E F 0
G H I 0
0 0 0 0

The resize implementation in a previous post does:

resize to 2x2
A B
C D

resize to 4x4
A B C D
E F G H
I 0 0 0
0 0 0 0

Anyhow, if the resize implementation you have works for you, then don't listen
to me. Personally, I wouldn't even provide one until I needed one since it
looks like we're going for the minimal solution anyway.

My main reason for needing this template class was to support searching the
screen using my patented DFA recognizer:
www.SeeScreen.com
I built a screen capture that captures the screen to Array2D Screen; Now each
pixel of (a copy of) the screen can be quickly accessed.

 

[Simon G Best]

Gianni Mariani wrote:
....

If "interface separation" is an issue, implement a proxy class. The OP
does not seem to have any need for "interface separation".

I do like proxy classes

I believe this next issue is done to death. This is often rebutted that
a proxy class will significantly detrimentally affect. Do the
benchmark, I think you'll find there is NO difference in performance
between the two approaches. Compilers today do an excellent job of
optimization such that there is no significant difference.

And I especially like proxy classes when they're done right, so that
things get inlined and optimized all the way down

Simon

 

[Daniel T.]

Also, to placate Daniel T, I would specialize Array2D<bool> like so:

template <>
class Array2D<bool>;

... and then fill in the blanks whenever you need Array2D<bool>, if ever.

Can that be done? The code posted assumes that any portion of the vector
can be converted into an array of pointers. How would you change the
implementation when that is not the case? Once you come up with the
change, why does the primary implementation use something different?

(BTW, I'm not being rhetorical with these questions. I really want to
know the answer.)

 

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

So what exactly is this issue with this is the official standard for bool,
to make sure no official standard exists? Just make the official standard
that a bool is always implemented as some consistent thing such as char,
and with some consistent value such as one for true, and zero for false.

Just change the standard to avoid that you have to learn and think.

 

[Simon G Best]

So what exactly is this issue with this is the official standard for bool, to
make sure no official standard exists?
Uh?

Just make the official standard that a
bool is always implemented as some consistent thing such as char, and with some
consistent value such as one for true, and zero for false. Why did anyone ever
make it more complicated than this?

It's so that space can be saved. A bool can be represented by a single
bit, but the smallest addressable unit of storage is a char - at least
eight bits. So, it's either one bool per char (wastes space), or
internally representing the bools in such a way that they can't be
individually referenced using built-in reference types (such as char &
or bool &). So that space need not be wasted, the standard has
std::vector<bool> specialized so that built-in reference types aren't
used. This means as many bools can be stored in a char (or whatever) as
possible, saving space.

Simon

 

[Noah Roberts]

It's so that space can be saved. A bool can be represented by a single
bit, but the smallest addressable unit of storage is a char - at least
eight bits. So, it's either one bool per char (wastes space), or
internally representing the bools in such a way that they can't be
individually referenced using built-in reference types (such as char &
or bool &). So that space need not be wasted, the standard has
std::vector<bool> specialized so that built-in reference types aren't
used. This means as many bools can be stored in a char (or whatever) as
possible, saving space.

At a pretty significant cost though. vector<bool> is not a container.
It kind of throws the whole thing off. Better to use bitset instead.

 

[Simon G Best]

My main reason for needing this template class was to support searching the
screen using my patented DFA recognizer:
www.SeeScreen.com

Oh, no. You're an inventor with a software patent :-(

Simon

 

[Daniel T.]

OK, so it appears to have changed to what I read a while ago.
Unfortunately the change does not address the issue I raised and why
(,) syntax is not appropriate.

Don't get so hung up on syntax.

Firstly, the [][] syntax is directly equivalent to the (,) syntax as
has been shown in many prior posts.

Actually it isn't. If it were, then I wouldn't bother suggesting to use
it over [][]. The (,) syntax is much more flexable than the [][] syntax.
It allows users to make more drastic changes to the way their code is
implemented with fewer changes to the actual text of the code.

The biggest reason I stick to [][] is that this IS the native syntax
of the language and hence array[][] (native) or Array2D class will
work almost interchangeably allowing for templates that are
appropriate.

As the FAQ mentions, if you "find yourself maintaining a billion-line
app where the original team used m[j]" things are different, but that
isn't a justification for starting a new project or library with such a
construct. Especially considering that more flexible constructs are
available that are "never worse than, and sometimes better than, the
[][] approach."

It's purely a syntax issue.

As mentioned in the FAQ, "there are easy performance tuning tricks that
can be done with the operator() approach that are more difficult in the
[][] approach." This is not merely a syntax issue.

One side of the argument is: "this syntax is better", and the other
is: "don't invent new syntax where none is needed".

No, one side of the argument is; don't box yourself in before the
project has really gotten started by exposing an implementation detail
that may not even be approprate.

On the other side is your argumentum ad antiquitatem fallacy. As the FAQ
says, "The world already has way too many exposed data structures and
way too many out-of-bounds parameters, and those cost way too much money
and cause way too many delays and way too many defects."

I think it's a no brainer personally. Go figure.

Now there, I can agree with you.

 

[Gianni Mariani]

Can that be done? The code posted assumes that any portion of the vector
can be converted into an array of pointers. How would you change the
implementation when that is not the case?

Apart from vector<bool>, this IS the C++ standard for std::vector. As
for Array2D<T>, I suppose you can return a proxy that gens a
std::vector<T>::reference_type instead of a pointer and there would be

... Once you come up with the
change, why does the primary implementation use something different?

I would not necessarily do anything different.

 

[Gianni Mariani]

OK, so it appears to have changed to what I read a while ago.
Unfortunately the change does not address the issue I raised and why
(,) syntax is not appropriate.

Don't get so hung up on syntax.

Firstly, the [][] syntax is directly equivalent to the (,) syntax as
has been shown in many prior posts.

Actually it isn't.

I can show an implementation of [][] that calls call your (,) and most
compilers will optimize it so there is nothing different between calling
(,) or [][].

No issue with flexibility with optimizations here since it is calling
your (,) ! right ?

The FAQ is guilty of being a proponent of inventing a new syntax where
none in needed IMHO.

Now, if I create a bunch o 2D array templates, they will work fine with
both the new Array2D or a native 2D array. Do that with the (,) syntax!


It's just easier all the way around.