C++ の整数の 3 次元配列
https://stackoverflow.com/questions/62512
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
C++ で整数の 3 次元配列を実装する安全な方法、ポインター算術/動的メモリ割り当て、または代わりに使用する方法を見つけたいと考えています。 STL ベクターなどの技術。
基本的に、整数配列の次元を次のようにしたいと考えています。
[ x ][ y ][ z ]
xとyは20〜6000 zの範囲内で、4に等しい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++ を使用して、各配列の 1 つのメモリ チャンクに 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;
}
}
実際の問題では、2 つの未知の次元が存在する可能性があるため、未知の次元を 1 つだけ許可するという私の提案には問題があります。それを管理する方法はいくつかあります。
良いニュースとして、変数の使用が 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 にアクセスするための間接コストがいくらかあります (ただし、優れたコンパイラーはおそらくそれを最適化して取り除くことができます) が、ヒープに割り当てられた配列にメモリ チャンクを 1 つだけ使用します。通常、これが最も効率的な選択です。
明らかに、上記のコードがまだシンプルで簡単な場合でも、STL または BOOST は適切に機能するため、車輪を再発明する必要はありません。それが簡単にできるのは面白いと今でも思っています。
ベクトルの場合:
std::vector< std::vector< std::vector< int > > > array3d;
要素がすでに追加されている場合は、すべての要素に array3d[x][y][z] を使用してアクセスできます。（例えば。Push_back経由)
3 番目の (最下位の) 次元がわかっているため、どのような意味でも、扱うのは 2D 配列だけであることに注意してください。
STL または Boost を使用することは、配列の各次元にいくつのエントリがあるか事前にわからない場合に非常に優れたアプローチです。動的メモリ割り当てが提供されるためです。データ セットが次の場合には、これらのアプローチのいずれかを推奨します。ほとんど静的なままにするか、またはほとんど新しいエントリのみを受け取り、削除はあまり行わない場合。
ただし、合計でおおよその項目数が保存されるか、配列にまばらにデータが格納されるかなど、データセットについて事前にわかっている場合は、ある種のハッシュ/バケット関数を使用した方がよい場合があります。 XYZ インデックスをキーとして使用します。この場合、次元あたりのエントリ数が 8192 (13 ビット) 未満であると仮定すると、40 ビット (5 バイト) キーで対処できます。または、常に 4 x Z エントリがあると仮定すると、単純に 26 ビット XY キーを使用することになります。これは、速度、メモリ使用量、動的割り当ての間のより効率的なトレードオフの 1 つです。
STL を使用してメモリを管理すると、new/delete を使用するよりも多くの利点があります。データを表現する方法の選択は、データの使用方法によって異なります。1 つの提案は、実装の決定を隠し、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' 個のベクトルのベクトル) コピーする必要があります。
