.. highlight:: c++
  :linenothreshold: 5


**********************
Multidimensional Array
**********************

General Multidimensional Array
==============================
+ Multidimensional arrays - arrays of arrays

  .. code-block:: c++

    int a[10];  // 1d local array
    int a1[2][3];  // 2d local array
    int a2[2][3][4];  // 3d local array
    int **a3;  // pointer of pointer to int, used for 2D dynamic array
    int ***a4;  // pointer of pointer of pointer to int, used for 3D dynamic array

.. graphviz::
  :caption: int matrix[10][10];  // a local 10 x 10 2D array

  digraph G {
    nodesep=.05;
    rankdir=LR;
    matrix[shape=box,height=0.1];
    node[shape=record,width=0.1,height=0.1];
    first[label="<f0>|<f1>|<f2>|<f3>|<f4>|<f5>|<f6>|<f7>|<f8>|<f9>"];
    matrix -> first:f0;

    sec0[label="{<s0>||||||||}"];
    sec1[label="{<s0>||||||||}"];
    sec2[label="{<s0>||||||||}"];
    sec3[label="{<s0>||||||||}"];
    sec4[label="{<s0>||||||||}"];
    sec5[label="{<s0>||||||||}"];
    sec6[label="{<s0>||||||||}"];
    sec7[label="{<s0>||||||||}"];
    sec8[label="{<s0>||||||||}"];
    sec9[label="{<s0>||||||||}"];

    first:f0 -> sec0:s0:w;
    first:f1 -> sec1:s0:w;
    first:f2 -> sec2:s0:w;
    first:f3 -> sec3:s0:w;
    first:f4 -> sec4:s0:w;
    first:f5 -> sec5:s0:w;
    first:f6 -> sec6:s0:w;
    first:f7 -> sec7:s0:w;
    first:f8 -> sec8:s0:w;
    first:f9 -> sec9:s0:w;
  }


Two dimensional array
=====================
+ 2d local array

  Example: a local array a1 with 2 rows, 3 columns

  * ``int a1[2][3];``
  * a1 has the pointer part of the array with the ``int **`` type
  * a1 is an array of 2 element, and each element is an array of 3 int
  * memory allocated on **stack** memory region
  * initialization syntax

    .. code-block:: c++

      // initialization of 2d array
      // a1[0] is {1, 2, 3}, a1[1] is {4, 5, 6}
      int a1[2][3] = {{1, 2, 3}, {4, 5, 6}};
      int a2[2][3] = {1, 2, 3, 4, 5, 6};
      int a3[][3] = {1, 2, 3, 4, 5, 6};  // first dimension can be inferred

+ 2d dynamic array

  Example: a dynamic array dynArr1 with 2 rows, 3 columns

  .. code-block:: c++

    // declaration
    int **dynArr1;

    // allocate memory (on Heap)
    dynArr1 = new int *[2];
    for (int i = 0; i < 2 ; ++i)
      dynArr1[i] = new int[3];
    //now you can access element using array syntax like dynArr1[0][0]

    // put values into the array
    for (int i = 0; i < 2 ; ++i)
      for (int j = 0; j < 3; ++j)
        dynArr1[i][j] = i * 3 + j + 1;
    // now dynArr1 is {{1, 2, 3}, {4, 5, 6}}

    // release memory
    for (int i = 0; i < 2 ; ++i)
      delete [] dynArr1[i];
    delete [] dynArr1;

.. _pass-2d-array:

+ 2d array as a function parameter

  #. pass a 2 x 3 **local** array

     + Declared like ``int a1[2][3];``
     + Not useful in real projects because of the limitation on dimension

     .. code-block:: c++

       // ---- wrong ----
       void matrixOp(int matrix[rows][cols], int rows, int cols);
       void matrixOp(int matrix[][], int rows, int cols);
       void matrixOp(int matrix[2][], int rows, int cols);

       // ---- correct ----
       // only the first dimension can be empty, use int literals
       // or const variables for other dimensions
       void matrixOp(int matrix[2][3], int rows, int cols);
       void matrixOp(int matrix[][3], int rows, int cols);

       // using const variables
       const int ROWS = 2;
       const int COLS = 3;
       void matrixOp(int matrix[ROWS][COLS], int rows, int cols);
       void matrixOp(int matrix[][COLS], int rows, int cols);

       // to call
       int a1[2][3] = {{1, 2, 3}, {4, 5, 6}};
       matrixOp(a1, 2, 3)

  #. passing a **dynamic** array, a much nicer solution
     + declared like ``int **dyArr1``

     .. code-block:: c++

       // correct version 1
       void matrixOp(int ** matrix, int rows, int cols) {
         for (int i = 0; i < rows ; ++i)
           for (int j = 0; j < cols; ++j)
             cout << matrix[i][j] << " ";  // same syntax as local array
       }
       // correct version 2
       void matrixOp(int *matrix[], int rows, int cols);

       // to call the function
       int **dyArr1;
       dyArr1 = new int *[2];
       for (int i = 0; i < 2; ++i) {
         dyArr1[i] = new int[3];
         // initialize values
       }
       matrixOp(dynArr1, 2, 3);
       // for loop delete []
       for (int i = 0; i < 2; ++i)
         delete [] dyArr1[i];
       delete [] dyArr1;

.. _return-md-array:

+ Returning a Multidimensional array from a function

  Just make a dynamic array and return the pointer::

    int **createMatrix(int rows, int cols, int value);

    int **createMatrix(int rows, int cols, int value) {
      int **result;
      result = new int *[rows];
      for (int i = 0; i < rows; ++i) {
        result[i] = new int[cols];
        for (int j = 0; j < cols; ++j)
          result[i][j] = value;
      }
      return result;
    }

    int main() {
      int **matrix = createMatrix(3, 5, 1);

      // work on the matrix

      // release memory
      for (int i = 0; i < rows; ++i)
        delete [] matrix[i];
      delete [] matrix;
    }

.. warning::

  This is the only option to return an array! Never return a local array!


.. warning::

  Never forget to delete dynamic array(s)!

.. _md-arr-pitfall:

Pitfalls
========

::

  // bad local array declaration
  int arr[rows][cols];  // rows and cols are not compilation-time constants
  int arr[][];
  int arr[2][];
  int arr[][3];

  // bad dynamic array related
  int **arr = new int[2][3];  // cannot use more than one pair of [] with new
  delete arr;  // missing []
  delete [2][3] arr;
  delete [][] arr;
  delete arr[2][3];

  // bad function declarations that take local array parameters
  void func1(int arr[][], int rows, int cols);
  void func1(int arr[2][], int rows, int cols);
  void func1(int arr[rows][cols], int rows, int cols);


  // bad function declarations that take dynamic array parameters
  void func1(int *arr[], int rows, int cols);