Better understanding of 3D to 1D array conversion in C++

Question

I'm working on a school project in which I need to dynamically manage a 3D matrix (or array, I don't think it makes a difference, right?). My first idea was to use a C-like approach, like this:

3Dmatrix(unsigned int height, unsigned int col, unsigned int row) : _3D_matrix(0), _row(0), _col(0), _height(0) { 


    try {
       _3D_matrix = new T**[height];
            for(int i =0; i<height; i++){
                _3D_matrix[i] = new T*[col];
                for(int j =0; j<col; j++){
                    _3D_matrix[i][j] = new T[row];


                }
            }
    }
    catch(...) {
        delete[] _3D_matrix;
        throw;
    }

       _row = row;
       _col = col;
       _height = height;

    }

With this approach, though, the memory is not contiguous, and trying to work with iterators is almost impossible. So I decided to switch to a different strategy, "indexing" the 3D array to a 1D array using the formula

A[ x * height * depth + y * depth + z] 

to index the element M[x][y][z]. Since I'm not really sure this approach is what I'm looking for, and I also find other discussions on this topic not very helpful, do you think this approach can serve my purpose?

In particular, I'm worried about getter and setter methods, as well as iterators for reading and writing.

PS: since this project is for didactic use, I'm not allowed to use std library classes like vector or similar, and C++11 or later as well

Answer 1

With this approach, though, the memory is not contiguous ...

That's not wholly true. Each row is contiguous, and if you mostly operate row-by-row, that might be fine. It's a performance question anyway, so get it working as simply as possible first and worry about optimization later (if at all).

[indexing] ... I'm not really sure this approach is what I'm looking for ... do you think this approach can serve my purpose?

What is your purpose?

A flattened array is easier to manage in the sense that there's only one dynamic (de)allocation - your existing nested structure is buggy because it's hard to clean up correctly part-way through construction.

A flattened array is probably slightly faster, if you care, depending on size and access pattern.

A nested structure is easier to write (and test, and generalize) in that you can layer it up one dimension at a time, roughly like

template <typename T> class Vector;
template <typename T> using Matrix2d = Vector<Vector<T>>;
template <typename T> using Matrix3d = Vector<Matrix2d<T>>;

trying to work with iterators is almost impossible

Slow down. Write one layer of abstraction at a time. If you can write the get(x,y,z) accessor, do that first and layer iteration on top of it.

Answer 2

You could try an approach like this:

struct Vector {
    unsigned int X;
    unsigned int Y;
    unsigned int Z;
};

struct Matrix {
    Vector rows[3];     // Depends on if you want row or col major.
    // Vector cols[3];
};

// Or Matrix {
    Vector* pRows;     // Depends on if you want row or col major.
    // Vector* pCols;

// Or
struct Matrix {   // Row Major
    Vector row1;
    Vector row2;
    Vector row3;
};

// Or
struct Matrix {  // Col Major
    Vector col1;
    Vector col2;
    Vector col3;
};

I did not add any constructors, operators nor functions only just shown basic data structure to illustrate the main point.

Note: This kind of pattern has a fixed dimensional size as it is a 3x3x3 matrix.

---

I do have a class template that can be a variable size matrix of any number of dimensions however it does use advanced techniques in which you stated that you were not able to use such as the standard library and c++11 or higher features. However as a bonus and for future use I can show it here as a good reference to look back on. This does not have anything to do with actually answering your question above; but this is what modern c++ would look like.

file Matrix.h

#ifndef MATRIX_H
#define MATRIX_H

#include <vector>
#include <algorithm>
#include <numeric>

namespace foo {

template<typename Type, size_t... Dims>
class Matrix {
public:
    static const size_t _numDims = sizeof...(Dims);

private:
    size_t _numElements;

    std::vector<Type>   _elements;
    std::vector<size_t> _strides;

public:
    Matrix() noexcept;

    template<typename... Args>
    Matrix( Args&&... args ) noexcept;

    const Type& operator[]( size_t idx );
    const Type operator[]( size_t idx ) const;

    const Type& operator() ( size_t idx );
    const Type operator() ( size_t idx ) const;

    size_t numElements() const {
        return _elements.size();
    }

    const std::vector<size_t>& strides() const {
        return _strides;
    }

    const std::vector<Type>& elements() const {
        return _elements;
    }
};


#include "Matrix.inl"

} // namespace foo

#endif // !MATRIX_H

file Matrix.inl

template<typename Type, size_t... Dims>
Matrix<Type, Dims...>::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 );
}

template<typename Type, size_t... Dims>
template<typename... Args>
Matrix<Type, Dims...>::Matrix( Args&&... args ) noexcept :
_elements( { args... } ),
_strides( { Dims... } ) {
    _numElements = _elements.size();
}

template<typename Type, size_t... Dims>
const Type Matrix<Type, Dims...>::operator[]( size_t idx ) const {
    return _elements[idx];
}

template<typename Type, size_t... Dims>
const Type& Matrix<Type, Dims...>::operator[]( size_t idx ) {
    return _elements[idx];
}

template<typename Type, size_t... Dims>
const Type Matrix<Type, Dims...>::operator()( size_t idx ) const {
    return _elements[idx];
}

template<typename Type, size_t... Dims>
const Type& Matrix<Type, Dims...>::operator()( size_t idx ) {
    return _elements[idx];
}

typical uses:

{

     Matrix<int,2,3,4> iMat2x3x4;

     Matrix<double,5,9> dMat5x9;

     struct MyStruct {
         int x;
         float y;
         char z;
     };

     Matrix<MyStruct, 4, 9, 7, 2, 3, 6> massiveMyStructMatrix;

}

The class upon instantiation will store the elements into one of its member vectors while calculating the strides for the dimensions and storing them into another vector. If a matrix is a 2x3x4x5 which is a 4D matrix the _strides container will have 4 values {2,3,4,5} respectively. This way if you need to do any kind of indexing the values are stored sequentially and you don't have to remember them, you can just index into the vector to get the size of the stride to do the appropriate indexing in the current level of your loop. All of the elements are contiguous in memory via the vector. There are also a few basic operators [] and () for both non const and const types. A method to return the number of elements which is the size of the _elements container. And two methods to return the actual containers.

Now you could take this idea and abstract the vectors out of the way however it still does not remove the dependency of the c++11 and higher features especially the use of variadic templates. This is nothing more than a good reference for future use.