C++의 3차원 정수 배열
-
09-06-2019 - |
문제
포인터 산술/동적 메모리 할당을 사용하거나 대안으로 C++에서 정수의 3차원 배열을 구현하는 안전한 방법을 찾고 싶습니다. STL
벡터와 같은 기술.
본질적으로 정수 배열 크기는 다음과 같습니다.
[ x ][ y ][ z ]
X와 Y는 범위에 있으며 20-6000 z는 알려져 있으며 4와 같습니다.
해결책
부스트를 살펴보세요 다차원 배열 도서관.다음은 예입니다(Boost 문서에서 수정됨).
#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++;
}
}
}
}
다른 팁
각 대괄호 쌍은 역참조 작업입니다(포인터에 적용되는 경우).예를 들어, 다음 코드 줄 쌍은 동일합니다.
x = myArray[4];
x = *(myArray+4);
x = myArray[2][7];
x = *((*(myArray+2))+7);
제안된 구문을 사용하려면 첫 번째 역참조에서 반환된 값을 역참조하기만 하면 됩니다.
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];
이 배열을 할당하려면 실제로 정수의 3차원 배열이 없다는 점만 인식하면 됩니다.정수 배열의 배열이 있습니다.
// 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;
}
}
}
이 배열의 할당을 취소하는 과정은 할당하는 과정과 유사합니다.
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;
다음은 각 배열에 대한 단일 메모리 청크에서 C 또는 C++를 사용하여 3D 배열을 만드는 간단한 방법입니다.BOOST를 사용하거나(좋더라도) 여러 간접 참조로 라인 간에 할당을 분할할 필요가 없습니다(이는 일반적으로 데이터에 액세스할 때 큰 성능 저하를 초래하고 메모리를 조각화하므로 상당히 나쁩니다).
이해해야 할 유일한 것은 다차원 배열이라는 것이 없고 단지 배열의 배열(배열의)이라는 것입니다.가장 안쪽 인덱스는 메모리에서 가장 멀리 떨어져 있습니다.
#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;
}
}
실제 문제의 경우 알 수 없는 차원이 두 개 있을 수 있으므로 알 수 없는 차원을 하나만 허용한다는 제안에 문제가 있습니다.이를 관리하는 방법에는 여러 가지가 있습니다.
좋은 소식은 변수를 사용하는 것이 이제 C에서 작동한다는 것입니다. 이를 가변 길이 배열이라고 합니다.당신은 보인다 여기 자세한 내용은.
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);
}
C++를 사용하는 경우 가장 간단한 방법은 아마도 연산자 오버로딩을 사용하여 배열 구문을 고수하는 것입니다.
{
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]);
}
위의 코드에는 InnerTwoDArray에 액세스하는 데 약간의 간접 비용이 있지만(그러나 좋은 컴파일러는 이를 최적화할 수 있음) 힙에 할당된 배열에 대해 하나의 메모리 청크만 사용합니다.일반적으로 가장 효율적인 선택입니다.
분명히 위의 코드가 여전히 간단하고 간단하더라도 STL이나 BOOST가 잘 작동하므로 바퀴를 다시 만들 필요가 없습니다.나는 그것이 쉽게 이루어질 수 있다는 것을 아는 것이 여전히 흥미롭다고 믿습니다.
벡터의 경우:
std::vector< std::vector< std::vector< int > > > array3d;
요소가 이미 추가된 경우 모든 요소는 array3d[x][y][z]로 액세스할 수 있습니다.(예:push_back을 통해)
모든 의도와 목적을 위해 세 번째(최하위) 차원이 알려져 있기 때문에 2D 배열만 다루고 있다는 점에 유의해야 합니다.
STL 또는 Boost를 사용하는 것은 배열의 각 차원에 얼마나 많은 항목이 있는지 미리 알 수 없는 경우 매우 좋은 접근 방식입니다. 왜냐하면 동적 메모리 할당을 제공하기 때문입니다. 데이터 세트가 다음과 같은 경우 이러한 접근 방식 중 하나를 권장합니다. 대체로 정적으로 유지하거나 대부분 새 항목만 수신하고 삭제를 많이 받지 않는 경우입니다.
그러나 대략적인 총 항목 수 등 데이터 세트에 대해 미리 알고 있거나 배열이 드물게 채워지는 경우 일종의 해시/버킷 기능을 사용하는 것이 더 나을 수 있습니다. XYZ 인덱스를 키로 사용합니다.이 경우 차원당 항목 수가 8192(13비트) 이하라고 가정하면 40비트(5바이트) 키를 사용하면 됩니다.또는 항상 4개의 x Z 항목이 있다고 가정하면 간단히 26비트 XY 키를 사용하면 됩니다.이는 속도, 메모리 사용량 및 동적 할당 간의 보다 효율적인 절충 중 하나입니다.
STL을 사용하여 메모리를 관리하면 새로 만들기/삭제를 사용하는 것보다 많은 이점이 있습니다.데이터를 표현하는 방법은 데이터 사용 방법에 따라 선택됩니다.한 가지 제안은 구현 결정을 숨기고 1차원 STL 벡터에 3차원 get/set 메서드를 제공하는 클래스입니다.
사용자 정의 3D 벡터 유형을 만들어야 한다고 정말로 생각한다면 먼저 Boost를 조사해 보세요.
// 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;
};
물론 Pieter의 제안은 좋지만 명심해야 할 한 가지는 대규모 배열을 구축하는 경우 상당히 느릴 수 있다는 것입니다.벡터 용량이 변경될 때마다 모든 데이터를 복사해야 합니다(벡터의 'n' 벡터).