Home Fast element access for multi-dimensional representation of contiguous array

# Fast element access for multi-dimensional representation of contiguous array

user5915738
1#
user5915738 Published in 2017-12-07 00:37:53Z
 I have a multi-dimensional array represented contiguously in memory. I want to keep this representation hidden and just let the user access the array elements as if it were a multi-dimensional one: e.g. my_array[0][3][5] or my_array(0,3,5) or something similar. The dimensions of the object are not determined until runtime, but the object is created with a type that specifies how many dimensions it has. This element look-up will need to be called billions of times, and so should hopefully involve minimal overhead for each call. I have looked at similar questions but not really found a good solution. Using the [] operator requires the creation of N-1 dimensional objects, which is fine for multi-dimensional structures like vectors-of-vectors because the object already exists, but for a contiguous array it seems like it would get convoluted very quickly and require some kind of slicing through the original array. I have also looked at overloading (), which seems more promising, but requires specifying the number of arguments, which will vary depending upon the number of dimensions of the array. I have thought about using list initialization or vectors, but wanted to avoid instantiating objects. I am only a little familiar with templates and figure that there should be some way with C++'s majestic template powers to specify a unique overloading of () for arrays with different types (e.g. different numbers of dimensions). But I have only used templates in really basic generic cases like making a function use both float and double. I am imagining something like this: template class MultiArray { public: MultiArray() {} //build some things ~MultiArray() {} //destroy some things // The number of arguments would be == to TDim for the instantiated class float& operator() (int dim1, int dim2, ...) { //convert to contiguous index and return ref to element // I believe the conversion equation is something like: // dim1 + Maxdim1 * ( dim2 + MaxDim2 * ( dim3 + MaxDim3 * (...))) } private: vector internal_array; vector MaxDimX; // Each element says how large each corresponding dim is. };  So if I initialize this class and attempted to access an element, it would look something like this: my_array = MultiArray<4>(); element = my_array(2,5,4,1);  How might I go about doing this using templates? Is this even possible?
Yakk
2#
 template struct slice { T* data = 0; std::size_t const* stride = 0; slice operator[](std::size_t I)const { return{ data + I* *stride, stride + 1 }; } operator T&()const { return *data; } T& operator=(T in) { *data = std::move(in); return *data; } };  store a vector of data, and an std::vector stride of strides, where stride[0] is the element-stride that the first index wants. template struct buffer { std::vector data; std::vector strides; buffer( std::vector sizes, std::vector d ): data(std::move(d)), strides(sizes) { std::size_t scale = 1; for (std::size_t i = 0; i get(){ return {data.data(), strides.data()}; } };  c++14. Live example. If you use not enough []s it refers to the first element of the subarray in question. If you use too many it does UB. It does zero dimension checking, both in count of dimensions and in size. Both can be added, but would cost performance. The number of dimensions is dynamic. You can split buffer into two types, one that owns the buffer and the other that provides the dimensioned view of it.
max66
3#
 If you can use C++17, so variadic template folding, and row major order, I suppose you can write something like (caution: not tested) template
 I've used this pattern several times when creating a class templates of a matrix class with variable dimensions. Matrix.h #ifndef MATRIX_H template class Matrix { public: static const size_t numDims_ = sizeof...(Dims); private: size_t numElements_; std::vector elements_; std::vector strides_; // Technically this vector contains the size of each dimension... (its shape) // actual strides would be the width in memory of each element to that dimension of the container. // A better name for this container would be dimensionSizes_ or shape_ public: Matrix() noexcept; template Matrix( Arg&&... as ) noexcept; const Type& operator[]( size_t idx ) const; size_t numElements() const { return elements_.size(); } const std::vector& strides() const { return strides_; } const std::vector& elements() const { return elements_; } }; // matrix #include "Matrix.inl" #endif // MATRIX_H  Matrix.inl template Matrix::Matrix() noexcept : strides_( { Dims... } ) { using std::begin; using std::end; auto mult = std::accumulate( begin( strides_ ), end( strides_ ), 1, std::multiplies<>() ); numElements_ = mult; elements_.resize( numElements_ ); } // Matrix template template Matrix::Matrix( Arg&&... as ) noexcept : elements_( { as... } ), strides_( { Dims... } ){ numElements_ = elements_.size(); } // Matrix template const T& Matrix::operator[]( size_t idx ) const { return elements_[idx]; } // Operator[]  Matrix.cpp #include "Matrix.h" #include #include #include #include  main.cpp #include #include #include "matrix.h" int main() { Matrix mat3x3( 1, 2, 3, 4, 5, 6, 7, 8, 9 ); for ( size_t idx = 0; idx < mat3x3.numElements(); idx++ ) { std::cout << mat3x3.elements()[idx] << " "; } std::cout << "\n\nnow using array index operator\n\n"; for ( size_t idx = 0; idx < mat3x3.numElements(); idx++ ) { std::cout << mat3x3[idx] << " "; } std::cout << "\n\ncheck the strides\n\n"; for ( size_t idx = 0; idx < mat3x3.numDims_; idx++ ) { std::cout << mat3x3.strides()[idx] << " "; } std::cout << "\n\n"; std::cout << "=================================\n\n"; Matrix mf5x2x9x7; // Check Strides // Num Elements // Total Size std::cout << "The total number of dimensions are: " << mf5x2x9x7.numDims_ << "\n"; std::cout << "The total number of elements are: " << mf5x2x9x7.numElements() << "\n"; std::cout << "These are the strides: \n"; for ( size_t n = 0; n < mf5x2x9x7.numDims_; n++ ) { std::cout << mf5x2x9x7.strides()[n] << " "; } std::cout << "\n"; std::cout << "The elements are: "; for ( size_t n = 0; n < mf5x2x9x7.numElements(); n++ ) { std::cout << mf5x2x9x7[n] << " "; } std::cout << "\n"; std::cout << "\nPress any key and enter to quit." << std::endl; char c; std::cin >> c; return 0; } // main  This is a simple variable multidimensional matrix class of the Same Type  You can create a matrix of floats, ints, chars etc of varying sizes such as a 2x2, 2x3, 5x3x7, 4x9x8x12x2x19. This is a very simple but versatile class. It is using std::vector<> so the search time is linear. The larger the multi - dimensional matrix grows in dimensions the larger the internal container will grow depending on the size of each dimension; this can "explode" fairly quick if each individual dimensions are of a large dimensional size for example: a 9x9x9 is only a 3 dimensional volumetric matrix that has many more elements than a 2x2x2x2x2 which is a 5 dimensional volumetric matrix. The first matrix has 729 elements where the second matrix has only 32 elements. I did not include a default constructor, copy constructor, move constructor, nor any overloaded constructors that would accept either a std::container or another Matrix. This can be done as an exercise for the OP. I also did not include any simple functions that would give the size of total elements from the main container, nor the number of total dimensions which would be the size of the strides container size. The OP should be able to implement these very simply. As for the strides and for indexing with multiple dimensional coordinates the OP would need to use the stride values to compute the appropriate indexes again I leave this as the main exercise. EDIT - I went ahead and added a default constructor, moved some members to private section of the class, and added a few access functions. I did this because I just wanted to demonstrate in the main function the power of this class even when creating an empty container of its type. Even more you can take user Yakk's answer with his "stride & slice" algorithm and should easily be able to plug it right into this class giving you the full functionality of what you are looking for.
 It seems to me that you could use Boost.MultiArray, boost::multi_array_ref to be more specific. boost::multi_array_ref does exactly what you want: it wraps continuous data array into an object that may be treated as a multidimensional array. You may also use boost::multi_array_ref::array_view for slicing purposes. I cannot provide you with any benchmark results, but from my experience, I can say that boost::multi_array_ref works pretty fast.