Ba chiều các số nguyên trong C++

Question

Tôi muốn tìm ra các cách an toàn để triển khai các mảng số nguyên ba chiều trong C++, sử dụng phân bổ bộ nhớ con trỏ/số động, hoặc, sử dụng các kỹ thuật STL như vectơ.

Về cơ bản tôi muốn kích thước mảng số nguyên của tôi trông giống như:

[ x ][ y ][ z ] 

x và y là trong khoảng 20-6000 z được biết đến và bằng 4.

Answer 1

Có một cái nhìn tại Boost multi-dimensional array thư viện. Dưới đây là ví dụ (được điều chỉnh từ tài liệu Tăng cường):

#include "boost/multi_array.hpp" 

int main() { 
    // Create a 3D array that is 20 x 30 x 4 
    int x = 20; 
    int y = 30; 
    int z = 4; 

    typedef boost::multi_array<int, 3> array_type; 
    typedef array_type::index index; 
    array_type my_array(boost::extents[x][y][z]); 

    // Assign values to the elements 
    int values = 0; 
    for (index i = 0; i != x; ++i) { 
    for (index j = 0; j != y; ++j) { 
     for (index k = 0; k != z; ++k) { 
     my_array[i][j][k] = values++; 
     } 
    } 
    } 
} 

Answer 2

Mỗi cặp dấu ngoặc vuông là thao tác dereferencing (khi được áp dụng cho con trỏ). Như một ví dụ, các cặp sau đây của dòng mã tương đương:

x = myArray[4]; 
x = *(myArray+4); 

 

x = myArray[2][7]; 
x = *((*(myArray+2))+7); 

Để sử dụng cú pháp đề nghị của bạn, bạn chỉ đơn giản là dereferencing giá trị trả về từ dereference đầu tiên.

int*** myArray = (some allocation method, keep reading); 
// 
// All in one line: 
int value = myArray[x][y][z]; 
// 
// Separated to multiple steps: 
int** deref1 = myArray[x]; 
int* deref2 = deref1[y]; 
int value = deref2[z]; 

Để đi về phân bổ mảng này, bạn chỉ cần nhận ra rằng bạn không thực sự có mảng ba chiều của số nguyên. Bạn có một mảng các mảng của các số nguyên.

// Start by allocating an array for array of arrays 
int*** myArray = new int**[X_MAXIMUM]; 

// Allocate an array for each element of the first array 
for(int x = 0; x < X_MAXIMUM; ++x) 
{ 
    myArray[x] = new int*[Y_MAXIMUM]; 

    // Allocate an array of integers for each element of this array 
    for(int y = 0; y < Y_MAXIMUM; ++y) 
    { 
     myArray[x][y] = new int[Z_MAXIMUM]; 

     // Specify an initial value (if desired) 
     for(int z = 0; z < Z_MAXIMUM; ++z) 
     { 
      myArray[x][y][z] = -1; 
     } 
    } 
} 

deallocating mảng này sau một quá trình tương tự để phân bổ nó:

for(int x = 0; x < X_MAXIMUM; ++x) 
{ 
    for(int y = 0; y < Y_MAXIMUM; ++y) 
    { 
     delete[] myArray[x][y]; 
    } 

    delete[] myArray[x]; 
} 

delete[] myArray; 

Answer 3

Cần lưu ý rằng, đối với tất cả các tính năng, bạn đang đối phó với chỉ một mảng 2D, bởi vì thứ ba (và ít quan trọng nhất) được biết đến.

Sử dụng STL hoặc Boost là cách tiếp cận khá tốt nếu bạn không biết trước bao nhiêu mục bạn sẽ có trong mỗi thứ nguyên của mảng, vì chúng sẽ cấp cho bạn phân bổ bộ nhớ động và tôi khuyên bạn nên sử dụng một trong các cách tiếp cận này tập dữ liệu của bạn vẫn giữ nguyên phần lớn hoặc nếu chủ yếu chỉ nhận được các mục nhập mới và không bị xóa nhiều. Tuy nhiên, nếu bạn biết điều gì đó về tập dữ liệu của bạn trước, chẳng hạn như khoảng bao nhiêu mục trong tổng số sẽ được lưu trữ hoặc nếu các mảng được phân bổ thưa thớt, bạn có thể sử dụng một số chức năng băm/thùng tốt hơn và sử dụng chỉ mục XYZ làm khóa của bạn. Trong trường hợp này, giả sử không quá 8192 (13 bit) mục cho mỗi thứ nguyên, bạn có thể nhận được bằng một khóa 40 bit (5 byte). Hoặc, giả sử luôn có 4 x mục Z, bạn chỉ cần sử dụng khóa XY 26 bit. Đây là một trong những sự cân bằng hiệu quả hơn giữa tốc độ, mức sử dụng bộ nhớ và phân bổ động.

Answer 4

Với vectơ:

std::vector< std::vector< std::vector<int> > > array3d; 

Mỗi phần tử là wit truy cập array3d [x] [y] [z] nếu các phần tử đã được thêm vào. (ví dụ: thông qua push_back)

Answer 5

Có nhiều lợi ích khi sử dụng STL để quản lý bộ nhớ của bạn bằng cách sử dụng mới/xóa. Việc lựa chọn cách trình bày dữ liệu của bạn phụ thuộc vào cách bạn dự định sử dụng nó.Một gợi ý sẽ là một lớp ẩn đi quyết định triển khai và cung cấp các phương thức get/set ba chiều cho một vector STL một chiều.

Nếu bạn thực sự tin rằng bạn cần tạo loại véc tơ 3D tùy chỉnh, hãy điều tra Tăng cường trước.

// a class that does something in 3 dimensions 

class MySimpleClass 
{ 
public: 

    MySimpleClass(const size_t inWidth, const size_t inHeight, const size_t inDepth) : 
    mWidth(inWidth), mHeight(inHeight), mDepth(inDepth) 
    { 
     mArray.resize(mWidth * mHeight * mDepth); 
    } 


    // inline for speed 
    int Get(const size_t inX, const size_t inY, const size_t inZ) { 
    return mArray[(inZ * mWidth * mHeight) + (mY * mWidth) + mX]; 
    } 

    void Set(const size_t inX, const size_t inY, const size_t inZ, const int inVal) { 
    return mArray[(inZ * mWidth * mHeight) + (mY * mWidth) + mX]; 
    } 

    // doing something uniform with the data is easier if it's not a vector of vectors 
    void DoSomething() 
    { 
    std::transform(mArray.begin(), mArray.end(), mArray.begin(), MyUnaryFunc); 
    } 

private: 

    // dimensions of data 
    size_t mWidth; 
    size_t mHeight; 
    size_t mDepth; 

    // data buffer 
    std::vector<int> mArray; 
}; 

Answer 6

Đề xuất của Pieter là tất nhiên, nhưng một điều bạn cần lưu ý là trong trường hợp mảng lớn xây dựng nó có thể khá chậm. Mỗi lần thay đổi dung lượng vector, tất cả dữ liệu phải được sao chép xung quanh ('n' vec-tơ vectơ).

Answer 7

Dưới đây là cách đơn giản để tạo mảng 3D sử dụng C hoặc C++ trong một đoạn bộ nhớ cho mỗi mảng. Không cần phải sử dụng BOOST (ngay cả khi nó tốt đẹp), hoặc để phân chia phân bổ giữa các dòng với nhiều sự gián đoạn (điều này là khá xấu vì nó thường cho hình phạt hiệu suất lớn khi truy cập dữ liệu và nó mảnh bộ nhớ).

Điều duy nhất cần hiểu là không có những thứ như mảng đa chiều, chỉ mảng của mảng (của mảng). Chỉ số trong cùng là bộ nhớ xa nhất trong bộ nhớ.

#include <stdio.h> 
#include <stdlib.h> 

int main(){ 

    { 
     // C Style Static 3D Arrays 
     int a[10][20][30]; 
     a[9][19][29] = 10; 
     printf("a[9][19][29]=%d\n", a[9][19][29]); 
    } 

    { 
     // C Style dynamic 3D Arrays 
     int (*a)[20][30]; 
     a = (int (*)[20][30])malloc(10*20*30*sizeof(int)); 
     a[9][19][29] = 10; 
     printf("a[9][19][29]=%d\n", a[9][19][29]); 
     free(a); 
    } 

    { 
     // C++ Style dynamic 3D Arrays 
     int (*a)[20][30]; 
     a = new int[10][20][30]; 
     a[9][19][29] = 10; 
     printf("a[9][19][29]=%d\n", a[9][19][29]); 
     delete [] a; 
    } 

} 

Đối với vấn đề thực tế của bạn, vì có thể có hai thứ nguyên không xác định, có vấn đề với đề xuất của tôi tại nó chỉ cho phép một thứ nguyên không xác định. Có một số cách để quản lý điều đó.

Tin tốt là sử dụng các biến hiện hoạt động với C, nó được gọi là các mảng độ dài biến đổi. Bạn nhìn here để biết chi tiết.

int x = 100; 
    int y = 200; 
    int z = 30; 

    { 
     // C Style Static 3D Arrays 
     int a[x][y][z]; 
     a[99][199][29] = 10; 
     printf("a[99][199][29]=%d\n", a[99][199][29]); 
    } 

    { 
     // C Style dynamic 3D Arrays 
     int (*a)[y][z]; 
     a = (int (*)[y][z])malloc(x*y*z*sizeof(int)); 
     a[99][199][29] = 10; 
     printf("a[99][199][29]=%d\n", a[99][199][29]); 
     free(a); 
    } 

Nếu sử dụng C++ cách đơn giản nhất có lẽ là sử dụng toán tử quá tải gắn bó với cú pháp mảng:

{ 
     class ThreeDArray { 
      class InnerTwoDArray { 
       int * data; 
       size_t y; 
       size_t z; 
       public: 
       InnerTwoDArray(int * data, size_t y, size_t z) 
        : data(data), y(y), z(z) {} 

       public: 
       int * operator [](size_t y){ return data + y*z; } 
      }; 

      int * data; 
      size_t x; 
      size_t y; 
      size_t z; 
      public: 
      ThreeDArray(size_t x, size_t y, size_t z) : x(x), y(y), z(z) { 
       data = (int*)malloc(x*y*z*sizeof data); 
      } 

      ~ThreeDArray(){ free(data); } 

      InnerTwoDArray operator [](size_t x){ 
       return InnerTwoDArray(data + x*y*z, y, z); 
      } 
     }; 

     ThreeDArray a(x, y, z); 
     a[99][199][29] = 10; 
     printf("a[99][199][29]=%d\n", a[99][199][29]); 
    } 

Đoạn mã trên có một số chi phí gián tiếp để truy cập InnerTwoDArray (nhưng một trình biên dịch tốt có lẽ có thể tối ưu hóa nó đi) nhưng chỉ sử dụng một bộ nhớ cho mảng được cấp phát trên heap. Đó thường là lựa chọn hiệu quả nhất.

Rõ ràng ngay cả khi mã trên vẫn đơn giản và dễ hiểu, STL hoặc BOOST làm tốt, do đó không cần phải phát minh lại bánh xe. Tôi vẫn tin rằng nó là thú vị để biết nó có thể dễ dàng thực hiện.