Advertisement
Advertisement


How do I declare a 2d array in C++ using new?


Question

How do i declare a 2d array using new?

Like, for a "normal" array I would:

int* ary = new int[Size]

but

int** ary = new int[sizeY][sizeX]

a) doesn't work/compile and b) doesn't accomplish what:

int ary[sizeY][sizeX] 

does.

2016/04/01
1
540
4/1/2016 12:15:41 PM

Accepted Answer

A dynamic 2D array is basically an array of pointers to arrays. You can initialize it using a loop, like this:

int** a = new int*[rowCount];
for(int i = 0; i < rowCount; ++i)
    a[i] = new int[colCount];

The above, for colCount= 5 and rowCount = 4, would produce the following:

enter image description here

2018/02/15
772
2/15/2018 10:33:16 PM


Although this popular answer will give you your desired indexing syntax, it is doubly inefficient: big and slow both in space and time. There's a better way.

Why That Answer is Big and Slow

The proposed solution is to create a dynamic array of pointers, then initializing each pointer to its own, independent dynamic array. The advantage of this approach is that it gives you the indexing syntax you're used to, so if you want to find the value of the matrix at position x,y, you say:

int val = matrix[ x ][ y ];

This works because matrix[x] returns a pointer to an array, which is then indexed with [y]. Breaking it down:

int* row = matrix[ x ];
int  val = row[ y ];

Convenient, yes? We like our [ x ][ y ] syntax.

But the solution has a big disadvantage, which is that it is both fat and slow.

Why?

The reason that it's both fat and slow is actually the same. Each "row" in the matrix is a separately allocated dynamic array. Making a heap allocation is expensive both in time and space. The allocator takes time to make the allocation, sometimes running O(n) algorithms to do it. And the allocator "pads" each of your row arrays with extra bytes for bookkeeping and alignment. That extra space costs...well...extra space. The deallocator will also take extra time when you go to deallocate the matrix, painstakingly free-ing up each individual row allocation. Gets me in a sweat just thinking about it.

There's another reason it's slow. These separate allocations tend to live in discontinuous parts of memory. One row may be at address 1,000, another at address 100,000—you get the idea. This means that when you're traversing the matrix, you're leaping through memory like a wild person. This tends to result in cache misses that vastly slow down your processing time.

So, if you absolute must have your cute [x][y] indexing syntax, use that solution. If you want quickness and smallness (and if you don't care about those, why are you working in C++?), you need a different solution.

A Different Solution

The better solution is to allocate your whole matrix as a single dynamic array, then use (slightly) clever indexing math of your own to access cells. The indexing math is only very slightly clever; nah, it's not clever at all: it's obvious.

class Matrix
{
    ...
    size_t index( int x, int y ) const { return x + m_width * y; }
};

Given this index() function (which I'm imagining is a member of a class because it needs to know the m_width of your matrix), you can access cells within your matrix array. The matrix array is allocated like this:

array = new int[ width * height ];

So the equivalent of this in the slow, fat solution:

array[ x ][ y ]

...is this in the quick, small solution:

array[ index( x, y )]

Sad, I know. But you'll get used to it. And your CPU will thank you.

2017/05/23

In C++11 it is possible:

auto array = new double[M][N]; 

This way, the memory is not initialized. To initialize it do this instead:

auto array = new double[M][N]();

Sample program (compile with "g++ -std=c++11"):

#include <iostream>
#include <utility>
#include <type_traits>
#include <typeinfo>
#include <cxxabi.h>
using namespace std;

int main()
{
    const auto M = 2;
    const auto N = 2;

    // allocate (no initializatoin)
    auto array = new double[M][N];

    // pollute the memory
    array[0][0] = 2;
    array[1][0] = 3;
    array[0][1] = 4;
    array[1][1] = 5;

    // re-allocate, probably will fetch the same memory block (not portable)
    delete[] array;
    array = new double[M][N];

    // show that memory is not initialized
    for(int r = 0; r < M; r++)
    {
        for(int c = 0; c < N; c++)
            cout << array[r][c] << " ";
        cout << endl;
    }
    cout << endl;

    delete[] array;

    // the proper way to zero-initialize the array
    array = new double[M][N]();

    // show the memory is initialized
    for(int r = 0; r < M; r++)
    {
        for(int c = 0; c < N; c++)
            cout << array[r][c] << " ";
        cout << endl;
    }

    int info;
    cout << abi::__cxa_demangle(typeid(array).name(),0,0,&info) << endl;

    return 0;
}

Output:

2 4 
3 5 

0 0 
0 0 
double (*) [2]
2015/05/27

I presume from your static array example that you want a rectangular array, and not a jagged one. You can use the following:

int *ary = new int[sizeX * sizeY];

Then you can access elements as:

ary[y*sizeX + x]

Don't forget to use delete[] on ary.

2009/06/01

There are two general techniques that I would recommend for this in C++11 and above, one for compile time dimensions and one for run time. Both answers assume you want uniform, two-dimensional arrays (not jagged ones).

Compile time dimensions

Use a std::array of std::array and then use new to put it on the heap:

// the alias helps cut down on the noise:
using grid = std::array<std::array<int, sizeX>, sizeY>;
grid * ary = new grid;

Again, this only works if the sizes of the dimensions are known at compile time.

Run time dimensions

The best way to accomplish a 2 dimensional array with sizes only known at runtime is to wrap it into a class. The class will allocate a 1d array and then overload operator [] to provide indexing for the first dimension. This works because in C++ a 2D array is row-major:

 matrix shown in logical form and one-dimensional form

(Taken from http://eli.thegreenplace.net/2015/memory-layout-of-multi-dimensional-arrays/)

A contiguous sequence of memory is good for performance reasons and is also easy to clean up. Here's an example class that omits a lot of useful methods but shows the basic idea:

#include <memory>

class Grid {
  size_t _rows;
  size_t _columns;
  std::unique_ptr<int[]> data;

public:
  Grid(size_t rows, size_t columns)
      : _rows{rows},
        _columns{columns},
        data{std::make_unique<int[]>(rows * columns)} {}

  size_t rows() const { return _rows; }

  size_t columns() const { return _columns; }

  int *operator[](size_t row) { return row * _columns + data.get(); }

  int &operator()(size_t row, size_t column) {
    return data[row * _columns + column];
  }
}

So we create an array with std::make_unique<int[]>(rows * columns) entries. We overload operator [] which will index the row for us. It returns an int * which points to the beginning of the row, which can then be dereferenced as normal for the column. Note that make_unique first ships in C++14 but you can polyfill it in C++11 if necessary.

It's also common for these types of structures to overload operator() as well:

  int &operator()(size_t row, size_t column) {
    return data[row * _columns + column];
  }

Technically I haven't used new here, but it's trivial to move from std::unique_ptr<int[]> to int * and use new/delete.

2018/09/29

This question was bugging me - it's a common enough problem that a good solution should already exist, something better than the vector of vectors or rolling your own array indexing.

When something ought to exist in C++ but doesn't, the first place to look is boost.org. There I found the Boost Multidimensional Array Library, multi_array. It even includes a multi_array_ref class that can be used to wrap your own one-dimensional array buffer.

2009/06/02

Source: https://stackoverflow.com/questions/936687
Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Email: [email protected]