Как мне лучше всего обрабатывать динамические многомерные массивы в C / C ++?

Question

Какой принятый / наиболее часто используемый способ манипулирования динамическими (со всеми измерениями, неизвестными до времени выполнения) многомерными массивами в C и / или C ++.

Я пытаюсь найти самый чистый способ выполнить то, что делает этот код Java:

public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 int rows=sc.nextInt();
 int cols=sc.nextInt();
 int[][] data=new int[rows][cols];
 manipulate(data);
}

public static void manipulate(int[][] data){
   for(int i=0;i<data.length;i++)
   for(int j=0;j<data[0].length.j++){
         System.out.print(data[i][j]);       
   }    
}

(читает из std_in только для пояснения, что измерения неизвестны до времени выполнения).

Редактировать: я заметил, что этот вопрос довольно популярен, хотя он довольно старый. Я на самом деле не согласен с ответом сверху. Я думаю, что лучший выбор для C - это использовать одномерный массив, как сказал Гуге ниже: «Вы можете выделить строки cols sizeof (int) и получить к нему доступ с помощью таблицы [row * cols + col].».

Существует ряд вариантов с C ++, если вам действительно нравятся boost или stl, тогда ответы ниже могут быть предпочтительнее, но самый простой и, вероятно, самый быстрый выбор - использовать одномерный массив, как в C.

Другим жизнеспособным выбором в C и C ++, если вы хотите использовать синтаксис [] [], является ответ lillq внизу - это ручное построение массива с большим количеством malloc.

Answer 1

Использование boost :: multi_array .

Как и в вашем примере, единственное, что вам нужно знать во время компиляции, это количество измерений. Вот первый пример в документации:

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

Редактировать: Как предлагается в комментариях, представляет собой «простой» пример приложения, которое позволяет вам определять размер многомерного массива во время выполнения, запрашивая данные с консоли. Вот пример выходных данных этого примера приложения (скомпилированный с константой, говорящей, что это 3 измерения):

Multi-Array test!
Please enter the size of the dimension 0 : 4

Please enter the size of the dimension 1 : 6

Please enter the size of the dimension 2 : 2

Text matrix with 3 dimensions of size (4,6,2) have been created.

Ready!
Type 'help' for the command list.

>read 0.0.0
Text at (0,0,0) :
  ""

>write 0.0.0 "This is a nice test!"
Text "This is a nice test!" written at position (0,0,0)

>read 0.0.0
Text at (0,0,0) :
  "This is a nice test!"

>write 0,0,1 "What a nice day!"
Text "What a nice day!" written at position (0,0,1)

>read 0.0.0
Text at (0,0,0) :
  "This is a nice test!"

>read 0.0.1
Text at (0,0,1) :
  "What a nice day!"

>write 3,5,1 "This is the last text!"
Text "This is the last text!" written at position (3,5,1)

>read 3,5,1
Text at (3,5,1) :
  "This is the last text!"

>exit

Важными частями в коде являются основная функция, где мы получаем измерения от пользователя и создаем массив с:

const unsigned int DIMENSION_COUNT = 3; // dimension count for this test application, change it at will :)

// here is the type of the multi-dimensional (DIMENSION_COUNT dimensions here) array we want to use
// for this example, it own texts
typedef boost::multi_array< std::string , DIMENSION_COUNT > TextMatrix;

// this provide size/index based position for a TextMatrix entry.
typedef std::tr1::array<TextMatrix::index, DIMENSION_COUNT> Position; // note that it can be a boost::array or a simple array

/*  This function will allow the user to manipulate the created array
    by managing it's commands.
    Returns true if the exit command have been called.
*/
bool process_command( const std::string& entry, TextMatrix& text_matrix );

/* Print the position values in the standard output. */
void display_position( const Position& position );

int main()
{
    std::cout << "Multi-Array test!" << std::endl;

    // get the dimension informations from the user
    Position dimensions; // this array will hold the size of each dimension 

    for( int dimension_idx = 0; dimension_idx < DIMENSION_COUNT; ++dimension_idx )
    {
        std::cout << "Please enter the size of the dimension "<< dimension_idx <<" : ";
        // note that here we should check the type of the entry, but it's a simple example so lets assume we take good numbers
        std::cin >> dimensions[dimension_idx]; 
        std::cout << std::endl;

    }

    // now create the multi-dimensional array with the previously collected informations
    TextMatrix text_matrix( dimensions );

    std::cout << "Text matrix with " << DIMENSION_COUNT << " dimensions of size ";
    display_position( dimensions );
    std::cout << " have been created."<< std::endl;
    std::cout << std::endl;
    std::cout << "Ready!" << std::endl;
    std::cout << "Type 'help' for the command list." << std::endl;
    std::cin.sync();


    // we can now play with it as long as we want
    bool wants_to_exit = false;
    while( !wants_to_exit )
    {
        std::cout << std::endl << ">" ;
        std::tr1::array< char, 256 > entry_buffer; 
        std::cin.getline(entry_buffer.data(), entry_buffer.size());

        const std::string entry( entry_buffer.data() );
        wants_to_exit = process_command( entry, text_matrix );
    }

    return 0;
}

И вы можете видеть, что для присоединения элемента в массиве это действительно просто: вы просто используете operator (), как в следующих функциях:

void write_in_text_matrix( TextMatrix& text_matrix, const Position& position, const std::string& text )
{
    text_matrix( position ) = text;
    std::cout << "Text \"" << text << "\" written at position ";
    display_position( position );
    std::cout << std::endl;
}

void read_from_text_matrix( const TextMatrix& text_matrix, const Position& position )
{
    const std::string& text = text_matrix( position );
    std::cout << "Text at ";
    display_position(position);
    std::cout << " : "<< std::endl;
    std::cout << "  \"" << text << "\"" << std::endl;
}

Примечание: я скомпилировал это приложение в VC9 + SP1 - получил только несколько забывчивых предупреждений.

Answer 2

Существует два способа представления двумерного массива в C ++. Один из них более гибкий, чем другой.

Массив массивов

Сначала создайте массив указателей, затем инициализируйте каждый указатель другим массивом.

// First dimension
int** array = new int*[3];
for( int i = 0; i < 3; ++i )
{
    // Second dimension
    array[i] = new int[4];
}

// You can then access your array data with
for( int i = 0; i < 3; ++i )
{
    for( int j = 0; j < 4; ++j )
    {
        std::cout << array[i][j];
    }
}

Проблема с этим методом заключается в том, что вашему второму измерению выделяется столько же массивов, что не облегчает работу распределителя памяти. Ваша память может быть фрагментирована, что приведет к снижению производительности. Это обеспечивает большую гибкость, поскольку каждый массив во втором измерении может иметь свой размер.

Большой массив для хранения всех значений

Хитрость в том, чтобы создать массивный массив для хранения всех необходимых вам данных. Сложность в том, что вам все еще нужен первый массив указателей, если вы хотите иметь доступ к данным с использованием синтаксиса array [i] [j].

int* buffer = new int[3*4];   
int** array = new int*[3];

for( int i = 0; i < 3; ++i )
{
    array[i] = array + i * 4;
}

Массив int * не является обязательным, так как вы можете получить доступ к своим данным непосредственно в буфере, вычислив индекс в буфере из двухмерных координат значения.

// You can then access your array data with
for( int i = 0; i < 3; ++i )
{
    for( int j = 0; j < 4; ++j )
    {
        const int index = i * 4 + j;
        std::cout << buffer[index];
    }
}

ПРАВИЛО, о котором следует помнить

Память компьютера является линейной и будет работать долго. Помните, что двумерные массивы изначально не поддерживаются на компьютере, поэтому единственный способ - это «линеаризовать» массив в одномерный массив.

Answer 3

Вы можете выделить строки cols sizeof (int) и получить к нему доступ по таблице [row * cols + col].

Answer 4

Вот простой способ сделать это в C:

void manipulate(int rows, int cols, int (*data)[cols]) {
    for(int i=0; i < rows; i++) {
        for(int j=0; j < cols; j++) {
            printf("%d ", data[i][j]);       
        }
        printf("\n");
    }
}

int main() {
    int rows = ...;
    int cols = ...;
    int (*data)[cols] = malloc(rows*sizeof(*data));
    manipulate(rows, cols, data);
    free(data);
}

Это совершенно верно, начиная с C99, однако это не C ++ какого-либо стандарта: C ++ требует, чтобы размеры типов массивов были постоянными времени компиляции. В этом отношении C ++ сейчас на пятнадцать лет отстает от C. И эта ситуация не изменится в ближайшее время (предложение массива переменной длины для C ++ 17 не приближается к функциональности массивов переменной длины C99).

Answer 5

Стандартным способом без использования boost является использование std :: vector:

std::vector< std::vector<int> > v;
v.resize(rows, std::vector<int>(cols, 42)); // init value is 42
v[row][col] = ...;

Это автоматически позаботится о новой / удаленной памяти. Но он довольно медленный, так как std::vector изначально не предназначен для такого использования (вложение std::vector друг в друга). Например, вся память выделяется не в одном блоке, а отдельно для каждого столбца. Кроме того, строки не должны быть одинаковой ширины. Faster использует нормальный вектор, а затем выполняет вычисление индекса, например col_count * row + col, чтобы получить определенную строку и столбец:

std::vector<int> v(col_count * row_count, 42);
v[col_count * row + col) = ...;

Но это потеряет возможность индексировать вектор, используя [x][y]. Вы также должны где-то хранить количество строк и столбцов, используя вложенное решение, вы можете получить количество строк, используя v.size(), и количество столбцов, используя v[0].size().

Используя boost, вы можете использовать boost::multi_array, который делает именно то, что вы хотите (см. Другой ответ).

---

Существует также простой способ использования собственных массивов C ++. Это влечет за собой некоторую работу и ничем не лучше, чем решение с вложенными векторами:

int ** rows = new int*[row_count];
for(std::size_t i = 0; i < row_count; i++) {
    rows[i] = new int[cols_count];
    std::fill(rows[i], rows[i] + cols_count, 42);
}

// use it... rows[row][col] then free it...

for(std::size_t i = 0; i < row_count; i++) {
    delete[] rows[i];
}

delete[] rows;

Вы должны хранить количество созданных вами столбцов и строк, поскольку вы не можете получить их от указателя.

Answer 6

2D-массивы в стиле C в C и C ++ - это блок памяти размером rows * columns * sizeof(datatype) байт.

Фактические измерения [строка] [столбец] существуют только статически во время компиляции. Там нет ничего динамически во время выполнения!

Итак, как уже упоминали другие, вы можете реализовать

  int array [ rows ] [ columns ];

Как:

 int  array [ rows * columns ]

или как:

 int * array = malloc ( rows * columns * sizeof(int) );

---

Далее: Объявление массива переменного размера. В C это возможно:

int main( int argc, char ** argv )
{
  assert( argc > 2 );

  int rows    = atoi( argv[1] );
  int columns = atoi( argv[2] );

  assert(rows > 0 && columns > 0);
  int data [ rows ] [ columns ];  // Yes, legal!

  memset( &data, 0, sizeof(data) );

  print( rows, columns, data );
  manipulate( rows, columns, data );
  print( rows, columns, data );
}

---

В C вы можете просто передать массив переменного размера примерно так же, как массив без переменного размера:

void manipulate( int theRows, int theColumns, int theData[theRows][theColumns] )
{
  for (   int r = 0; r < theRows;    r ++ )
    for ( int c = 0; c < theColumns; c ++  )
      theData[r][c] = r*10 + c;
}

Однако в C ++ это невозможно. Вы должны выделить массив с помощью динамического выделения, например:

int *array = new int[rows * cols]();

или предпочтительно (с автоматическим управлением памятью)

std::vector<int> array(rows * cols);

Затем функции должны быть изменены, чтобы принимать одномерные данные:

void manipulate( int theRows, int theColumns, int *theData )
{
  for (   int r = 0; r < theRows;    r ++ )
    for ( int c = 0; c < theColumns; c ++  )
      theData[r * theColumns + c] = r*10 + c;
}

Answer 7

Если вы используете C вместо C ++, возможно, вы захотите взглянуть на абстракцию Array_T в библиотеке Дейва Хансона Интерфейсы и реализации C . Это исключительно чистый и хорошо продуманный. Мои ученики выполняют двумерную версию в качестве упражнения. Вы можете сделать это или просто написать дополнительную функцию, которая выполняет отображение индекса, например,

void *Array_get_2d(Array_T a, int width, int height, int i, int j) {
    return Array_get(a, j * width, i, j);
}

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

Answer 8

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

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я не был уверен, должен ли я публиковать это как ответ, потому что он отвечает только на часть вашего вопроса. Мои извинения за следующее:

• Я не рассматривал, как читать измерения из стандартного ввода, как отмечали другие комментаторы.
• Это в первую очередь для C ++.
• Я кодировал это решение только для двух измерений.

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

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

Я не видел расширений компилятора, упомянутых в других ответах, например, предоставляемых GCC / G ++ для объявления многомерных массивов с динамическими границами так же, как вы делаете со статическими границами. Из того, что я понимаю, вопрос не ограничивает ответы стандартным C / C ++. ISO C99, очевидно, поддерживает их, но в C ++ и предыдущих версиях C они представляются расширениями, специфичными для компилятора. Смотрите этот вопрос: Динамические массивы в C без malloc?

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

template <typename T> 
class Array2D {
private:
    std::unique_ptr<T> managed_array_;
    T* array_;
    size_t x_, y_;

public:
    Array2D(size_t x, size_t y) {
        managed_array_.reset(new T[x * y]);
        array_ = managed_array_.get();
        y_ = y;
    }
    T* operator[](size_t x) const {
        return &array_[x * y_];
    }
};

Вы можете использовать это так. Размеры не

auto a = Array2D<int>(x, y);
a[xi][yi] = 42;

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

Производительность динамических многомерных массивов в C ++

Answer 9

Вы можете использовать malloc для достижения этой цели, и при этом иметь доступ к ней через обычный массив [] [] означает, что метод массива [row * cols + cols].

main()
{
   int i;
   int rows;
   int cols;
   int **array = NULL;

   array = malloc(sizeof(int*) * rows);
   if (array == NULL)
       return 0;  // check for malloc fail

   for (i = 0; i < rows; i++)
   {
       array[i] = malloc(sizeof(int) * cols)
       if (array[i] == NULL)
           return 0;  // check for malloc fail
   }

   // and now you have a dynamically sized array
}

Answer 10

Нет способа определить длину данного массива в C ++. Лучше всего было бы передать длину каждого измерения массива и использовать его вместо свойства .length самого массива.