Как работать с очень большим 2d-массивом в C ++
Вопрос
Мне нужно создать 2D-массив int размером 800x800.Но это приводит к переполнению стека (ха-ха).
Я новичок в C ++, так должен ли я сделать что-то вроде вектора векторов?И просто инкапсулировать 2d-массив в класс?
В частности, этот массив является моим zbuffer в графической программе.Мне нужно сохранить значение z для каждого пикселя на экране (отсюда и большой размер 800x800).
Спасибо!
Решение
Вам нужно около 2,5 мегабайт, так что просто использовать кучу должно быть нормально.Вам не нужен вектор, если только вам не нужно изменить его размер.Видишь C ++ FAQ Lite для примера использования "2D" массива кучи.
int *array = new int[800*800];
(Не забудьте delete[]
это когда ты закончишь.)
Другие советы
До сих пор каждое сообщение оставляло управление памятью за программистом.Этого можно и нужно избегать.ReaperUnreal чертовски близок к тому, что я бы сделал, за исключением того, что я бы использовал вектор, а не массив, а также создал параметры шаблона dimensions и изменил функции доступа - и, о, просто мне нужно немного почистить:
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;
};
Теперь вы можете разместить этот двумерный массив в стеке просто отлично:
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.Вероятно, более эффективно использовать одно распределение, подобное этому, вместо выделения 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];
}
};
Показанная здесь абстракция имеет много пробелов, например, что произойдет, если вы получите доступ к out после конца "строки"?В книге "Эффективный C ++" довольно хорошо обсуждается написание хороших многомерных массивов на C ++.
Одна вещь, которую вы можете сделать, это изменить размер стека (если вам действительно нужен массив в стеке) с помощью VC. Флаг для этого - [/ F](http://msdn.microsoft.com/en-us/library/tdkhxaks (ПРОТИВ.80).aspx).
Но решение, которое вы, вероятно, хотите, состоит в том, чтобы поместить память в кучу, а не в стек, для этого вам следует использовать vector
из vectors
.
В следующей строке объявляется vector
из 800 элементов каждый элемент представляет собой vector
из 800 int
s и избавляет вас от необходимости управлять памятью вручную.
std::vector<std::vector<int> > arr(800, std::vector<int>(800));
Обратите внимание на расстояние между двумя закрывающими угловыми скобками (> >
), который необходим для того, чтобы устранить неоднозначность с помощью оператора сдвига вправо (который больше не будет нужен в 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 (возможно, с перегрузкой []
operator, если вы хотите начать осваивать более продвинутый C ++).Я бы рекомендовал подходить к этому медленно, хотя, если вы только начинаете с C ++ и не начинаете создавать повторно используемые полностью классовые шаблоны для n-размерных массивов, которые просто собьют вас с толку, когда вы начнете.
Как только вы приступите к графической работе, вы можете обнаружить, что накладные расходы, связанные с вызовами дополнительных классов, могут замедлить работу вашего кода.Однако не беспокойтесь об этом до тех пор, пока ваше приложение не станет недостаточно быстрым, и вы сможете профилировать его, чтобы показать, где теряется время, вместо того, чтобы усложнять его использование с самого начала с возможной ненужной сложностью.
Я обнаружил, что FAQ по C ++ lite отлично подходит для получения подобной информации.В частности, на ваш вопрос отвечает:
http://www.parashift.com/c++-faq-lite/freestore-mgmt.html#faq-16.16
Вы можете разместить массив в статическом хранилище (в области видимости файла или добавить static
квалификатор в области действия функции), если вам нужен только один экземпляр.
int array[800][800];
void fn()
{
static int array[800][800];
}
Таким образом, он не попадет в стек, и вам не придется иметь дело с динамической памятью.
Что ж, основываясь на том, что начал Найл Райан, если производительность является проблемой, вы можете сделать еще один шаг вперед, оптимизировав математику и инкапсулировав это в класс.
Итак, мы начнем с небольшой математики.Напомним , что 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];
};