[how to] Dynamic 2D array

Several different methods.

Trivial way is to allocate an array of pointers, and have them point to arrays. First [] deference takes you from a ** to a *, second deference gets your value.

Efficient way is to allocate a single array and supply an array-mapping-function, which in C++ is typically an overloaded operator() (can''t use [] because it can only take one parameter, () can take any number).

You could also overload operator[] and return a proxy object with another overloaded operator[]. This would work, but would require a very good optimizing compiler to make the output code efficient (e.g. MSVC or gcc 3.2+)


Last, I''m pretty sure boost has a mutli-array template.

- Magmai Kai Holmlor

"No, his mind is not for rent to any god nor government" - Rush, Tom Sawyer

[Look for information | GDNet Start Here | GDNet Search Tool | GDNet FAQ | MSDN RTF[L] | SGI STL Docs | STFW | Asking Smart Questions ]

[Free C++ Libraries | Boost | ACE | Loki | MTL | Blitz++ | wxWindows| Spirit(xBNF)]
[Free C Libraries | zlib ]

A 2D array is really an array of arrays. Since it''s dynamic we should use a pointer.

int** array;

Now you have to decide the size of the arrays. If you want them all the same size then simply:
array = new int[num_arrays][size_arrays];

That will create num_arrays arrays of size size_arrays. If you want them to be diffetrent sizes then you just have to declare them 1 at a time.

array = new int*[num_arrays];
for(int i = 0; i < num_arrays; i++)
array = new int[array_size];

And accessing is easy enough.
array[array_num][element_num];

quote:

---

Original post by Cherez
A 2D array is really an array of arrays.

---

Not in C++.

quote:

---

Now you have to decide the size of the arrays. If you want them all the same size then simply:
array = new int[num_arrays][size_arrays];

---

This is illegal in C++ too. Try it. operator new can only allocate a single dimension.

Read Magmai''s comments above. Also, using i for indexing on these forums is a bad idea because when subscripted it gets interpreted as a forum shortcut for italicized text. Either use another letter or place your code within source tags (or space the subscription out like so: [ i ]).

Definitely illegal. Here''s what I typed in:

int num_arrays = 0;
int size_arrays = 0;

cin >> num_arrays;
cin >> size_arrays;

int** array;

array = new int[num_arrays][size_arrays]; //error C2540 here


And here''s the error messege:

error C2540: non-constant expression as array bound.

Cherez was on the right track. A 2d dynamically allocated array in C++ is, in fact, an array of arrays. This should work, I've used it fairly often:

int **array;
array = new int[arrayWidth];

for (int j = 0; j < arrayWidth; j++)
    array[j] = new int[arrayHeight];     

To access use array[x][y]
And for deletion:

for (int j = 0; j < arrayWidth; j++)
    delete [] array[j];

delete [] array;     

Magmai Kai Holmlor's suggestion of using an array-mapping function is also one I've tried and found worked well.

[edited by - glassJAw on June 3, 2003 12:51:41 PM]

Here use this.

#ifndef ARRAY2D_INCLUDED
#define ARRAY2D_INCLUDED

#include <algorithm>

template <typename T>
class cArray2D
{
	T *m_pData;
	T **m_pRows;
	int m_iRows;
	int m_iColumns;


//no copy && assign

	cArray2D(const cArray2D&);
	cArray2D& operator=(const cArray2D&);

public:
	cArray2D(void):
		m_pData(0), m_pRows(0), m_iRows(0), m_iColumns(0)
	{}

	cArray2D(int iRows, int iCols):
		m_iRows(iRows), m_iColumns(iCols)
	{
		m_pData = new T[iRows * iCols];
		m_pRows = new T*[iRows];
		for(int i = 0; i < iRows; ++i)
			m_pRows[i] = m_pData + i * iRows;
	}

	~cArray2D(void)
	{
		delete [] m_pData;
		delete [] m_pRows;
	}

	T* operator[](int i){ return m_pRows[i];}
	const T* operator[](int i) const { return m_pRows[i];}
	int rows(void) const { return m_iRows;}
	int columns(void) const { return m_iColumns;}
	void swap(cArray2D& that)
	{
		std::swap(m_pData, that.m_pData);
		std::swap(m_pRows, that.m_pRows);
		std::swap(m_iRows, that.m_iRows);
		std::swap(m_iColumns, that.m_iColumns);
	}
	
	void resize(int iRows, int iCols)
	{
		cArray2D arr( iRows, iCols);
		iRows = std::min( iRows, rows());
    	iCols = std::min( iCols, columns());
  		while(iRows--)
     		for(int iX = 0; iX < iCols; ++iX)
  				arr[ iRows][ iX] = (*this)[ iRows][ iX];
  		swap( arr);
	}

};

#endif

Ok, some people will probably call me stupid for this implementation but it do have some really nice points.

+ it lessens memory fragmentation
+ it plays nice with the cache

the drawback being
- neglible overhead of sizeof( pointer) * rows;

I usually declare an array (single dimension) and then I provide a mapping from 2D to 1D. For example:

#define Index(x,y) (((x)-1)*dimx+(y)-1)

int * array2D=new int[dimx*dimy];

for (int x=0;x<dimx;x++)
    for (int y=0;y<dimy;y++)
        array2D[Index(x,y)]=0;

delete [] array2D;

This way, I can't forget to call the macro "Index" because array2D is, in fact, a single dimension array and I know I want to use two indexes.

I hope to be helpful.
Bye.

Fil (il genio)

[edited by - fil on June 3, 2003 1:23:58 PM]

[edited by - fil on June 3, 2003 1:24:47 PM]

[edited by - fil on June 3, 2003 1:27:23 PM]