如何在C / C ++中最好地处理dynamicmultidimensional array?

在C和/或C ++中操纵dynamic(所有维度在运行时间之前都是未知的)的multidimensional array是什么被接受/最常用的方法。

我试图find最干净的方法来完成这个Java代码的function:

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中读取只是为了阐明直到运行时才知道维度)。

编辑:我注意到,这个问题是相当stream行,即使它是相当古老。 我实际上并不同意顶尖的投票答案。 我认为C的最佳select是使用一个单维数组,如下面的Guge所说:“你可以分配行cols sizeof(int)并通过table [row * cols + col]来访问它”。

C ++有很多select,如果你真的喜欢boost或stl,那么下面的答案可能会更好,但最简单也可能是最快的select是使用C中的单维数组。

在C和C ++中另一个可行的select,如果你想[] []语法是lillq的答案在底部是手动构build有很多malloc的数组。

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

编辑:正如在评论中所build议的, 这里是一个“简单的”示例应用程序,它允许您在运行时定义multidimensional array大小,从控制台input询问。 下面是这个示例应用程序的示例输出(用常量编译为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 

代码中的重要部分是我们从用户获取维度的主要function,并通过以下方式创build数组:

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

你可以看到要inheritance数组中的一个元素,这很容易:你只需要像下面的函数那样使用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中编译这个应用程序 – 得到一些遗忘的警告。

有两种方法可以用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]; } } 

这个方法的问题在于你的第二个维度被分配了许多数组,所以不能简化内存分配器的工作。 你的记忆很可能是分散的,导致性能较差。 它提供了更多的灵活性,因为第二维中的每个数组可以有不同的大小。

大数组来保存所有的值

这里的技巧是创build一个海量数组来保存您所需要的每个数据。 困难的部分是,如果你想能够使用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]; } } 

要牢记的规则

计算机的内存是线性的,并且仍然是很长一段时间。 请记住,2维数组本身并不支持在计算机上,所以唯一的方法是将数组“线性化”为1维数组。

你可以分配行cols sizeof(int)并通过table [row * cols + col]来访问它。

不使用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]索引向量的能力。 您还必须在某处存储行数和列数,而在使用嵌套解决scheme时,可以使用v.size()获取行数,并使用v[0].size() v.size()获取列v[0].size()

使用boost,你可以使用boost::multi_array ,这正是你想要的(见另一个答案)。


还有使用本地C ++数组的原始方式。 这涉及相当多的工作,并没有比嵌套的vector解决scheme更好:

 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; 

您必须存储您在某处创build的列和行的数量,因为您无法从指针接收它们。

这是在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 ++要求数组types的大小是编译时间常量。 在这方面,C ++现在比C慢十五年。这种情况不会很快发生变化(C ++ 17的可变长度数组提议并不接近C99可变长度数组的function)。

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

实际的[row] [column]维仅在编译时静态存在。 在运行时没有任何dynamic的!

所以,正如其他人所说,你可以执行

  int array [ rows ] [ columns ]; 

如:

  int array [ rows * columns ] 

或者如:

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

Next:声明一个可变大小的数组。 在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 ++中是不可能的。 您需要使用dynamic分配来分配数组,例如:

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

或者优选(具有自动化存储器pipe理)

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

如果您使用的是C而不是C ++,则可能需要查看Dave Hanson库C Interfaces and Implementations中的Array_T抽象。 这是非常干净和精心devise。 我有我的学生做一个二维版本的练习。 你可以做到这一点,或者只是写一个额外的function,做一个索引映射,例如,

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

在存储宽度,高度和指向元素的指针的地方有一个单独的结构,这样会更清洁些。

我最近遇到了类似的问题。 我没有提供Boost。 与普通数组相比,向量的vector结果相当慢。 有一个指针数组会使得初始化变得非常麻烦,因为你必须遍历每一个维度并初始化指针,在这个过程中可能有一些相当笨重的级联types,可能会有很多typedef。

免责声明:我不确定是否应该发表这个答案,因为它只回答你的问题的一部分。 我对以下事项表示歉意:

  • 正如其他评论家所说,我没有涉及如何从标准input中读取维度。
  • 这主要是针对C ++的。
  • 我只编码这个解决scheme的两个维度。

无论如何,我决定发布这个,因为我看到经常出现的vector向量回答有关C ++multidimensional array的问题,没有任何人提及它的性能方面(如果你关心的话)。

我还解释了这个问题的核心问题是如何获得dynamicmultidimensional array,可以像Java示例一样轻松地使用这个问题,也就是说,没有必须用伪代码计算索引的麻烦,多维一维数组。

我没有看到在其他答案中提到的编译器扩展,就像GCC / G ++提供的那样,用dynamic边界声明multidimensional array的方式与静态边界相同。 从我的理解,这个问题并不限制标准C / C ++的答案。 ISO C99显然确实支持它们,但是在C ++和C的早期版本中,它们似乎是编译器特定的扩展。 看到这个问题: dynamic数组在C中没有malloc?

我想出了一种人们可能喜欢C ++的方式,因为它的代码很less,内置静态multidimensional array的使用方便,而且速度也一样快。

 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; 

您可以添加一个断言,至less除了最后一个维度之外,还可以将这个想法扩展到两个以上的维度。 我在博客上发表了一篇关于获得multidimensional array的替代方法。 我对这里的相关性能和编码工作也更加具体。

dynamicmultidimensional array在C ++中的性能

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

你可以使用malloc来实现这个function,并且仍然可以通过正常的数组[] []来表示数组[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 }