Как мне объявить 2d массив в C ++, используя new? - PullRequest
475 голосов
/ 02 июня 2009

Как мне объявить 2d массив, используя new?

Например, для "нормального" массива я бы:

int* ary = new int[Size]

но

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

а) не работает / не компилируется и б) не выполняет то, что:

int ary[sizeY][sizeX] 

делает.

Ответы [ 22 ]

678 голосов
/ 02 июня 2009

Динамический двумерный массив - это массив указателей на массивы . Вы можете инициализировать его с помощью цикла, например:

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

Выше, для colCount= 5 и rowCount = 4, получилось бы следующее:

enter image description here

288 голосов
/ 02 июня 2009
int** ary = new int[sizeY][sizeX]

должно быть:

int **ary = new int*[sizeY];
for(int i = 0; i < sizeY; ++i) {
    ary[i] = new int[sizeX];
}

и тогда очистка будет:

for(int i = 0; i < sizeY; ++i) {
    delete [] ary[i];
}
delete [] ary;

РЕДАКТИРОВАТЬ: , как отметил Дитрих Эпп в комментариях, это не совсем легкое решение. Альтернативный подход заключается в использовании одного большого блока памяти:

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

// ary[i][j] is then rewritten as
ary[i*sizeY+j]
188 голосов
/ 03 марта 2015

Хотя этот популярный ответ даст вам желаемый синтаксический индекс, он вдвойне неэффективен: большой и медленный как в пространстве, так и во времени. Есть лучший способ.

Почему этот ответ большой и медленный

Предлагаемое решение - создать динамический массив указателей, а затем инициализировать каждый указатель своим собственным независимым динамическим массивом. Преимущество этого подхода состоит в том, что он дает вам синтаксис индексации, к которому вы привыкли, поэтому, если вы хотите найти значение матрицы в позиции x, y, вы скажете:

int val = matrix[ x ][ y ];

Это работает, потому что matrix [x] возвращает указатель на массив, который затем индексируется с помощью [y]. Разбивка:

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

Удобно, да? Нам нравится наш [x] [y] синтаксис.

Но решение имеет большой недостаток , заключающийся в том, что оно и жирное, и медленное.

Почему?

Причина, по которой он толстый и медленный, на самом деле одна и та же. Каждая «строка» в матрице представляет собой отдельно выделенный динамический массив. Распределение кучи требует больших затрат как во времени, так и в пространстве. Распределитель требует времени, чтобы выполнить выделение, иногда запуская O (n) алгоритмы, чтобы сделать это. И распределитель «дополняет» каждый из ваших массивов строк дополнительными байтами для учета и выравнивания. Это дополнительное место стоит ... ну ... дополнительное место. При освобождении матрицы также потребуется дополнительное время для освобождения матрицы, кропотливого освобождения каждого отдельного распределения строк. Встает в меня, просто думая об этом.

Есть еще одна причина, по которой он медленный. Эти отдельные распределения имеют тенденцию жить в прерывистых частях памяти. Одна строка может быть по адресу 1000, другая по адресу 100000 - вы поняли. Это означает, что когда вы пересекаете матрицу, вы перепрыгиваете через память, как дикий человек. Это приводит к потере кеша, что значительно замедляет время обработки.

Итак, если у вас в абсолюте должен быть симпатичный синтаксис [x] [y], используйте это решение. Если вам нужна быстрота и малость (и если вас это не волнует, почему вы работаете в C ++?), Вам нужно другое решение.

Другое решение

Лучшее решение состоит в том, чтобы выделить всю матрицу в виде одного динамического массива, а затем использовать (слегка) умную собственную индексную математику для доступа к ячейкам. Индексная математика очень умна; нет, это совсем не умно: это очевидно.

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

Учитывая, что эта функция index() (которую я представляю, является членом класса, потому что она должна знать m_width вашей матрицы), вы можете получить доступ к ячейкам внутри вашего матричного массива. Матричный массив выделяется так:

array = new int[ width * height ];

Итак, эквивалент этого в медленном, жирном растворе:

array[ x ][ y ]

... это быстрое, маленькое решение:

array[ index( x, y )]

Грустно, я знаю. Но вы привыкнете к этому. И ваш процессор поблагодарит вас.

111 голосов
/ 26 апреля 2013

В C ++ 11 это возможно:

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

Таким образом, память не инициализируется. Чтобы инициализировать это, сделайте это вместо:

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

Пример программы (скомпилировать с помощью "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;
}

Выход:

2 4 
3 5 

0 0 
0 0 
double (*) [2]
53 голосов
/ 02 июня 2009

Я предполагаю из вашего примера статического массива, что вы хотите прямоугольный массив, а не зубчатый. Вы можете использовать следующее:

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

Тогда вы можете получить доступ к элементам как:

ary[y*sizeX + x]

Не забудьте использовать delete [] на ary.

41 голосов
/ 28 августа 2015

Есть два основных метода, которые я бы порекомендовал для этого в C ++ 11 и выше, один для измерений времени компиляции и один для времени выполнения. В обоих ответах предполагается, что вам нужны однородные двумерные массивы (не зубчатые).

Размеры времени компиляции

Используйте std::array из std::array, а затем используйте new, чтобы положить его в кучу:

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

Опять же, это работает, только если размеры измерений известны во время компиляции.

Измерения времени выполнения

Лучший способ создания двумерного массива с размерами, известными только во время выполнения, - заключить его в класс. Класс выделит одномерный массив, а затем перегрузит operator [], чтобы обеспечить индексацию для первого измерения. Это работает, потому что в C ++ двумерный массив имеет мажорную строку:

matrix shown in logical form and one-dimensional form

(взято из http://eli.thegreenplace.net/2015/memory-layout-of-multi-dimensional-arrays/)

Непрерывная последовательность памяти хороша из соображений производительности, а также легко очищается. Вот пример класса, который пропускает много полезных методов, но показывает основную идею:

#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];
  }
}

Итак, мы создаем массив с std::make_unique<int[]>(rows * columns) записями. Мы перегружаем operator [], что будет индексировать строку для нас. Он возвращает int *, который указывает на начало строки, которая затем может быть разыменована как обычно для столбца. Обратите внимание, что make_unique сначала поставляется в C ++ 14, но вы можете заполнить его в C ++ 11, если необходимо.

Для этих типов конструкций также характерно перегрузка operator():

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

Технически я не использовал new здесь, но тривиально перейти от std::unique_ptr<int[]> к int * и использовать new / delete.

27 голосов
/ 02 июня 2009

Этот вопрос меня беспокоил - это достаточно распространенная проблема, что хорошее решение уже должно существовать, что-то лучше, чем вектор векторов или сворачивание индексации собственного массива.

Когда что-то должно существовать в C ++, но его нет, первое, на что нужно обратить внимание, это boost.org . Там я нашел библиотеку Boost для многомерных массивов, multi_array. Он даже включает класс multi_array_ref, который можно использовать для переноса собственного буфера одномерного массива.

23 голосов
/ 06 июня 2016

Почему бы не использовать STL: вектор? Так просто, и вам не нужно удалять вектор.

int rows = 100;
int cols = 200;
vector< vector<int> > f(rows, vector<int>(cols));
f[rows - 1][cols - 1] = 0; // use it like arrays

Источник: Как создать 2, 3 (или мульти) размерные массивы в C / C ++?

14 голосов
/ 09 марта 2016

2D-массив - это, в основном, одномерный массив указателей, где каждый указатель указывает на одномерный массив, который будет содержать фактические данные.

Здесь N - строка, а M - столбец.

динамическое распределение

int** ary = new int*[N];
  for(int i = 0; i < N; i++)
      ary[i] = new int[M];

заполнения

for(int i = 0; i < N; i++)
    for(int j = 0; j < M; j++)
      ary[i][j] = i;

печать

for(int i = 0; i < N; i++)
    for(int j = 0; j < M; j++)
      std::cout << ary[i][j] << "\n";

бесплатно

for(int i = 0; i < N; i++)
    delete [] ary[i];
delete [] ary;
13 голосов
/ 12 января 2012

Как выделить непрерывный многомерный массив в GNU C ++? Существует расширение GNU, позволяющее работать «стандартному» синтаксису.

Кажется, проблема в операторе new []. Убедитесь, что вместо этого вы используете оператор new:

double (* in)[n][n] = new (double[m][n][n]);  // GNU extension

И это все: вы получаете C-совместимый многомерный массив ...

...