2D Dynamic Arrays

[zuwaka]

I'm having troubles with some code. I'm trying to implement a dynamic 2D vector class. I've been working on it for the past weeks, and nothing I've tried worked. I wouldn't mind using pointers if that would be easier.

Here's the code:

#ifndef DYNAMIC_ARRAY_2D_H
#define DYNAMIC_ARRAY_2D_H

#include <vector>

template <class T>
class DynamicArray2D
{
public:
	DynamicArray2D() : numberOfRows(0), numberOfColumns(0), data(NULL)
	{
	}
	T& operator()(int row, int column)
	{
		if (numberOfRows < row)
		{
			numberOfRows = row;
			data.resize(numberOfRows * numberOfColumns);
		}
		else if (numberOfColumns < column)
		{
			numberOfColumns = column;
			data.resize(numberOfRows * numberOfColumns);
		}
		return data[row * numberOfColumns + column];
	}
	T operator()(int row, int column) const
	{		
		if (numberOfRows < row)
		{
			numberOfRows = row;
			data.resize(numberOfRows * numberOfColumns);
		}
		else if (numberOfColumns < column)
		{
			numberOfColumns = column;
			data.resize(numberOfRows * numberOfColumns);
		}
		return data[row * numberOfColumns + column];
	}
private:
	int numberOfRows;
	int numberOfColumns;
	std::vector<T> data;
};

#endif 

[Galik]

You can make 2D vectors like this:

std::vector<std::vector<int> > data(X_SIZE, std::vector<int>(Y_SIZE));

data[2][3] = 6;

[zuwaka]

I wouldn't mind using that, but I need to be able to change the size of the vector/vectors/array/whatever whenever someone calls operator() with an out-of-bounds index.

[Galik]

Well maybe you could base your class around that technique. You can then resize accordingly. Is this a college assignment?

[Disch]

2 things:

first:
DynamicArray2D() : numberOfRows(0), numberOfColumns(0), data(NULL) <- what is that 'data(NULL)' about? I guess that will work in that it will create a vector of size 0, but it just seems a little weird to me XD.

second:
you can't resize the vector from your const () operator because that breaks the constness. You'd either need to make the vector mutable (which I wouldn't recommend), or you have to do something else if an out of bounds element is accessed -- like throw an exception.

EDIT:

1 more thing

Resizing the vector this way might result in its contents being "jumbled" after a resize, since it wouldn't grow in an intuitive way.

For example say you have a 3x2 array:

1 2 3
4 5 6

If you resize to a 4x2 array you'll get the following:

1 2 3 4
5 6 x x

instead of the more intuitive:

1 2 3 x
4 5 6 x

[m4ster r0shi]

It is a good idea to use the vector<vector<T> > approach Galik suggests. This way you'll also avoid the resizing problem Disch pointed out. If you have a 3x2 array and you want to expand it to a 4x3 array, you'll change the size of the outer vector from 3 to 4 and then you'll change the size of each inner vector from 2 to 3.

However, I suggest setting the initial size using a loop, as it's a bit faster:

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

struct MyBigDataBlock
{
    double data[25];
};

const int X_SIZE=1500;
const int Y_SIZE=1500;

int main()
{
    unsigned start, stop, t1, t2;

    //////////////////////////////////////////////////////////////////////////////

    start=clock();
    cout << start << endl;

    vector<vector<MyBigDataBlock> > array1(X_SIZE,vector<MyBigDataBlock>(Y_SIZE));

    stop=clock();
    cout << stop << endl;
    t1=stop-start;

    //////////////////////////////////////////////////////////////////////////////

    start=clock();
    cout << start << endl;

    vector<vector<MyBigDataBlock> > array2;

    array2.resize(X_SIZE);
    //'register' just in case the compiler is not very smart...
    for (register int i=0; i<X_SIZE; i++)
        array2[i].resize(Y_SIZE);

    stop=clock();
    cout << stop << endl;
    t2=stop-start;

    //////////////////////////////////////////////////////////////////////////////

    cout << "\nt1: " << t1 << endl;
    cout << "t2: " << t2 << endl;

    cout << "\nhit enter to quit...";
    cin.get();
    return 0;
}

[zuwaka]

I'm still having troubles. I've implemented a resize() method, but it doesn't seem to work.

Here's the revised code:

#ifndef DYNAMIC_ARRAY_2D_H
#define DYNAMIC_ARRAY_2D_H

#include <vector>
#include <stdexcept>

template <class T>
class DynamicArray2D
{
public:
	DynamicArray2D() : numberOfRows(0), numberOfColumns(0)
	{
	}
	void resize(int row, int column)
	{
		numberOfRows = row;
		numberOfColumns = column;
		data.resize(row);
		for (int i = 0; i < row; ++i)
		{
			data[i].resize(column);
		}
	}
	T& operator()(int row, int column)
	{
		if (numberOfRows < row || numberOfColumns < column)
		{
			throw std::out_of_range("Row or column out-of-range");
		}
		else
		{
			return data[row][column];
		}
	}
	T operator()(int row, int column) const
	{
		if (numberOfRows < row || numberOfColumns < column)
		{
			throw std::out_of_range("Row or column out-of-range");
		}
		else
		{
			return data[row][column];
		}
	}
private:
	int numberOfRows;
	int numberOfColumns;
	std::vector<std::vector<T> > data;
};

#endif 

Is this a college assignment?

No, I'm working on a game engine and wanted it to be easier to use 2D dynamic arrays.

first:
DynamicArray2D() : numberOfRows(0), numberOfColumns(0), [bold]data(NULL)<- what is that 'data(NULL)' about? I guess that will work in that it will create a vector of size 0, but it just seems a little weird to me XD.

That would be from when I was trying to use a pointer to store the data.

[m4ster r0shi]

resize seems to be ok. But this here -> if (numberOfRows < row || numberOfColumns < column)
should be like this -> if (numberOfRows <= row || numberOfColumns <= column)

What are the problems you have?

[m4ster r0shi]

You may also want to do something like this, in order to make your array class compatible with code that uses the typical 2D array syntax. But mind that the compatibility comes at a performance cost.

#include <iostream>
#include <vector>
using namespace std;

template <class T>
class DynamicArray2D
{
private:

    int numberOfRows;
    int numberOfColumns;

    class Row
    {
        friend class DynamicArray2D;

        vector<T> row_data;

    public:

        T & operator[](int i)
        {
            if (row_data.size()<=i) throw(911);
            return row_data[i];
        }
    };

    vector<Row> data;

public:

    DynamicArray2D() : numberOfRows(0), numberOfColumns(0) {}

    void resize(int row, int column)
    {
        numberOfRows = row;
        numberOfColumns = column;

        data.resize(row);

        for (int i = 0; i < row; ++i)
            data[i].row_data.resize(column);
    }

    Row & operator[](int i)
    {
        if (numberOfRows<=i) throw(911);
        return data[i];
    }
};

/////////////////////////////////////////////////////////////

int main()
{
    DynamicArray2D<int> array;

    array.resize(2,3);

    array[0][0]=1;
    cout << array[0][0]<< endl;

    array[1][0]=2;
    cout << array[1][0] << endl;

    array[0][2]=3;
    cout << array[0][2] << endl;

    array[1][1]=4;
    cout << array[1][1] << endl;

    cout << "\nhit enter to quit...";
    cin.get();
    return 0;
}

[zuwaka]

#include <iostream>
#include <vector>
using namespace std;

template <class T>
class DynamicArray2D
{
private:

    int numberOfRows;
    int numberOfColumns;

    class Row
    {
        friend class DynamicArray2D;

        vector<T> row_data;

    public:

        T & operator[](int i)
        {
            if (row_data.size()<=i) throw(911);
            return row_data[i];
        }
    };

    vector<Row> data;

public:

    DynamicArray2D() : numberOfRows(0), numberOfColumns(0) {}

    void resize(int row, int column)
    {
        numberOfRows = row;
        numberOfColumns = column;

        data.resize(row);

        for (int i = 0; i < row; ++i)
            data[i].row_data.resize(column);
    }

    Row & operator[](int i)
    {
        if (numberOfRows<=i) throw(911);
        return data[i];
    }
};

/////////////////////////////////////////////////////////////

int main()
{
    DynamicArray2D<int> array;

    array.resize(2,3);

    array[0][0]=1;
    cout << array[0][0]<< endl;

    array[1][0]=2;
    cout << array[1][0] << endl;

    array[0][2]=3;
    cout << array[0][2] << endl;

    array[1][1]=4;
    cout << array[1][1] << endl;

    cout << "\nhit enter to quit...";
    cin.get();
    return 0;
}

I got it to work with the operator(), but this is giving me a whole bunch of syntax errors.

------ Build started: Project: Dev, Configuration: Debug Win32 ------
Compiling...
Level.cpp
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(24) : error C2143: syntax error : missing ';' before '&'
        c:\documents and settings\shane\desktop\math\dynamicarray2d.h(55) : see reference to class template instantiation 'DynamicArray2D<T>' being compiled
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(24) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(25) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(24) : error C2143: syntax error : missing ';' before '&'
        c:\documents and settings\shane\desktop\math\level.h(27) : see reference to class template instantiation 'DynamicArray2D<T>' being compiled
        with
        [
            T=int
        ]
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(24) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(25) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
main.cpp
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(24) : error C2143: syntax error : missing ';' before '&'
        c:\documents and settings\shane\desktop\math\dynamicarray2d.h(55) : see reference to class template instantiation 'DynamicArray2D<T>' being compiled
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(24) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(25) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(24) : error C2143: syntax error : missing ';' before '&'
        c:\documents and settings\shane\desktop\math\main.cpp(41) : see reference to class template instantiation 'DynamicArray2D<T>' being compiled
        with
        [
            T=int
        ]
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(24) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
c:\documents and settings\shane\desktop\math\dynamicarray2d.h(25) : error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
c:\documents and settings\shane\desktop\math\main.cpp(46) : error C2109: subscript requires array or pointer type
c:\documents and settings\shane\desktop\math\main.cpp(47) : error C2109: subscript requires array or pointer type
Generating Code...
Build log was saved at "file://c:\Documents and Settings\Shane\Desktop\Math\Debug\BuildLog.htm"
Dev - 14 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

[m4ster r0shi]

Honestly, I have no idea why this happens... It compiles fine here (CodeBlocks/gcc).

EDIT: Did you put that and only that in a cpp file and it didn't compile?

[m4ster r0shi]

Are you using Visual Studio?

Check this out -> http://msdn.microsoft.com/en-us/library/ms173696%28VS.80%29.aspx

You can turn C4430 off, I guess that would solve the problem.

[zuwaka]

I tried putting only that into a source file, and it compiles fine.

Edit: I fixed it all up, but I didn't like the way the code was organized and whenever I tried to change the organization the errors cropped up, so I've decided to use my original design for now.

[m4ster r0shi]

zuwaka wrote:

whenever I tried to change the organization the errors cropped up

Separating the definitions from the declarations will help. If you do that, don't forget the inline keyword in the definitions of your [] operators.

[Disch]

*Disch vomits all over this thread*

Creating a new 'Row' type just so you can have foo[y][x] syntax is WRETCHED

*gag*gag*vomit*


*looks up to see that M4ster r0shi actually suggested it*

*becomes confused and lightheaded*

[Galik]

You don't need the Row type to have [x][y] semantics. You get them for free because overloading operator[] returns a reference to std::vector.

[Galik]

zuwaka wrote:

I wouldn't mind using that, but I need to be able to change the size of the vector/vectors/array/whatever whenever someone calls operator() with an out-of-bounds index.

Changing the size on the fly like that can be a bit dangerous because it can mask programming logic errors when you write out of bounds when you don't intend to.

Having said that here is my implementation. Its not heavily tested but it gives you two ways to access your 2D array. Either using the array notation[x][y] which will not do any bounds checking nor will it expand the array. That makes it the fast access way. Else you can use the function method (x, y) which will auto-resize the array as required. Slower and less secure from logic errors:

#include <vector>
#include <iostream>

template<typename T>
class Vector2D
{
private:
	std::vector<std::vector<T> > data;
public:
	Vector2D(size_t x = 0, size_t y = 0): data(x, std::vector<T>(y)){}

	/**
	 * Return the current x dimension
	 */
	size_t xsize() { return data.size(); }

	/**
	 * Return the current y dimension. (Zero if x dimension is zero)
	 */
	size_t ysize() { return data.size() ? data[0].size() : 0; }

	/**
	 * Access the array without expanding. (faster)
	 */
	std::vector<T>& operator[](size_t i) { return data[i]; }

	/**
	 * Access the array expanding its bounds
	 * as required. (slower/less secure)
	 */
	T& operator()(size_t x, size_t y)
	{
		if(y >= ysize())
		{
			for(size_t x(0); x < xsize(); ++x)
			{
				data[x].resize(y + 1);
			}
		}
		if(x >= xsize())
		{
			data.resize(x + 1, std::vector<T>(ysize()));
		}
		return (*this)[x][y];
	}
};

int main()
{
	Vector2D<int> vec(3, 6);

	std::cout << "xsize: " << vec.xsize() << std::endl;
	std::cout << "ysize: " << vec.ysize() << std::endl;

	vec(4, 2) = 3;

	std::cout << "xsize: " << vec.xsize() << std::endl;
	std::cout << "ysize: " << vec.ysize() << std::endl;

	for(size_t y(0); y < vec.ysize(); ++y)
	{
		for(size_t x(0); x < vec.xsize(); ++x)
		{
			std::cout << vec[x][y] << " ";
		}
		std::cout << std::endl;
	}
}

[m4ster r0shi]

Galik wrote:

You don't need the Row type to have [x][y] semantics. You get them for free because overloading operator[] returns a reference to std::vector.

Indeed, but what about the bounds checking?... :/

@Disch:

When you start feeling better, would you mind explaining why is that such a bad idea? :D

[Galik]

m4ster r0shi wrote:

Indeed, but what about the bounds checking?... :/

That's very true. Mind you there is always val = at(x).at(y); for that:

template<typename T>
class Vector2D
{
private:
	std::vector<std::vector<T> > data;
public:
	// .. stuff ...
	/**
	 * Access the array with bounds checking.
	 */
	std::vector<T>& at(size_t i) { return data.at(i); }

	// ... stuff ...
};

EDIT: forgot to put the bounds check in ;o)

[m4ster r0shi]

Ok, allow me to help you understand my point of view.

I haven't written one myself, but I suppose writing a game engine is no trivial task. Especially if this is the OP's first attempt at something like this, maybe many parts have to be rewritten over and over again, as he finds new, better ways to implement his algorithms. It is also highly probable that he wants to test known algorithms found on the internet. And what will the 2D array syntax of these algorithms be? This one -> "array[i][j]". No? And who would want to have to modify the syntax of every algorithm he wants to test with his game engine? I'll tell you who. Nobody.

Furthermore, the bounds checking is necessary in the debug version of his game engine. My guess is the OP doesn't want random crashes caused by heap corruption when he makes games with this (who would?). Now, what is a good way to have both this syntax -> "array[i][j]" and bounds checking??? Maybe there are smarter ways out there, but from the ones shown in this topic, the one I suggested is the only way to achieve this. Isn't it?...

When the OP decides that he doesn't want to make any more changes and he feels ready to build the release version of his game engine, he can just get rid of that stuff and implement his 2D array in the fastest and most unsafe way he can imagine. But if he does that from the beginning, it will most certainly slow down the development of his project considerably.

It doesn't look so bad now, does it, Disch?... :D
Maybe it was something you ate that caused you to feel bad :P