Как работать с очень большим 2d-массивом в C ++

Question

Мне нужно создать 2D-массив int размером 800x800.Но это приводит к переполнению стека (ха-ха).

Я новичок в C ++, так должен ли я сделать что-то вроде вектора векторов?И просто инкапсулировать 2d-массив в класс?

В частности, этот массив является моим zbuffer в графической программе.Мне нужно сохранить значение z для каждого пикселя на экране (отсюда и большой размер 800x800).

Спасибо!

Answer 1

Вам нужно около 2,5 мегабайт, так что просто использовать кучу должно быть нормально.Вам не нужен вектор, если только вам не нужно изменить его размер.Видишь C ++ FAQ Lite для примера использования "2D" массива кучи.

int *array = new int[800*800];

(Не забудьте delete[] это когда ты закончишь.)

Answer 2

До сих пор каждое сообщение оставляло управление памятью за программистом.Этого можно и нужно избегать.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.Спасибо Андреасу за то, что уловил это!

Answer 3

Однако пример Кевина хорош:

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;
}

Answer 4

Вы могли бы создать вектор векторов, но это повлекло бы за собой некоторые накладные расходы.Для 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];

Answer 5

Я мог бы создать массив с одним размером 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 ++.

Answer 6

Одна вещь, которую вы можете сделать, это изменить размер стека (если вам действительно нужен массив в стеке) с помощью VC. Флаг для этого - [/ F](http://msdn.microsoft.com/en-us/library/tdkhxaks (ПРОТИВ.80).aspx).

Но решение, которое вы, вероятно, хотите, состоит в том, чтобы поместить память в кучу, а не в стек, для этого вам следует использовать vector из vectors.

В следующей строке объявляется vector из 800 элементов каждый элемент представляет собой vector из 800 ints и избавляет вас от необходимости управлять памятью вручную.

std::vector<std::vector<int> > arr(800, std::vector<int>(800));

Обратите внимание на расстояние между двумя закрывающими угловыми скобками (> >), который необходим для того, чтобы устранить неоднозначность с помощью оператора сдвига вправо (который больше не будет нужен в C++0x).

Answer 7

Или вы могли бы попробовать что-то вроде:

boost::shared_array<int> zbuffer(new int[width*height]);

Вы все равно должны быть в состоянии сделать и это тоже:

++zbuffer[0];

Больше не нужно беспокоиться об управлении памятью, не нужно заботиться о пользовательских классах, и ими легко разбрасываться.

Answer 8

Есть 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

Answer 9

Вы можете разместить массив в статическом хранилище (в области видимости файла или добавить static квалификатор в области действия функции), если вам нужен только один экземпляр.

int array[800][800];

void fn()
{
    static int array[800][800];
}

Таким образом, он не попадет в стек, и вам не придется иметь дело с динамической памятью.

Answer 10

Что ж, основываясь на том, что начал Найл Райан, если производительность является проблемой, вы можете сделать еще один шаг вперед, оптимизировав математику и инкапсулировав это в класс.

Итак, мы начнем с небольшой математики.Напомним , что 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];
};