Multi-Dimensional Arrays

[Zaita]

This is another topic we get asked quite a bit.
- How do I do a 2D/3D Array?

When I also started working with multi-dimensional arrays I found it hard to find the answers I wanted too. So I'll post up some info that will hopefully help other people. I'll go over both of the 2 major methods (Vector vs Pointer).

Vector based multi-dimensional arrays
Vectors are a STL container that allow you to store pretty much anything in them. When used correctly they can be very powerful containers.

They provide an added benefit that they will automatically remove the memory they use when they go out of scope. This means that objects stored within a vector do not need to be de-allocated (but pointers to objects do).

You can also do some interesting things with dynamic multi-dimensional arrays with vectors. For example, if you only allocate the first dimension, then use the .push_back() to add records to the 2nd dimension it's no longer a grid, but an array with a dynamically sized 2nd dimension (much like a street of buildings each with a different amount of floors). This functionality can be achieved using pointers, but is much harder to do.

A simple 2D Array with vectors:

#include <vector>
using std::vector;

#define HEIGHT 5
#define WIDTH 3

int main() {
  vector<vector<double> > array2D;

  // Set up sizes. (HEIGHT x WIDTH)
  array2D.resize(HEIGHT);
  for (int i = 0; i < HEIGHT; ++i)
    array2D[i].resize(WIDTH);

  // Put some values in
  array2D[1][2] = 6.0;
  array2D[3][1] = 5.5;

  return 0;
}

A 3D Array with vectors.

#include <vector>
using std::vector;

#define HEIGHT 5
#define WIDTH 3
#define DEPTH 7

int main() {
  vector<vector<vector<double> > > array3D;

  // Set up sizes. (HEIGHT x WIDTH)
  array3D.resize(HEIGHT);
  for (int i = 0; i < HEIGHT; ++i) {
    array3D[i].resize(WIDTH);

    for (int j = 0; j < WIDTH; ++j)
      array3D[i][j].resize(DEPTH);
  }

  // Put some values in
  array3D[1][2][5] = 6.0;
  array3D[3][1][4] = 5.5;

  return 0;
}

Pointer based multi-dimensional arrays
Pointer based multi-dimensional arrays provide you with a more raw access to the objects. The benefits can be added speed and you can apply custom optimizations to them.

Note: There are ways you can optimize this by combining the 2 dimensions into a single dimension (HEIGHTxWIDTH). I leave the discussion of this out, as it's a more advanced topic for people already familiar with this topic.

A simple 2D Array:

#define HEIGHT 5
#define WIDTH 3

int main() {
  double **p2DArray;

  // Allocate memory
  p2DArray = new double*[HEIGHT];
  for (int i = 0; i < HEIGHT; ++i)
    p2DArray[i] = new double[WIDTH];

  // Assign values
  p2DArray[0][0] = 3.6;
  p2DArray[1][2] = 4.0;

  // De-Allocate memory to prevent memory leak
  for (int i = 0; i < HEIGHT; ++i)
    delete [] p2DArray[i];
  delete [] p2DArray;

  return 0;
}

A 3D Array:

#define HEIGHT 5
#define WIDTH 3
#define DEPTH 7

int main() {
  double ***p2DArray;

  // Allocate memory
  p2DArray = new double**[HEIGHT];
  for (int i = 0; i < HEIGHT; ++i) {
    p2DArray[i] = new double*[WIDTH];

    for (int j = 0; j < WIDTH; ++j)
      p2DArray[i][j] = new double[DEPTH];
  }

  // Assign values
  p2DArray[0][0][0] = 3.6;
  p2DArray[1][2][4] = 4.0;

  // De-Allocate memory to prevent memory leak
  for (int i = 0; i < HEIGHT; ++i) {
    for (int j = 0; j < WIDTH; ++j)
      delete [] p2DArray[i][j];

    delete [] p2DArray[i];
  }
  delete [] p2DArray;

  return 0;
}

One final thing to note. When creating dynamic arrays with your own object types, you cannot overload the constructor. The ISO standard forbids this, and you must initialize the values on the objects later. All objects allocated into arrays must utilize the default constructor.

The above code snippets should compile on both Windows and Linux with no problems.

Recommendations
Unless your application has an extreme need to be highly optimized, and you are quite proficient at C++ memory management, you will want to use the vector based approach. This method is a lot easier to manage, especially if you are just learning C++.

[Mythios]

Very nice Zaita, once you understand them they are more easier than you think. But you explanation here covers it quite well. So for those of you who don't I believe this will be helpful.

Awesome work ;)

Shame we cant ++rep;

[Mythios]

You should possibly add how to pass 2d and 3d arrays to functions etc? Would be a good help for a lot of people as that question goes around a fair bit.

[cascade384]

Would it be something like this?void function(double array[][WIDTH])

[Zaita]

You can pass them by pointer.

e.g
void doSomethingWith2D(double **Array);
or
voud doSomethingWith2D(vector<vector<double> > &Array);

[Mythios]

You can also pass them by reference

void function( int (&myArray)[HEIGHT][WIDTH]

According to C++ Primer 4th Edition

[vRltwE]

And how can a method return a vector?

How can I do to pass matrix from method matrix_read to main?

/* 
 * File:   main.cpp
 * Author: cristiano
 *
 * Created on April 22, 2009, 11:32 AM
 */

#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>

using namespace std;
/*
 * 
 */

int matrix_lines(istream &iFile) {
// Método para obter o número linhas da matriz.
    iFile.clear();
    iFile.seekg(0);
    int lines = 0;
    string line;
    while(!iFile.eof()) {
        getline (iFile, line);
        lines++;
    }
    cout << "Número de linhas: " << lines-1 << endl;
    return lines-1;
}

int matrix_cols(istream &iFile) {
// Método para obter o número de colunas da matriz.
    iFile.clear();
    iFile.seekg(0);

    string line;
    double n;
    int cols = 0;

    getline (iFile, line);
//    cout << line << endl;

    stringstream is(line);
    n = 0;
    while (is >> n) {
//        cout << n << endl;
        cols++;
    }


//
    cout << "Número de colunas: " << cols << endl;
    return cols;
}

double** matrix_read(istream &iFile, int lines, int cols) {
// Método para ler a matriz.

    vector<vector<double> > matrix;
    matrix.resize(cols);
    for(int i = 0; i < cols; i++)
        matrix[i].resize(lines);

    double value;
    iFile.clear();
    iFile.seekg(0);
    
    for(int i = 0; i < lines; i++){
        for(int j = 0; j < cols; j++){
           matrix[i][j]  = (iFile >> value,value);
           cout << matrix[i][j] << " ";
        }
        cout << "\n";
    }
    return matrix;
}

int main(int argc, char** argv) {
    
    int lines,cols;
    ifstream iFile;
    iFile.open("/home/cristiano/matrix3.dat");

    if(!iFile) { // file couldn't be opened
        cerr << "Error: file could not be opened" << endl;
        exit(1);
    }

    cols = matrix_cols(iFile);
    lines = matrix_lines(iFile);

//    vector<vector<double> > matrix;
//    matrix.resize(cols);
//    for(int i = 0; i < cols; i++)
//        matrix[i].resize(lines);

    matrix_read(iFile, lines, cols);


    iFile.close();

    return (EXIT_SUCCESS);
}

[kempofighter]

@cstrieder: I wouldn't recommend returning the vector as it will cost you dearly. you'd have to build a vector within the function and return it by value resulting in a copy after building the vector. Multi-Dimensional arrays can get very large depending on their size and number of dimensions. I would recommend passing an inout parameter to the function as a reference and then filling it for the caller. The function would have a void return type. First, create a typedef for the type so that you don't have to retype so much.

typedef std::vector<vector<double> > MatrixArrayType;


Declare the function like so. Notice that you don't need to pass cols and lines parameters anymore because the caller could simply build the inout parameter to the correct initial size. Moreover, it is not good for Matrix_Read to assume things about the file. You need to take into consideration that the contents of the file could cause it to grow.
void matrix_read(istream &iFile, MatrixArrayType& theMatrix);

[kempofighter]

@zaita: I think that this is a nice article. I only have 2 minor critiques of it.

First, the following statement is not entirely true. I see your point but it is worded incorrectly.

One final thing to note. When creating dynamic arrays with your own object types, you cannot overload the constructor. The ISO standard forbids this, and you must initialize the values on the objects later. All objects allocated into arrays must utilize the default constructor.

You can overload the constructor provided that you define the default constructor or provide a constructor that can be invoked without any arguments. Take a look at this example. It compiles just fine. The constructor has default values so a point can be constructed without any user supplied arguments.

class point
{
public:
	point(int x = 0, int y = 0) : x_(x), y_(y) { }
	int getX() const { return x_; }
	int getY() const { return y_; }

private:
	int x_;
	int y_;
};

int main()
{
	
	// Build a dynamic array of points
	point thePointArray[5][5];
	point** theDynPointArray = new point*[5];
	for(int i = 0; i < 5; ++i)
		theDynPointArray[i] = new point[5];
	return 0;
}

The only other suggestion I had was to provide a 3rd section on non-dynamic multi-dimensional arrays. Perhaps the intent was to show how dynamic arrays are created but based on the title I thought it was about multi-dimensional arrays in general. They don't have to be dynamic at all.

[Polter]

Use the Boost Multidimensional Array Library:
http://www.boost.org/doc/libs/1_39_0/libs/multi_array/doc/user.html

Quoting synopsis:

"The Boost Multidimensional Array Library provides a class template for multidimensional arrays, as well as semantically equivalent adaptors for arrays of contiguous data. The classes in this library implement a common interface, formalized as a generic programming concept. The interface design is in line with the precedent set by the C++ Standard Library containers. Boost MultiArray is a more efficient and convenient way to express N-dimensional arrays than existing alternatives (especially the std::vector<std::vector<...>> formulation of N-dimensional arrays). The arrays provided by the library may be accessed using the familiar syntax of native C++ arrays. Additional features, such as resizing, reshaping, and creating views are available (and described below). "

Here's an example (from the same source):

#include "boost/multi_array.hpp"
#include <cassert>

int 
main () {
  // Create a 3D array that is 3 x 4 x 2
  typedef boost::multi_array<double, 3> array_type;
  typedef array_type::index index;
  array_type A(boost::extents[3][4][2]);

  // Assign values to the elements
  int values = 0;
  for(index i = 0; i != 3; ++i) 
    for(index j = 0; j != 4; ++j)
      for(index k = 0; k != 2; ++k)
        A[i][j][k] = values++;

  // Verify values
  int verify = 0;
  for(index i = 0; i != 3; ++i) 
    for(index j = 0; j != 4; ++j)
      for(index k = 0; k != 2; ++k)
        assert(A[i][j][k] == verify++);

  return 0;
}