Трехмерные массивы целых чисел в C ++
-
09-06-2019 - |
Вопрос
Я хотел бы найти безопасные способы реализации трехмерных массивов целых чисел в C ++, используя арифметику указателей / динамическое распределение памяти или, в качестве альтернативы, используя STL
такие методы, как векторы.
По сути, я хочу, чтобы размеры моего целочисленного массива выглядели следующим образом:
[ x ][ y ][ z ]
значения x и y находятся в диапазоне 20-6000 z известно и равно 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];
Чтобы приступить к распределению этого массива, вам просто нужно признать, что на самом деле у вас нет трехмерного массива целых чисел.У вас есть массив массивов целых чисел.
// 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;
Ниже приведен простой способ создания 3D-массивов с использованием C или C ++ в одном фрагменте памяти для каждого массива.Не нужно использовать BOOST (даже если это приятно) или разделять выделение между строками с несколькими косвенными ссылками (это довольно плохо, поскольку обычно приводит к большому снижению производительности при доступе к данным и фрагментирует память).
Единственное, что нужно понимать, это то, что не существует такого понятия, как многомерные массивы, просто массивы массивов (of arrays).Самый внутренний индекс является самым удаленным в памяти.
#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;
}
}
Что касается вашей реальной проблемы, поскольку потенциально существует два неизвестных измерения, существует проблема с моим предложением разрешить только одно неизвестное измерение.Есть несколько способов справиться с этим.
Хорошей новостью является то, что использование переменных теперь работает с 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 (но хороший компилятор, вероятно, может оптимизировать его), но использует только один фрагмент памяти для массива, выделенного в куче.Что обычно является наиболее эффективным выбором.
Очевидно, что даже если приведенный выше код по-прежнему прост и понятен, STL или BOOST делают это хорошо, следовательно, нет необходимости изобретать велосипед.Я все еще считаю, что интересно знать, что это можно легко сделать.
С векторами:
std::vector< std::vector< std::vector< int > > > array3d;
Каждый элемент доступен с помощью array3d [x] [y] [z], если элемент уже был добавлен.(например,через push_back)
Следует отметить, что, по сути, вы имеете дело только с 2D-массивом, поскольку известно третье (и наименее значимое) измерение.
Использование STL или Boost - неплохие подходы, если вы заранее не знаете, сколько записей у вас будет в каждом измерении массива, потому что они обеспечат вам динамическое выделение памяти, и я рекомендую любой из этих подходов, если ваш набор данных должен оставаться в основном статичным, или если он в основном будет получать только новые записи и не так много удалений.
Однако, если вы заранее знаете что-то о своем наборе данных, например, примерно, сколько всего элементов будет сохранено, или если массивы должны быть малонаселенными, возможно, вам лучше использовать какую-нибудь функцию хэша / корзины и использовать индексы XYZ в качестве вашего ключа.В этом случае, предполагая не более 8192 (13 бит) записей на измерение, вы могли бы обойтись 40-битным (5-байтовым) ключом.Или, предполагая, что всегда есть 4 записи x Z, вы бы просто использовали 26-битный ключ XY.Это один из наиболее эффективных компромиссов между скоростью, использованием памяти и динамическим распределением.
Использование STL для управления вашей памятью имеет много преимуществ по сравнению с использованием new / delete.Выбор способа представления ваших данных зависит от того, как вы планируете их использовать.Одним из предложений был бы класс, который скрывает решение о реализации и предоставляет трехмерные методы получения / установки для одномерного вектора STL.
Если вы действительно считаете, что вам нужно создать пользовательский векторный тип 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;
};
Предложение Питера, конечно, хорошее, но вы должны иметь в виду одну вещь: в случае создания больших массивов это может быть довольно медленным.Каждый раз, когда емкость вектора изменяется, все данные должны быть скопированы по кругу ('n' векторов векторов).