C++ で非常に大きな 2D 配列を回避する方法
質問
サイズ 800x800 の 2D int 配列を作成する必要があります。ただし、そうするとスタック オーバーフローが発生します (笑)。
C++ は初めてなので、ベクトルのベクトルのようなことをすべきでしょうか?そして、2次元配列をクラスにカプセル化するだけですか?
具体的には、この配列はグラフィックス プログラムの zbuffer です。画面上のすべてのピクセルの Z 値を保存する必要があります (したがって、800x800 という大きなサイズになります)。
ありがとう!
解決
約 2.5 メガが必要なので、ヒープを使用するだけで問題ありません。サイズを変更する必要がない限り、ベクターは必要ありません。見る C++ FAQ Lite 「2D」ヒープ配列の使用例については、「2D」ヒープ配列の使用例を参照してください。
int *array = new int[800*800];
(忘れずに delete[]
終わったらそれでいいよ。)
他のヒント
これまでのすべての投稿では、メモリ管理はプログラマに委ねられています。これは避けられるし、避けるべきです。ReaperUnreal は、配列ではなくベクトルを使用し、ディメンション テンプレート パラメータを作成し、アクセス関数を変更する点を除いて、私がやろうとしていることに非常に近いです。そして、ああ、IMNSHO が少し物事を整理しています。
template <class T, size_t W, size_t H>
class Array2D
{
public:
const int width = W;
const int height = H;
typedef typename T type;
Array2D()
: buffer(width*height)
{
}
inline type& at(unsigned int x, unsigned int y)
{
return buffer[y*width + x];
}
inline const type& at(unsigned int x, unsigned int y) const
{
return buffer[y*width + x];
}
private:
std::vector<T> buffer;
};
これで、この 2 次元配列をスタックに適切に割り当てることができます。
void foo()
{
Array2D<int, 800, 800> zbuffer;
// Do something with zbuffer...
}
これがお役に立てば幸いです!
編集:から配列指定を削除しました Array2D::buffer
. 。それを見つけてくれたアンドレアスに感謝します!
ただし、ケビンの例は優れています。
std::vector<T> buffer[width * height];
そうあるべきです
std::vector<T> buffer;
これを少し拡張すると、at() 関数の代わりに演算子オーバーロードを追加することもできます。
const T &operator()(int x, int y) const
{
return buffer[y * width + x];
}
そして
T &operator()(int x, int y)
{
return buffer[y * width + x];
}
例:
int main()
{
Array2D<int, 800, 800> a;
a(10, 10) = 50;
std::cout << "A(10, 10)=" << a(10, 10) << std::endl;
return 0;
}
ベクトルのベクトルを実行することもできますが、オーバーヘッドが発生します。Z バッファの場合、より一般的な方法は、サイズ 800*800=640000 の配列を作成することです。
const int width = 800;
const int height = 800;
unsigned int* z_buffer = new unsigned int[width*height];
次に、次のようにピクセルにアクセスします。
unsigned int z = z_buffer[y*width+x];
800*800 の 1 次元配列を作成するかもしれません。おそらく、800 個の個別のベクトルを割り当てるよりも、このように単一の割り当てを使用する方が効率的です。
int *ary=new int[800*800];
次に、それを 2D 配列のように動作するクラスにカプセル化します。
class _2DArray
{
public:
int *operator[](const size_t &idx)
{
return &ary[idx*800];
}
const int *operator[](const size_t &idx) const
{
return &ary[idx*800];
}
};
ここで示した抽象化には多くの穴があります。たとえば、「行」の終わりを超えてアクセスするとどうなるでしょうか?『Effective C++』という本には、C++ で優れた多次元配列を作成する方法について非常に詳しく説明されています。
できることの 1 つは、VC を使用してスタック サイズを変更することです (本当にスタック上に配列が必要な場合)。これを行うためのフラグは [/F](http://msdn.microsoft.com/en-us/library/tdkhxaks(VS.80).aspx).
しかし、おそらくあなたが望む解決策は、メモリをスタックではなくヒープに置くことです。そのためには、 vector
の vectors
.
次の行は、 vector
800 個の要素からなり、各要素は vector
800のうち int
これにより、メモリを手動で管理する手間が省けます。
std::vector<std::vector<int> > arr(800, std::vector<int>(800));
2 つの閉じ山かっこ間のスペースに注意してください (> >
) これは、右シフト演算子とのあいまいさをなくすために必要です (これは、 C++0x).
または、次のようなことを試すこともできます。
boost::shared_array<int> zbuffer(new int[width*height]);
これも引き続き実行できるはずです。
++zbuffer[0];
メモリ管理について心配する必要はなくなり、カスタム クラスを管理する必要もなく、簡単に使い回すことができます。
C のような方法があります。
const int xwidth = 800;
const int ywidth = 800;
int* array = (int*) new int[xwidth * ywidth];
// Check array is not NULL here and handle the allocation error if it is
// Then do stuff with the array, such as zero initialize it
for(int x = 0; x < xwidth; ++x)
{
for(int y = 0; y < ywidth; ++y)
{
array[y * xwidth + x] = 0;
}
}
// Just use array[y * xwidth + x] when you want to access your class.
// When you're done with it, free the memory you allocated with
delete[] array;
をカプセル化できます y * xwidth + x
簡単な get メソッドと set メソッドを備えたクラス内で (おそらくオーバーロードを使用して) []
より高度な C++ を使い始めたい場合は、演算子を使用してください)。ただし、C++ を始めたばかりで、n 次元配列用の再利用可能な完全なクラス テンプレートの作成に着手しない場合は、ゆっくりとこれに到達することをお勧めします。これは、開始時に混乱するだけです。
グラフィックスの作業を開始すると、追加のクラス呼び出しによるオーバーヘッドによってコードの速度が低下する可能性があることに気づくかもしれません。ただし、アプリケーションの速度が十分でなく、不必要な複雑さの可能性によって最初から使いにくくなるのではなく、アプリケーションをプロファイリングして、どこで時間が失われているかを示すことができるまでは、これについて心配する必要はありません。
このような情報については、C++ lite FAQ が最適であることがわかりました。特にあなたの質問には次のように答えられます。
http://www.parashift.com/c++-faq-lite/freestore-mgmt.html#faq-16.16
静的ストレージ (ファイルのスコープ内) に配列を割り当てることも、追加することもできます。 static
インスタンスが 1 つだけ必要な場合は、関数スコープ内の修飾子)。
int array[800][800];
void fn()
{
static int array[800][800];
}
この方法では、スタックに保存されず、動的メモリを扱う必要がなくなります。
そうですね、Niall Ryan が始めたことに基づいて、パフォーマンスが問題になる場合は、数学を最適化し、これをクラスにカプセル化することで、これをさらに一歩進めることができます。
それでは、少し数学から始めましょう。800 は 2 のべき乗で次のように書けることを思い出してください。
800 = 512 + 256 + 32 = 2^5 + 2^8 + 2^9
したがって、アドレッシング関数は次のように記述できます。
int index = y << 9 + y << 8 + y << 5 + x;
したがって、すべてを適切なクラスにカプセル化すると、次のようになります。
class ZBuffer
{
public:
const int width = 800;
const int height = 800;
ZBuffer()
{
for(unsigned int i = 0, *pBuff = zbuff; i < width * height; i++, pBuff++)
*pBuff = 0;
}
inline unsigned int getZAt(unsigned int x, unsigned int y)
{
return *(zbuff + y << 9 + y << 8 + y << 5 + x);
}
inline unsigned int setZAt(unsigned int x, unsigned int y, unsigned int z)
{
*(zbuff + y << 9 + y << 8 + y << 5 + x) = z;
}
private:
unsigned int zbuff[width * height];
};