2D Array

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Jul 30, 2003 at 13:16
template<typename T> class Array2D;

template<typename T>
class Line {
    Array2D<T>* array;
    int x;
public:
    explicit Line(class Array2D<T>* array,int x) : array(array),x(x) {}
    T& operator[](int y);
};

template<typename T>
class Array2D {
    int w,h;
    T* data;
public:
    Array2D() : w(0),h(0),data(0) {}
    ~Array2D() { dealloc(); }
    Array2D(const Array2D& other) : w(other.w),h(other.h),data(new T[w*h]) {
 memcpy(data,other.data,w*h);
    }
    Array2D(int w,int h) {
 alloc(w,h);
    }
    void alloc(int w,int h) {
 data = new T[w*h];
 this->w = w;
 this->h = h;
    }
    void dealloc() {
 delete data, data = 0;
 this->w = 0;
 this->h = 0;
    }
    T& access(int x,int y) {
 return data[x + w*y];
    }
    T* ptr() {
 return data;
    }
    Line<T> operator[](unsigned int x) {
 return Line<T>(this,x);
    }
};

template<typename T> inline T& Line<T>::operator[](int y) {
    return this->array->access(x,y);
}

a demo usage:

struct v2 { int x,y; };
v2 makev2(int x,int y) { v2 v = {x,y}; return v; }

int main() {
    Array2D<v2> array2d;
    array2d.alloc(4,4);
    for(int x=0;x<4;++x) {
 for(int y=0;y<4;++y) {
    array2d[x][y] = makev2(x,y);
 }
    }
    v2* data = array2d.ptr();
    for(int i=0;i<16;++i) {
 std::cout<<"v2["<<i<<"] = ("<<data[i].x<<","<<data[i].y<<")\n";
    }
    return 0;
}

shows that objects with increasing x-position are sitting near eachother in the array…

but i still prefer

T* data = new T[width*height];
data[x + width*y] = ..

:D

anyways. i just tested and it just worked so i just shared:D

21 Replies

Please log in or register to post a reply.

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 30, 2003 at 13:27

just beware of memory leaks…

alloc should call dealloc else you could end up with

Array2D<type> arr;

arr.alloc( x, y);
//later needing to resize
arr.alloc( bigger_x, bigger_y); //oooops just leaked the old memory...

and why not make operator[] just return T* the proxy class doesn’t add anything
beside extra work for the compiler and obscures the usage pattern by actually
switching the alignment from the C standard array[y][x] to array[x][y]
effectivly giving us FORTRAN style arrays (column major instead of row major)

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Jul 30, 2003 at 13:36

that was the plan (as i find c-array order stupid..)

thanks about the memory leak, hehe..

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 30, 2003 at 13:44

@davepermen

that was the plan (as i find c-array order stupid..)

Then it would be good to document that clearly anyone using the array as they would with a normal 2D array would get a huge performance hit due to chache pollution, maybe a clearer and smaller design would be having operator[] work as expected (by me) and have operator()(int x, int y) doing the work of access?

that way you can be explicit about what ordering you really expect and you also lessen the confusion for new users
as a rule of thumb follow the path of least surprise

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Jul 30, 2003 at 13:46

uhm.. nobody polutes the cache in an optimizing system.. if you access by first incrementing x, then incrementing y, you get perfect cachelines..

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Jul 30, 2003 at 13:48

(the thing with the optimizing system i wanted to say is, a good optimizer should remove all overhead.. i’ll see if he really does:D but not today..)

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Jul 30, 2003 at 13:48

500 :D

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 30, 2003 at 13:53

@davepermen

uhm.. nobody polutes the cache in an optimizing system.. if you access by first incrementing x, then incrementing y, you get perfect cachelines..

yes, provided you know that your’e supposed to do it that way, say you have code using a old C-style fixed size 2D array and you just swap in the nice wrapper.

And in a large code base where mixing the two could be common you would quickly
loose track on when to first process rows and then columns and when the otherway
was the natrual way.

What would happen? Your blazing fast code would come to a halt, you would blame OOP and C++, altering the order of access effectivly creates a syntactic disparity
that can only be seen by knowing the type of the array (plain C-style or wrapper)
not by reading the code.

Overloading operator() at least gives a clear distinction that it’s not a POD type
and that if Im not sure of type and behavoir I should probably look it up before
touching it.

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 30, 2003 at 13:54

@davepermen

500 :D

enterirly off-topic but congtratz ;)

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 30, 2003 at 14:13

I would also suggest moving Line inside the Array2D class to preserve the global namespace possibly making it private even though having it publicly availble does also offer some nice opportunities.

Also you should have a look at the copy ctor using memcpy is only safe for POD types you should consider making an explicit loop assigning every elemtn instead

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 30, 2003 at 14:16

or better yet using std::copy like so

Array2D(const Array2D& other) : w(other.w),h(other.h),data(new T[w*h]) 
{
 std::copy( other.data, other.data + w * h, data);
}
4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 30, 2003 at 14:26

You could also manually strength reduce Line by saving a T* and width instead of the array pointer and x, doing that would allow you to have

T& operator[](int y){ return ptr[ w * y];}

instead of

T& operator[](int y){array->access(x, y);}

now this seems quite silly and as if it would buy us nothing but actually
we’re saving one memory access (fetching the data pointer from where ever
the current array is) and todays systems are memory limited so that’s really
a thing to keep in mind.

The drawback with doing this is that it gets risky to save Lines for prelonged periods of time, resizing the array will invalidate all Lines pointing into it, the
current approach don’t have that problem. But anyone that have ever dealt
with STL will have no problems coping with iterators getting invalidated after
resizing.

0684f9d33f52fa189aad7ac9e8c87510
0
baldurk 101 Jul 30, 2003 at 17:53

you know, it’s really a lot nicer-looking if you post everything in one post. Some might even say you’re trying to get your post-count up *whistles* ;).

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 30, 2003 at 20:04

@baldurk

you know, it’s really a lot nicer-looking if you post everything in one post. Some might even say you’re trying to get your post-count up *whistles* ;).

Well actually I think it’s better looking when they’re diffrent replies becuase the deal with slightly diffrent topics making it easier to quote the right passage when replying to my reply…

But sure I can start keeping them togheter as one in the future…

0684f9d33f52fa189aad7ac9e8c87510
0
baldurk 101 Jul 30, 2003 at 20:38

that’s what paragraphs are for.

Sorry, it just annoys me. If it doesn’t annoy anyone else, just ignore me.

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Jul 30, 2003 at 20:44

@baldurk

that’s what paragraphs are for. Sorry, it just annoys me. If it doesn’t annoy anyone else, just ignore me.

Ok, ill use paragraphs the next time.
So do you have any oppinions about the actual thread?

C24eb7e6aaefba78b94c831ddc7b4d0b
0
donBerto 101 Jul 30, 2003 at 21:06

baldurk: sorry ol’ chum

but paragraphs get annoying fast. by having it in separate replies, the reader can digest the little amounts of specific points given.

although I have to admit… 5+ replies by the same person does seem like a shameless plug for posts :lol:

…kidding. wel…

:yes:

C24eb7e6aaefba78b94c831ddc7b4d0b
0
donBerto 101 Jul 31, 2003 at 20:36

davepermen: got some samples of mapping [terminology?]

ex:

vertex<blah, blahblah> something;
something["file.txt"] ...

thanks
:yes:

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Aug 01, 2003 at 06:19

Im guessing that you’re meaning associative containers right?

like std::map and hash maps?
do you wan’t examples of using them or making them?

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Aug 03, 2003 at 20:17

hy, dave is back..

drunkencoder, uhm.. memory access cache polution is STILL not a problem. as you HAVE to use my arrays the “other way around” to get the same behaviour as the original c array anyways. there is no way around it.

never said i like my code.. its merely there to be useful for newbies to see the power and the poverty of c++.. you can do everything you want, if you know how, and what. but 2d arrays in c++ are still done best by doing them 1d..

its just so simple:D

and on a good compiler this code btw really runs optimal.. :D everything gets inline, and unneeded parameter pushpops get thrown out.. so its just a straight memory access..

yep, line could be a subclass of array2d..

i should use std::copy, yes..

4851117d61425bafb6c034e0f595d517
0
DrunkenCoder 101 Aug 04, 2003 at 06:03

memory access cache polution is STILL not a problem. as you HAVE to use my arrays the “other way around” to get the same behaviour as the original c array anyways. there is no way around it.

I never said it was a problem if you used it the way you intend I just said
that it’s contra intuitive and will in most cases thrash the cache for anyone
trying to use it instead of a normal 2D array. Changing access order of arrays
is quite much like making a numberclass where + means - and - means +
sure the class author can make it compute the right things but anyone not
familar with the innerworkings of it will get into trouble with seemingly faulty
results. It’s just one of those design guidelines don’t surprise people with
stuff like this if it’s going to act as a drop in replacement.

never said i like my code.. its merely there to be useful for newbies to see the power and the poverty of c++.. you can do everything you want, if you know how, and what. but 2d arrays in c++ are still done best by doing them 1d..

I never said you said, I just pointed out some obvious flaws and something very
close to abusive design. Im not attacking you or your ability to code Im merly
pointing out issues with the code you posted.

And about the 2D arrays are best done using 1D, yes, but wrapping them makes
them easier and less error prone to use without costing you any performance.
Also it makes it easier to have convinence functions to use STL algorithms,
and I really hope you don’t dynamicly allocate 1D arrays instead of using
std::vector.

yep, line could be a subclass of array2d..

NO! It should be a member class of array2d that’s probably what you ment
but a subclass is a wholy diffrenty entity.

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Aug 04, 2003 at 06:40

memberclass, subclass, bah.. yep, its what i ment..

btw, i NEVER ever used yet a c-style 2d or 3d array! NEVER. thats why i designed it that way. its the way that sounds logically for me:D

actually, when ever i use a dynamic sized array, but not dynamic resizable, i use it directly, no vector..

thats the lowlevel part of my heart beating :D