Allocating a 2D Array Differently

This is a discussion on Allocating a 2D Array Differently within the C++ Programming forums, part of the General Programming Boards category; After reading the question asked in this thread , I started wondering "Why not allocate the whole 2D array, including ...

  1. #1
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399

    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.
    Last edited by pianorain; 12-14-2005 at 01:33 PM.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  2. #2
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    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

  3. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Wow...thanks for that. Makes sense.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    Rabble Rouser Slacker's Avatar
    Join Date
    Dec 2005
    Posts
    116
    Quote 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!

  5. #5
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  6. #6
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    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];
    	}

  7. #7
    Rabble Rouser Slacker's Avatar
    Join Date
    Dec 2005
    Posts
    116
    >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.

  8. #8
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote 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;
    }
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  9. #9
    Rabble Rouser Slacker's Avatar
    Join Date
    Dec 2005
    Posts
    116
    >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.

  10. #10
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    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.
    Last edited by pianorain; 12-14-2005 at 02:11 PM.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  11. #11
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    To use this template with classes is not such a good idea.
    No destructors would be called.
    Kurt

  12. #12
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    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.
    Last edited by pianorain; 12-14-2005 at 03:07 PM.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  13. #13
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    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;
    }
    Last edited by pianorain; 12-14-2005 at 03:23 PM.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  14. #14
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    > 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;

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. cannot print out my 2d array correctly! please help
    By dalearyous in forum C++ Programming
    Replies: 5
    Last Post: 04-10-2006, 02:07 AM
  2. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 08:51 AM
  3. Read file in 2D array
    By Chook in forum C Programming
    Replies: 1
    Last Post: 05-08-2005, 12:39 PM
  4. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  5. Merge sort please
    By vasanth in forum C Programming
    Replies: 2
    Last Post: 11-09-2003, 11:09 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21