Jump to content


2D Array


21 replies to this topic

#1 davepermen

    Senior Member

  • Members
  • PipPipPipPip
  • 1306 posts

Posted 30 July 2003 - 01:16 PM

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
davepermen.net
-Loving a Person is having the wish to see this Person happy, no matter what that means to yourself.
-No matter what it means to myself....

#2 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 30 July 2003 - 01:27 PM

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)

#3 davepermen

    Senior Member

  • Members
  • PipPipPipPip
  • 1306 posts

Posted 30 July 2003 - 01:36 PM

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

thanks about the memory leak, hehe..
davepermen.net
-Loving a Person is having the wish to see this Person happy, no matter what that means to yourself.
-No matter what it means to myself....

#4 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 30 July 2003 - 01:44 PM

davepermen said:

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

#5 davepermen

    Senior Member

  • Members
  • PipPipPipPip
  • 1306 posts

Posted 30 July 2003 - 01:46 PM

uhm.. nobody polutes the cache in an optimizing system.. if you access by first incrementing x, then incrementing y, you get perfect cachelines..
davepermen.net
-Loving a Person is having the wish to see this Person happy, no matter what that means to yourself.
-No matter what it means to myself....

#6 davepermen

    Senior Member

  • Members
  • PipPipPipPip
  • 1306 posts

Posted 30 July 2003 - 01:48 PM

(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..)
davepermen.net
-Loving a Person is having the wish to see this Person happy, no matter what that means to yourself.
-No matter what it means to myself....

#7 davepermen

    Senior Member

  • Members
  • PipPipPipPip
  • 1306 posts

Posted 30 July 2003 - 01:48 PM

500 :D
davepermen.net
-Loving a Person is having the wish to see this Person happy, no matter what that means to yourself.
-No matter what it means to myself....

#8 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 30 July 2003 - 01:53 PM

davepermen said:

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.

#9 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 30 July 2003 - 01:54 PM

davepermen said:

500 :D
enterirly off-topic but congtratz ;)

#10 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 30 July 2003 - 02:13 PM

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

#11 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 30 July 2003 - 02:16 PM

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);
}



#12 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 30 July 2003 - 02:26 PM

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.

#13 baldurk

    Senior Member

  • Members
  • PipPipPipPip
  • 1057 posts

Posted 30 July 2003 - 05:53 PM

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* ;).
baldurk
He who knows not and knows that he knows not is ignorant. Teach him.
He who knows not and knows not that he knows not is a fool. Shun him.

#14 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 30 July 2003 - 08:04 PM

baldurk said:

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...

#15 baldurk

    Senior Member

  • Members
  • PipPipPipPip
  • 1057 posts

Posted 30 July 2003 - 08:38 PM

that's what paragraphs are for.

Sorry, it just annoys me. If it doesn't annoy anyone else, just ignore me.
baldurk
He who knows not and knows that he knows not is ignorant. Teach him.
He who knows not and knows not that he knows not is a fool. Shun him.

#16 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 30 July 2003 - 08:44 PM

baldurk said:

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?

#17 donBerto

    Senior Member

  • Members
  • PipPipPipPip
  • 369 posts

Posted 30 July 2003 - 09:06 PM

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:
Imagine.

#18 donBerto

    Senior Member

  • Members
  • PipPipPipPip
  • 369 posts

Posted 31 July 2003 - 08:36 PM

davepermen: got some samples of mapping [terminology?]

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

thanks
:yes:
Imagine.

#19 DrunkenCoder

    Member

  • Members
  • PipPip
  • 97 posts

Posted 01 August 2003 - 06:19 AM

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?

#20 davepermen

    Senior Member

  • Members
  • PipPipPipPip
  • 1306 posts

Posted 03 August 2003 - 08:17 PM

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..
davepermen.net
-Loving a Person is having the wish to see this Person happy, no matter what that means to yourself.
-No matter what it means to myself....





1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users