Dynamic array advice.

[JoeC]

I am crating a new version of my map game and my map will be a 2d
array. I had problems trying to create a 2d array dynamically, in
fact C++ won't let me do it. My question is how to create the size of
array I need at run time without using too much memory or going over
the allotted size if I choose to use this object for a different
game.

One idea I have is to create space * spaces = new space[len*with];
then have all my accessors just convert x and y to:

void place(int x, int y){spaces[x*len+y;}

 

[John Harrison]

I am crating a new version of my map game and my map will be a 2d
array. I had problems trying to create a 2d array dynamically, in
fact C++ won't let me do it. My question is how to create the size of
array I need at run time without using too much memory or going over
the allotted size if I choose to use this object for a different
game.

One idea I have is to create space * spaces = new space[len*with];
then have all my accessors just convert x and y to:

void place(int x, int y){spaces[x*len+y;}

That would work. There are other lots of other approaches.

The classic is (and simplest) to use double pointers

space** spaces = new space*[width];
for (int i = 0; i < width; ++i)
spaces = new space[length];

then you can just say

space[j] = whatever;

and when you want to free the memory, do the reverse

for (int i = 0; i < width; ++i)
delete[] spaces;
delete[] spaces;

john

 

[Kai-Uwe Bux]

I am crating a new version of my map game and my map will be a 2d
array. I had problems trying to create a 2d array dynamically, in
fact C++ won't let me do it. My question is how to create the size of
array I need at run time without using too much memory or going over
the allotted size if I choose to use this object for a different
game.

One idea I have is to create space * spaces = new space[len*with];
then have all my accessors just convert x and y to:

void place(int x, int y){spaces[x*len+y;}

You might want to put that into a class with an overloaded operator():

int & operator( std::size_t row, std::size_t col ) {
return ( the_data [ col_size * row + col ] );
}

and you could add a const version too:

int const & operator( std::size_t row, std::size_t col ) const {
return ( the_data [ col_size * row + col ] );
}

You also might make the member the_data a std::vector<int>. In that case,
you would not even have to take care of your own assignment operator, copy
constructor and destructor. E.g:. [code not tested/compiled]

template <typename T>
class array2d {

std::size_t the_row_size;
std::size_t the_col_size;
std::vector<T> the_data;

public:

array2d ( std::size_t r, std::size_t c, T const & val = T() )
: the_row_size ( r )
, the_col_size ( c )
, the_data ( the_row_size * the_col_size, val )
{}

T & operator( std::size_t row, std::size_t col ) {
return ( the_data [ the_col_size * row + col ] );
}

T const & operator( std::size_t row, std::size_t col ) const {
return ( the_data [ the_col_size * row + col ] );
}

std::size_t row_size ( void ) const {
return ( the_row_size );
}

std::size_t col_size ( void ) const {
return ( the_col_size );
}

};

That would work. There are other lots of other approaches.

The classic is (and simplest) to use double pointers

space** spaces = new space*[width];
for (int i = 0; i < width; ++i)
spaces = new space[length];

then you can just say

space[j] = whatever;

and when you want to free the memory, do the reverse

for (int i = 0; i < width; ++i)
delete[] spaces;
delete[] spaces;

I doubt that this is the _simplest_ approach. Once you want an exception
safe version, you will find that it is not that simple at all. Any new in
the for-loop might throw. In order not to leak, you need to keep track of
that and delete the previously allocated rows. The idea of the OP is much
easier to implement properly.


Best

Kai-Uwe Bux

 

[Doyle Rhynard]

I am crating a new version of my map game and my map will be a 2d

array. I had problems trying to create a 2d array dynamically, in
fact C++ won't let me do it. My question is how to create the size of
array I need at run time without using too much memory or going over
the allotted size if I choose to use this object for a different
game.

One idea I have is to create space * spaces = new space[len*with];
then have all my accessors just convert x and y to:

void place(int x, int y){spaces[x*len+y;}

I am getting rather tired of complaints about not being able to do 2-D arrays.

Here is a multidimensional array class derived from std::vector that I wrote and
have used for many years. It is not optimal, but is close enough for all but the
most time intensive programs.

If this not sufficient, the I would suggest using the Boost::multiarray.


//======================== Array.h ===============================

#ifndef GPD_Array_H
#define GPD_Array_H

//**** Includes ****
#include <vector>
#include <cstdlib>
#include <cstdarg>


//**** Uses ****
using std::vector;


namespace GPD {

template<typename T_, int ND> class ArrayBase: public vector<T_> {
public:// Defs
typedef typename vector<T_>::iterator IterArr;

public:// Uses
using vector<T_>::begin;
using vector<T_>::end;
using vector<T_>::size;

public:// Constructors
ArrayBase(): vector<T_>() {}
ArrayBase(int Len): vector<T_>(Len) {}
ArrayBase(const ArrayBase& a): vector<T_>(a) {(*this) = a;}

public:// Destructor
virtual ~ArrayBase() {}

public:// Functions
int Dim(int N) const {return int(dim[N]);}
ArrayBase& operator=(const ArrayBase& a) {
vector<T_>:perator=(a);
copy(&a.dim[0], &a.dim[ND], &dim[0]);
copy(&a.sizeDim[0], &a.sizeDim[ND], &sizeDim[0]);
iData = begin();
return (*this);
}

protected:// Variables
size_t dim[ND];
size_t sizeDim[ND];
IterArr iData;
};

template<typename T_, int ND> class SubArr {
private:// Defs
typedef typename ArrayBase<T_, ND>::iterator IterArr;

public:// Constructors
SubArr<T_, ND>(const IterArr IStart, const size_t* ArrSizeDim):
sizeDim(ArrSizeDim), iElem(IStart) {}

public:// Functions
SubArr<T_, ND-1> operator[](size_t K) const {
return SubArr<T_, ND-1>((iElem+K*sizeDim[0]),
(sizeDim+1));
}
private:// Variables
const size_t* sizeDim;
IterArr iElem;
};


template<typename T_> class SubArr<T_, 1> {
private:// Defs
typedef typename ArrayBase<T_, 1>::iterator IterArr;

public:// Constructors
SubArr(const IterArr IStart, const size_t* ArrSizeDim):
sizeDim(ArrSizeDim), iElem(IStart) {}

public:// Functions
T_& operator[](size_t K) const {return (*(iElem+K));}

private:// Variables
const size_t* sizeDim;
IterArr iElem;
};


template<typename T_, int ND=1> class Array: public ArrayBase<T_, ND> {
public:// Defs
typedef typename Array<T_, ND>::iterator IterArr;

public:// Uses
using vector<T_>::begin;
using vector<T_>::end;
using vector<T_>::size;
using ArrayBase<T_, ND>::sizeDim;
using ArrayBase<T_, ND>::dim;
using ArrayBase<T_, ND>::iData;

public:// Constructors
Array<T_, ND>(): ArrayBase<T_, ND>() {}
Array<T_, ND>(const Array<T_, ND>& a): ArrayBase<T_, ND>(a) {}
Array<T_, ND>(size_t D1, ...) {
// Initialize array dimensions and compute total array size
va_list ListDims;
va_start(ListDims, D1);
sizeDim[0] = 1;
for (int N = 0; N < ND; N++) {
dim[N] = (N ? va_arg(ListDims, int) : D1);
sizeDim[0] *= dim[N];
}
va_end(ListDims);

// Initialize array subspace sizes
for (int N = 1; N < ND; N++) {
sizeDim[N] = sizeDim[N-1] / dim[N-1];
}

// Allocate memory for data array
resize(sizeDim[0]);
iData = begin();
}

public:// Functions
void clear() const {return vector<T_>::clear();}
int Size() const {return int(size());}

void Resize(size_t D1, ...) {
// Initialize array dimensions and compute total size
va_list ListDims;
va_start(ListDims, D1);
sizeDim[0] = 1;
for (int N = 0; N < ND; N++) {
dim[N] = (N ? va_arg(ListDims, int) : D1);
sizeDim[0] *= dim[N];
}
va_end(ListDims);

// Initialize array subspace sizes
for (int N = 1; N < ND; N++) {
sizeDim[N] = sizeDim[N-1] / dim[N-1];
}

// Allocate memory for data array
resize(sizeDim[0]);
iData = begin();
}

void Clear() {
clear();
for (int N = 1; N < ND; N++) {
sizeDim[N] = 0;
}
}

void Fill(const T_& val) {
for (IterArr IT = begin(); IT < end(); IT++) {
(*IT) = val;
}
}

public:// Functions
SubArr<T_, ND-1> operator[](size_t K) const {
return SubArr<T_, ND-1>((iData+K*sizeDim[1]),
(sizeDim+2));
}
};


template<typename T_> class Array<T_, 1>: public ArrayBase<T_, 1> {
public:// Constructors
Array(): ArrayBase<T_, 1>() {}
Array(size_t Len): ArrayBase<T_, 1>(Len) {}
Array(const ArrayBase<T_, 1>& a): ArrayBase<T_, 1>(a) {}
};

}

#endif


//======================== Test Program ===============================

//**** Includes****
#include "Array.h"
#include <iostream>


//**** Uses ****
using std::cout;
using std::endl;
using GPD::Array;


int main() {
cout << "Start Array Test: " << endl;
Array<float,3> a(3,2,5);
for (int N0 = 0; N0 < a.Dim(0); N0++) {
for (int N1 = 0; N1 < a.Dim(1); N1++) {
for (int N2 = 0; N2 < a.Dim(2); N2++) {
a[N0][N1][N2] = 100*(N0+1) + 10*(N1+1) + (N2+1);
cout << a[N0][N1][N2] << endl;
}
}
}
return 0;
}

 

[JoeC]

I am crating a new version of my map game and my map will be a 2d
array. I had problems trying to create a 2d array dynamically, in
fact C++ won't let me do it. My question is how to create the size of
array I need at run time without using too much memory or going over
the allotted size if I choose to use this object for a different
game.

One idea I have is to create space * spaces = new space[len*with];
then have all my accessors just convert x and y to:

void place(int x, int y){spaces[x*len+y;}

That would work. There are other lots of other approaches.

The classic is (and simplest) to use double pointers

space** spaces = new space*[width];
for (int i = 0; i < width; ++i)
spaces = new space[length];

then you can just say

space[j] = whatever;

and when you want to free the memory, do the reverse

for (int i = 0; i < width; ++i)
delete[] spaces;
delete[] spaces;

john

Thanks I never thought of that or seen that as an example. I will see
if my way works but thanks for idea.

 

[Gavin Deane]

//======================== Array.h ===============================

#ifndef GPD_Array_H
#define GPD_Array_H

//**** Includes ****
#include <vector>
#include <cstdlib>
#include <cstdarg>

//**** Uses ****
using std::vector;

That's not a good thing to have in the header. Remove it and fully
qualify vector (i.e. type std::vector) throughout the header.

//======================== Test Program ===============================

//**** Includes****
#include "Array.h"

With your header above, your program (and the OP's program if he uses
your code, and every other program that ever uses your code) now has
using std::vector forced upon it. That entirely defeats the purpose of
vector being in the std namespace. Using declarations and directives
have pros and cons that must be considered on a case by case basis. To
have the decision forced upon you, particularly by a such a generic
concept as a multi-dimensional array that has potential uses far
beyond the program it was originally created for, is a Bad Thing. And
it can easily be avoided by the one-off cost of a little extra typing
up front by fully qualifying the names in the header.

Gavin Deane

 

[red floyd]

I am crating a new version of my map game and my map will be a 2d
array. I had problems trying to create a 2d array dynamically, in
fact C++ won't let me do it. My question is how to create the size of
array I need at run time without using too much memory or going over
the allotted size if I choose to use this object for a different
game.

One idea I have is to create space * spaces = new space[len*with];
then have all my accessors just convert x and y to:

void place(int x, int y){spaces[x*len+y;}

You might want to put that into a class with an overloaded operator():

int & operator( std::size_t row, std::size_t col ) {
return ( the_data [ col_size * row + col ] );
}

and you could add a const version too:

int const & operator( std::size_t row, std::size_t col ) const {
return ( the_data [ col_size * row + col ] );
}

You also might make the member the_data a std::vector<int>. In that case,
you would not even have to take care of your own assignment operator, copy
constructor and destructor. E.g:. [code not tested/compiled]

template <typename T>
class array2d {

std::size_t the_row_size;
std::size_t the_col_size;
std::vector<T> the_data;

public:

array2d ( std::size_t r, std::size_t c, T const & val = T() )
: the_row_size ( r )
, the_col_size ( c )
, the_data ( the_row_size * the_col_size, val )
{}

T & operator( std::size_t row, std::size_t col ) {
return ( the_data [ the_col_size * row + col ] );
}

T const & operator( std::size_t row, std::size_t col ) const {
return ( the_data [ the_col_size * row + col ] );
}

std::size_t row_size ( void ) const {
return ( the_row_size );
}

std::size_t col_size ( void ) const {
return ( the_col_size );
}

};

Kai, you missed a pair of parens on both.

T& operator()( std::size_t row, std::size_t col );
T const & operator()( std::size_t row, std::size_t col ) const;

 

[Ross A. Finlayson]

JoeC wrote:
I am crating a new version of my map game and my map will be a 2d
array. I had problems trying to create a 2d array dynamically, in
fact C++ won't let me do it. My question is how to create the size of
array I need at run time without using too much memory or going over
the allotted size if I choose to use this object for a different
game.

One idea I have is to create space * spaces = new space[len*with];
then have all my accessors just convert x and y to:

void place(int x, int y){spaces[x*len+y;}

You might want to put that into a class with an overloaded operator():

int & operator( std::size_t row, std::size_t col ) {
return ( the_data [ col_size * row + col ] );
}

and you could add a const version too:

int const & operator( std::size_t row, std::size_t col ) const {
return ( the_data [ col_size * row + col ] );
}

You also might make the member the_data a std::vector<int>. In that case,
you would not even have to take care of your own assignment operator, copy
constructor and destructor. E.g:. [code not tested/compiled]

template <typename T>
class array2d {

std::size_t the_row_size;
std::size_t the_col_size;
std::vector<T> the_data;

public:

array2d ( std::size_t r, std::size_t c, T const & val = T() )
: the_row_size ( r )
, the_col_size ( c )
, the_data ( the_row_size * the_col_size, val )
{}

T & operator( std::size_t row, std::size_t col ) {
return ( the_data [ the_col_size * row + col ] );
}

T const & operator( std::size_t row, std::size_t col ) const {
return ( the_data [ the_col_size * row + col ] );
}

std::size_t row_size ( void ) const {
return ( the_row_size );
}

std::size_t col_size ( void ) const {
return ( the_col_size );
}

};

Kai, you missed a pair of parens on both.

T& operator()( std::size_t row, std::size_t col );
T const & operator()( std::size_t row, std::size_t col ) const;

Should you just use the valarray and slices and gslices?

I wonder.

Ross

 

[Kai-Uwe Bux]

JoeC wrote:
I am crating a new version of my map game and my map will be a 2d
array. I had problems trying to create a 2d array dynamically, in
fact C++ won't let me do it. My question is how to create the size of
array I need at run time without using too much memory or going over
the allotted size if I choose to use this object for a different
game.

One idea I have is to create space * spaces = new space[len*with];
then have all my accessors just convert x and y to:

void place(int x, int y){spaces[x*len+y;}

You might want to put that into a class with an overloaded operator():

int & operator( std::size_t row, std::size_t col ) {
return ( the_data [ col_size * row + col ] );
}

and you could add a const version too:

int const & operator( std::size_t row, std::size_t col ) const {
return ( the_data [ col_size * row + col ] );
}

You also might make the member the_data a std::vector<int>. In that case,
you would not even have to take care of your own assignment operator,
copy constructor and destructor. E.g:. [code not tested/compiled]

template <typename T>
class array2d {

std::size_t the_row_size;
std::size_t the_col_size;
std::vector<T> the_data;

public:

array2d ( std::size_t r, std::size_t c, T const & val = T() )
: the_row_size ( r )
, the_col_size ( c )
, the_data ( the_row_size * the_col_size, val )
{}

T & operator( std::size_t row, std::size_t col ) {
return ( the_data [ the_col_size * row + col ] );
}

T const & operator( std::size_t row, std::size_t col ) const {
return ( the_data [ the_col_size * row + col ] );
}

std::size_t row_size ( void ) const {
return ( the_row_size );
}

std::size_t col_size ( void ) const {
return ( the_col_size );
}

};

Kai, you missed a pair of parens on both.

T& operator()( std::size_t row, std::size_t col );
T const & operator()( std::size_t row, std::size_t col ) const;

Oops, thanks.

I also missed the asserts that should be there:

T & operator() ( std::size_t row, std::size_t col ) {
assert( row < row_size() );
assert( col < col_size() );
return ( the_data [ the_col_size * row + col ] );
}

T const & operator() ( std::size_t row, std::size_t col ) const {
assert( row < row_size() );
assert( col < col_size() );
return ( the_data [ the_col_size * row + col ] );
}

And, of course, there should be some typedefs like value_type, reference,
const_reference, size_type. So what about:

struct array2d {

typedef typename std::vector<T>::size_type size_type;
typedef typename std::vector<T>::value_type value_type;
typedef typename std::vector<T>::reference reference;
typedef typename std::vector<T>::const_reference const_reference;

private:

size_type the_row_size;
size_type the_col_size;
std::vector<T> the_data;

size_type pos ( size_type row, size_type col ) {
assert( row < row_size() );
assert( col < col_size() );
return ( the_col_size * row + col );
}

public:

array2d ( size_type r, size_type c, const_reference val = T() )
: the_row_size ( r )
, the_col_size ( c )
, the_data ( the_row_size * the_col_size, val )
{
assert( the_row_size < size_type(-1) / the_col_size );
}

reference operator() ( size_type row, size_type col ) {
return ( the_data [ pos( row, col ) ] );
}

const_reference operator() ( size_type row, size_type col ) const {
return ( the_data [ pos( row, col ) ] );
}

size_type row_size ( void ) const {
return ( the_row_size );
}

size_type col_size ( void ) const {
return ( the_col_size );
}

};

The assert in the constructor is a little too strict.


Best

Kai-Uwe Bux

 

[JoeC]

I am crating a new version of my map game and my map will be a 2d
array. I had problems trying to create a 2d array dynamically, in
fact C++ won't let me do it. My question is how to create the size of
array I need at run time without using too much memory or going over
the allotted size if I choose to use this object for a different
game.

One idea I have is to create space * spaces = new space[len*with];
then have all my accessors just convert x and y to:

void place(int x, int y){spaces[x*len+y;}

I am getting rather tired of complaints about not being able to do 2-D arrays.

Here is a multidimensional array class derived from std::vector that I wrote and
have used for many years. It is not optimal, but is close enough for all but the
most time intensive programs.

If this not sufficient, the I would suggest using the Boost::multiarray.

//======================== Array.h ===============================

#ifndef GPD_Array_H
#define GPD_Array_H

//**** Includes ****
#include <vector>
#include <cstdlib>
#include <cstdarg>

//**** Uses ****
using std::vector;

namespace GPD {

template<typename T_, int ND> class ArrayBase: public vector<T_> {
public:// Defs
typedef typename vector<T_>::iterator IterArr;

public:// Uses
using vector<T_>::begin;
using vector<T_>::end;
using vector<T_>::size;

public:// Constructors
ArrayBase(): vector<T_>() {}
ArrayBase(int Len): vector<T_>(Len) {}
ArrayBase(const ArrayBase& a): vector<T_>(a) {(*this) = a;}

public:// Destructor
virtual ~ArrayBase() {}

public:// Functions
int Dim(int N) const {return int(dim[N]);}
ArrayBase& operator=(const ArrayBase& a) {
vector<T_>:perator=(a);
copy(&a.dim[0], &a.dim[ND], &dim[0]);
copy(&a.sizeDim[0], &a.sizeDim[ND], &sizeDim[0]);
iData = begin();
return (*this);
}

protected:// Variables
size_t dim[ND];
size_t sizeDim[ND];
IterArr iData;
};

template<typename T_, int ND> class SubArr {
private:// Defs
typedef typename ArrayBase<T_, ND>::iterator IterArr;

public:// Constructors
SubArr<T_, ND>(const IterArr IStart, const size_t* ArrSizeDim):
sizeDim(ArrSizeDim), iElem(IStart) {}

public:// Functions
SubArr<T_, ND-1> operator[](size_t K) const {
return SubArr<T_, ND-1>((iElem+K*sizeDim[0]),
(sizeDim+1));
}
private:// Variables
const size_t* sizeDim;
IterArr iElem;
};

template<typename T_> class SubArr<T_, 1> {
private:// Defs
typedef typename ArrayBase<T_, 1>::iterator IterArr;

public:// Constructors
SubArr(const IterArr IStart, const size_t* ArrSizeDim):
sizeDim(ArrSizeDim), iElem(IStart) {}

public:// Functions
T_& operator[](size_t K) const {return (*(iElem+K));}

private:// Variables
const size_t* sizeDim;
IterArr iElem;
};

template<typename T_, int ND=1> class Array: public ArrayBase<T_, ND> {
public:// Defs
typedef typename Array<T_, ND>::iterator IterArr;

public:// Uses
using vector<T_>::begin;
using vector<T_>::end;
using vector<T_>::size;
using ArrayBase<T_, ND>::sizeDim;
using ArrayBase<T_, ND>::dim;
using ArrayBase<T_, ND>::iData;

public:// Constructors
Array<T_, ND>(): ArrayBase<T_, ND>() {}
Array<T_, ND>(const Array<T_, ND>& a): ArrayBase<T_, ND>(a) {}
Array<T_, ND>(size_t D1, ...) {
// Initialize array dimensions and compute total array size
va_list ListDims;
va_start(ListDims, D1);
sizeDim[0] = 1;
for (int N = 0; N < ND; N++) {
dim[N] = (N ? va_arg(ListDims, int) : D1);
sizeDim[0] *= dim[N];
}
va_end(ListDims);

// Initialize array subspace sizes
for (int N = 1; N < ND; N++) {
sizeDim[N] = sizeDim[N-1] / dim[N-1];
}

// Allocate memory for data array
resize(sizeDim[0]);
iData = begin();
}

public:// Functions
void clear() const {return vector<T_>::clear();}
int Size() const {return int(size());}

void Resize(size_t D1, ...) {
// Initialize array dimensions and compute total size
va_list ListDims;
va_start(ListDims, D1);
sizeDim[0] = 1;
for (int N = 0; N < ND; N++) {
dim[N] = (N ? va_arg(ListDims, int) : D1);
sizeDim[0] *= dim[N];
}
va_end(ListDims);

// Initialize array subspace sizes
for (int N = 1; N < ND; N++) {
sizeDim[N] = sizeDim[N-1] / dim[N-1];
}

// Allocate memory for data array
resize(sizeDim[0]);
iData = begin();
}

void Clear() {
clear();
for (int N = 1; N < ND; N++) {
sizeDim[N] = 0;
}
}

void Fill(const T_& val) {
for (IterArr IT = begin(); IT < end(); IT++) {
(*IT) = val;
}
}

public:// Functions
SubArr<T_, ND-1> operator[](size_t K) const {
return SubArr<T_, ND-1>((iData+K*sizeDim[1]),
(sizeDim+2));
}
};

template<typename T_> class Array<T_, 1>: public ArrayBase<T_, 1> {
public:// Constructors
Array(): ArrayBase<T_, 1>() {}
Array(size_t Len): ArrayBase<T_, 1>(Len) {}
Array(const ArrayBase<T_, 1>& a): ArrayBase<T_, 1>(a) {}
};

}

#endif

//======================== Test Program ===============================

//**** Includes****
#include "Array.h"
#include <iostream>

//**** Uses ****
using std::cout;
using std::endl;
using GPD::Array;

int main() {
cout << "Start Array Test: " << endl;
Array<float,3> a(3,2,5);
for (int N0 = 0; N0 < a.Dim(0); N0++) {
for (int N1 = 0; N1 < a.Dim(1); N1++) {
for (int N2 = 0; N2 < a.Dim(2); N2++) {
a[N0][N1][N2] = 100*(N0+1) + 10*(N1+1) + (N2+1);
cout << a[N0][N1][N2] << endl;
}
}
}
return 0;

}

Thanks, that is a bit more complex than I need.