C / C ++: «Сетка [x + y * ширина]» против «Сетка [x] [y]»

Question

Это очень специфично и почти не имеет последствий, но мне всегда удавалось беспокоить меня только потому, что я не знал, что будет лучше.Я надеюсь, что вы, ребята, поможете мне остановиться на одном:

Something ** grid; grid[x][y];
Something *  grid; grid[x + y * width];

Я знаю, что любой, кто запрограммировал, должен был создать двумерный массив в какой-то момент.Что вы выбрали и что заставило вас пойти по этому пути?Или, может быть, вы вообще использовали другую форму?

Answer 1

Обычно второй метод предпочтителен по ряду причин:

• Одиночное умножение немного быстрее, чем дополнительное разыменование массива
• Поддержание непрерывности массива также незначительно увеличивает скорость из-за попаданий в кэш
• Во многих случаях, например при загрузке растрового файла или при работе с поверхностями DirectX / OpenGL, необходимо сохранять 2D-поверхность в одном непрерывном блоке памяти.
• Требуется только одно выделение / освобождение массива
• Как правило, с указателями легче иметь дело, чем с указателями на указатели

---

Как уже упоминалось несколькими другими, если вы знаете ширину во время компиляции, объявление переменной как int grid[][width] даст вам все перечисленные преимущества с более приятным синтаксисом. Очевидно, что если ширина является динамической, это не вариант.

Answer 2

В C я бы использовал typedef Something grid_t[][width]; grid[y][x] (обратите внимание на порядок и явный размер массива). Я предпочитаю не использовать зубчатый массив Something **grid.

В C ++ я бы использовал grid.get(x, y), и внутри реализации был бы любой из них, поэтому я могу легко переключаться на лучшее представление при необходимости (например, треугольные матрицы). Скорее всего, я бы начал с std::vector<Something>(height * width) для хранения фактических данных.

Answer 3

в первом случае вы должны создать новый указатель для каждого "x", во втором случае вы сразу же выделите память, мой выбор:

Что-то * grid;grid [x + y * width];

меньше вероятность ошибок, например, нарушение доступа, когда вы забыли создать сетку подмассива [x] с некоторыми x

Answer 4

Вы можете пойти любым путем с этим, как вам угодно (при условии, что вы буквально не подразумеваете, что оно определено как что-то ** решетка, см. Ответы ultor или Sjoerd).Первый обычно легче набрать, второй дает вам больше гибкости и контроля.Большую часть времени они будут вырабатывать одни и те же инструкции, поэтому в некоторой степени это сводится к личным привычкам печатания и кодирования, удобочитаемости, удобству обслуживания и т. Д.

Answer 5

В первой форме массив не должен быть прямоугольным, то есть каждая «строка» может иметь разный размер.Я бы вообще предпочел второе, если нет конкретной причины для отдельной обработки каждой строки.Он более эффективен в отношении памяти, кешируется, быстрее.

Конкретный пример этого преимущества - создание копии массива.Это единственный memcpy (), использующий вторую форму, но намного сложнее с первой.

Для C ++ также существует Boost.MultiArray

Answer 6

Используйте вторую форму:

• LAPACK / CBLAS и большинству других внешних библиотек требуется вторая форма.
• Представление более компактно [избегает дополнительного вектора указателей, как в первом случае]
• Представление быстрее (grid [x] [y] требует двух разыменований указателя, а не одного)
• malloc проще в работе [нет необходимости выполнять два шага для malloc]

для непрерывного доступа, версия с одним массивом более эффективна. для произвольного доступа версия с одним массивом все еще более эффективна [требуется только разыменование указателя]

Answer 7

У вас есть линейный доступ? Вторым было бы лучше использовать строку кэша.

Но первый легче читать.