如何在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语言的最佳选择是像Guge所说的那样使用单维数组，“您可以为rowscols sizeof（int）分配内存，并通过table [row * cols + col]访问它。”

C ++中有许多选择，如果你真的喜欢boost或stl，那么下面的答案可能更可取，但最简单且可能最快的选择是像C语言一样使用单维数组。

如果您想要[][]语法，则在底部的lillq回答中还有另一个可行的选择，即手动使用大量malloc构建数组。

- Ari Ronen

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

你可以看到，要访问数组中的一个元素非常容易：只需像以下函数一样使用操作符()：

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中编译此应用程序的，只得到了一些容易被忽略的警告。

- Klaim

---

这是为C++设计的。 - Johannes Schaub - litb

你还应该展示如何从std::cin中读取尺寸（正如问题中所要求的）。 - Martin York

你说得对！我添加了一个示例应用程序。如果不够清晰，请告诉我 :) - Klaim

可以直接使用int类型作为索引，而不必使用“typedef array_type :: index index”吗？ - Timothy

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] = buffer + 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];
    }
}

记住的规则

计算机内存是线性的，并且在很长一段时间内仍然如此。请记住，计算机不原生支持二维数组，所以唯一的方法是将数组“线性化”为一维数组。

- Vincent Robert

---

你可能是指第二个例子中的： array[i] = buffer + i * 4; - Viaceslavus

你可能是指第二个例子中的： array[i] = buffer + i * 4; - undefined

Answer 3

以下是使用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落后了15年。而且这种情况不会很快改变（C++17的可变长度数组提案远不能接近C99可变长度数组的功能）。

- cmaster - reinstate monica

Answer 4

你可以分配rows列大小为int的空间，并通过table[row*cols+col]访问它。

- Guge

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。例如，所有内存不是在一个块中分配的，而是为每一列分别分配的。此外，行不必全部具有相同的宽度。更快的方法是使用普通向量，然后通过索引计算类似于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;

由于您无法从指针中获取创建的列和行的数量，因此必须将其存储在某个地方。

- litb

---

嵌套的<vector>是实现自动管理的Ileffe向量的标准方法。对于不规则数组，嵌套的<vector>不仅是最简单的方法，也是最少头疼的方法。 - moshbear

Answer 6

C和C++中的2D C风格数组是一个大小为rows * columns * sizeof(datatype)字节的内存块。

实际的[row][column]维度只存在于编译时静态地。在运行时没有动态内容！

因此，正如其他人已经提到的，您可以实现

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

- Mr.Ree

Answer 7

如果您使用的是C语言而不是C ++，您可能想查看Dave Hanson图书馆C接口和实现中的Array_T抽象。它非常干净和设计良好。我让我的学生做一个二维版本作为练习。您可以这样做，或者只需编写一个附加函数来执行索引映射，例如：

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

“将宽度、高度和元素指针存储在单独的结构中会使代码更加清晰。”

- Norman Ramsey

Answer 8

我最近遇到了类似的问题。我没有Boost可用。与普通数组相比，向量的向量在速度上表现得相当慢。使用指针数组使初始化变得更加费力，因为您必须遍历每个维度并初始化指针，可能会在此过程中拥有一些非常笨重的级联类型，可能带有大量的typedef。

免责声明：我不确定是否应将此发布为答案，因为它仅回答了您问题的一部分。对于以下内容，我深感抱歉：

• 我没有涵盖如何从标准输入读取维度，因为其他评论者已经提到了这一点。
• 这主要适用于C++。
• 我只为两个维度编写了此解决方案。

尽管如此，我还是决定发布这篇文章，因为我经常看到在C++中关于多维数组的问题中，人们经常提到向量的向量，而没有任何人提到其性能方面（如果您关心的话）。

我还理解了这个问题的核心问题是如何获得可以像问题中的Java示例那样轻松使用的动态多维数组，即无需计算具有伪多维一维数组的索引。

我没有在其他回答中看到编译器扩展的提及，例如GCC/G++提供的声明多维数组具有动态边界的方式与静态边界相同。据我所知，该问题并不限制答案为标准C/C++。 ISO C99显然支持它们，但在C ++和早期版本的C中，它们似乎是特定于编译器的扩展。请参见此问题：Dynamic arrays in C without 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 ++中动态多维数组的性能

- user2880576

---

这个是否按行对齐元素？这对于缓存优化访问非常重要，大多数程序员会认为x在空间上是相邻的。另一种选择是在代码中的所有位置切换x，y，包括使用“a[yi][xi]”，这对程序员来说不直观，但对数学家来说恰到好处 ;) - hobb

非常感谢您指出这一点！内存通常应该按照顺序布局，因此现代硬件可以预测访问。关于这个问题，SO上最受欢迎的与性能相关的问题之一正是关于这个问题的：https://dev59.com/iWgu5IYBdhLWcg3wkH6P - user2880576

Answer 9

你可以使用malloc来实现这一点，并且仍然可以通过正常的array[][]方式访问它，而不是使用array[rows * 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
}

- Lane

Answer 10

在C++中，没有办法确定给定数组的长度。最好的方法可能是传递数组每个维度的长度，并使用它来代替数组本身的.length属性。

- Andy