Allocating a 2D Array Differently

After reading the question asked in this thread, I started wondering "Why not allocate the whole 2D array, including the pointers necessary to navigate the 2D array, at once?" My purpose was to basically create a 2D array that can be created with one call to new and deleted with one call to delete.

Code:

void** Make2DArray(int size, int xMax, int yMax)
{
	void** buffer = (void**)new char[size*xMax*yMax+sizeof(void*)*xMax];
	memset((void*)buffer, 0, size*xMax*yMax+sizeof(void*)*xMax);

	for(int i = 0; i < xMax; i++)
		buffer[i] = &((char*)buffer)[sizeof(void*)*xMax+size*yMax*i];

	return buffer;
}

I started with the creation logic. I needed a buffer with enough space for all of the requested objects AND all of the x-axis pointers. As a diagnostic aid, I went ahead and zeroed out the contents of the buffer. I then needed to wire up x-axis pointers to point at the necessary blocks of memory.

Code:

void Delete2DArray(void** array)
{
	delete[] (char*)array;
}

Because the entire array was created with a single call to new, I should be able to delete it all with a single call to delete. Because the buffer began life as a char array, I figured I should probably cast it back to a char pointer when deleting.

Code:

int main()
{
	const int X_MAX = 20;
	const int Y_MAX = 10;

	int** bigArray = (int**)Make2DArray(sizeof(int),X_MAX,Y_MAX );

	for(int x = 0; x < X_MAX; x++)
		for(int y = 0; y < Y_MAX ; y++)
			bigArray[x][y] = 10;

	Delete2DArray((void**)bigArray);

	return 0;
}

Here's the driver for testing out this memory-thrasher. It blows up while deleting. I'm not exactly sure why. I get the message:
"Windows has triggered a breakpoint in test.exe.

This may be due to a corruption of the heap, and indicates a bug in test.exe or any of the DLLs it has loaded."

I noticed that if I commented out the assignments to bigArray, then the delete worked. I tried tracing through the calls, and it finally blows away on a call to HeapValidate in _CrtIsValidHeapPointer. However, I still don't know why. What rules am I unknowingly breaking?

[EDIT] I forgot to mention that I'm working with VS 2005, in case that makes any difference.
[EDIT2] Added the fix pointed out by ZuK.

Yes you missed something
This should work

Code:

void** Make2DArray(int size, int xMax, int yMax) {
	void** buffer = (void**)new char[size*xMax*yMax+sizeof(void*)*xMax];
	memset((void*)buffer, 0, size*xMax*yMax+sizeof(void*)*xMax);

	for(int i = 0; i < xMax; i++) {
		buffer[i] = &((char*)buffer)[sizeof(void*)*xMax*(i+1)];
	}
	return buffer;
}

Kurt

Wow...thanks for that. Makes sense.

Originally Posted by pianorain

After reading the question asked in this thread, I started wondering "Why not allocate the whole 2D array, including the pointers necessary to navigate the 2D array, at once?" My purpose was to basically create a 2D array that can be created with one call to new and deleted with one call to delete.

Code:

void** Make2DArray(int size, int xMax, int yMax)
{
	void** buffer = (void**)new char[size*xMax*yMax+sizeof(void*)*xMax];
	memset((void*)buffer, 0, size*xMax*yMax+sizeof(void*)*xMax);

	for(int i = 0; i < xMax; i++)
		buffer[i] = &buffer[sizeof(void*)*xMax+size*yMax*i];

	return buffer;
}

That's about as close to being a gratuitous abuse of dynamic memory as you can get without actually being one.

Cheers!

Heh...after I was done, I cringed at the ugliness of it. I'm not sure how usable it is, since all elements still have to be initialized. It was an interesting academic exercise, though.

I agree that it's ugly.
And still wrong. This should do the trick.

Code:

	for(int i = 0; i < xMax; i++) {
		buffer[i] = &((char*)buffer)[sizeof(void*)*xMax + size * yMax*i];
	}

>Heh...after I was done, I cringed at the ugliness of it.
I think it's very pretty, even though I wouldn't let anyone see me write something like it. Then again, when I first stumbled on the trick, I tried to do it with one allocation and one deallocation too, and it wasn't that much different from what you have.

Originally Posted by ZuK

I agree that it's ugly.
And still wrong. This should do the trick.

Aye, I noticed that one. I don't know what I was thinking the first time through.

Another question...is it actually necessary to cast the pointer back to a char* when deleting? Instead of having a Delete2DArray() function, am I breaking any rules by simply doing delete[] bigArray?

Code:

int main()
{
	const int X_MAX = 5;
	const int Y_MAX = 2;

	int** bigArray = (int**)Make2DArray(sizeof(int),X_MAX,Y_MAX );

	for(int x = 0; x < X_MAX; x++)
		for(int y = 0; y < Y_MAX ; y++)
			bigArray[x][y] = 10;

	//Delete2DArray((void**)bigArray); //Maybe I don't need that?
	delete[] bigArray; //Is this okay?

	return 0;
}

>is it actually necessary to cast the pointer back to a char* when deleting?
Nope. operator delete[] takes a pointer to void as its argument anyway, so the cast wouldn't do anything.

That's pretty sweet. I think making it a templated function is the last thing I'm going to do with this piece of code. Now you don't have to pass in the size and all objects are guaranteed to be constructed (as long as they have a parameterless constructor, of course).

Code:

template<class T>
T** Make2DArray(int xMax, int yMax)
{
	T** buffer = (T**)new char[sizeof(T)*xMax*yMax+sizeof(T*)*xMax];

	for(int x = 0; x < xMax; x++)
	{
		buffer[x] = (T*)&((char*)buffer)[sizeof(T*)*xMax+sizeof(T)*yMax*x];
		for(int y = 0; y < yMax; y++)
			buffer[x][y] = T();
	}

	return buffer;
}

Here's a simple driver to illustrate:

Code:

class B
{
public:
	int m_a;
	double m_b;
	char m_c;
	
	B() : m_a(3), m_b(1.6), m_c('X')
	{

	}
};

int main()
{
	const int X_MAX = 5;
	const int Y_MAX = 2;

	B** bigArray = Make2DArray<B>(X_MAX,Y_MAX);
	
	for(int x = 0; x < X_MAX; x++)
		for(int y = 0; y < Y_MAX ; y++)
			cout << "(x,y): " << x << "," << y 
				<< " m_a: " << bigArray[x][y].m_a
				<< " m_b: " << bigArray[x][y].m_b
				<< " m_c: " << bigArray[x][y].m_c << endl;

	delete[] bigArray;

	return 0;
}

[EDIT] The language filter really didn't want to let me make a double pointer of type A.

To use this template with classes is not such a good idea.
No destructors would be called.
Kurt

Aye...good point. Here's my quick attempt at fixing that up.

Code:

template<class T>
T** Make2DArray(int xMax, int yMax)
{
	T** buffer = (T**)new char[sizeof(T)*xMax*yMax+sizeof(T*)*xMax];
	T empty;

	for(int x = 0; x < xMax; x++)
	{
		buffer[x] = (T*)&((char*)buffer)[sizeof(T*)*xMax+sizeof(T)*yMax*x];
		for(int y = 0; y < yMax; y++)
			buffer[x][y] = empty;
	}

	return buffer;
}

template<class T>
void Delete2DArray(T** array, int xMax, int yMax)
{
	for(int x = 0; x < xMax; x++)
		for(int y = 0; y < yMax ; y++)
			array[x][y].~T();

	delete[] array;
}

class B
{
public:
	int m_a;
	double m_b;
	char m_c;
	
	B() : m_a(3), m_b(1.6), m_c('X')
	{

	}

	~B()
	{
		cout << "Destructor called" << endl;
	}
};

int main()
{
	const int X_MAX = 5;
	const int Y_MAX = 2;

	B** bigArray = Make2DArray<A>(X_MAX,Y_MAX);
	
	for(int x = 0; x < X_MAX; x++)
		for(int y = 0; y < Y_MAX ; y++)
			cout << "(x,y): " << x << "," << y 
				<< " m_a: " << bigArray[x][y].m_a
				<< " m_b: " << bigArray[x][y].m_b
				<< " m_c: " << bigArray[x][y].m_c << endl;

	Delete2DArray(bigArray, X_MAX, Y_MAX);

	return 0;
}

That should do it. However, if you're going to be toting around the size of the array, you might as well make it a class.

Here's a class that totes around the bounds for you.

Code:

template<class T>
class TwoDArray
{
private:
	int m_xMax;
	int m_yMax;

	T** m_buffer;
public:
	TwoDArray<T>(int xMax, int yMax) : m_xMax(xMax), m_yMax(yMax)
	{
		m_buffer = (T**)new char[sizeof(T)*xMax*yMax+sizeof(T*)*xMax];
		T empty = T();

		for(int x = 0; x < xMax; x++)
		{
			m_buffer[x] = (T*)&((char*)m_buffer)[sizeof(T*)*xMax+sizeof(T)*yMax*x];
			for(int y = 0; y < yMax; y++)
				m_buffer[x][y] = empty;
		}
	}

	virtual ~TwoDArray<T>()
	{
		for(int x = 0; x < m_xMax; x++)
			for(int y = 0; y < m_yMax ; y++)
				m_buffer[x][y].~T();

		delete[] m_buffer;
	}

	inline T* operator[](int index)
	{
		return m_buffer[index];
	}

	inline int UpperBoundX()
	{
		return m_xMax;
	}

	inline int UpperBoundY()
	{
		return m_yMax;
	}
};

If you use the previously posted class B, you can use this driver to check.

Code:

int main()
{
	const int X_MAX = 5;
	const int Y_MAX = 2;

	TwoDArray<B> bigArray(X_MAX,Y_MAX);

	for(int x = 0; x < X_MAX; x++)
		for(int y = 0; y < Y_MAX ; y++)
			cout << "(x,y): " << x << "," << y 
				<< " m_a: " << bigArray[x][y].m_a
				<< " m_b: " << bigArray[x][y].m_b
				<< " m_c: " << bigArray[x][y].m_c << endl;

	return 0;
}

> m_buffer = (T**)new char[sizeof(T)*xMax*yMax+sizeof(T*)*xMax];
But you're still not calling the constructors for T, and you're still abusing the type system!

// constructor

Code:

m_buffer = new T*[xMax];
T *m_temp = new T[xMax*yMax];
for ( int x = 0 ; x < xMax ; x++, m_temp += yMax ) m_buffer[x] = m_temp;

// destructor

Code:

delete [] m_buffer[0];
delete [] m_buffer;