what is the best modern c++ approach to construct and manipulate a 2d array

Question

As in the title, I got to find tons of solutions doing this. Most people would say std::array<4, std::array<4, int>> or std::vector<std::vector<int>> are good, which, however, I find looks teidous and hard to extend to multi-dimensional arrays. Also, I fear that these arrays are actually object-arrays which is likely to be with some overhead (I guess so, not really certain). So what is the best way to do this ?

Answer 1

Some points to get you started.

First, std::array vs std::vector. This is easy. If you know at compile time the size of your 2d array then definitely std::array else std::vector.

std::vector<std::vector<T>> is ok for something that you need to cook up quickly and you use seldom in pieces of code that are not performance critical⁽¹⁾.

The big downside to std::vector<std::vector<T>> is the memory layout. You have double indirection and each line is allocated separately, wreaking havoc on your cache so it's a definitely a no no in performance critical code ⁽¹⁾. For performance critical code you need to use a mature math library. Experts can write performance oriented code order of magnitude better than you or me and another important advantage of such library is that it passed the test of time.

If for whatever reason you want to write this yourself then the solution is to flatten the matrix. I.e. use std::vector<T>(numRows * numColumns) and then access the elements with the formula: (i, j) -> v[i * numColumns + j]. And wrap that in a nice interface. How complex the interface is and what kind of operations you allow on it it's totally up to you.

---

⁽¹⁾ I would like to point out that most often especially novice programmers completely misunderstand performance concerns (it's completely understandable due to lack of experience). First there are some few generally acceptable practices that apply to any situation. Then comes the analysis of the algorithm and the data types used. But other than that you first write code for readability and then, if performance is a concern, you profile your code and start optimizing where the profiler tells you.

Answer 2

I happen to have this completely untested example lying around. If it works, good, otherwise it is an example of how you might go about creating a 2D view onto a 1D array:

template<typename T>
class two_dee_array
{
public:
    two_dee_array(std::size_t row, std::size_t col)
        : v(row * col), stride(col) {}

    T& operator()(std::size_t row, std::size_t col)
        { return v[(row * stride) + col]; }

    T const& operator()(std::size_t row, std::size_t col) const
        { return v[(row * stride) + col]; }

    std::size_t col_size() const { return stride; }
    std::size_t row_size() const { return v.size() / stride; }

    auto begin() { return std::begin(v); }
    auto end() { return std::end(v); }

    auto begin() const { return std::begin(v); }
    auto end() const { return std::end(v); }

    auto cbegin() const { return std::cbegin(v); }
    auto cend() const { return std::cend(v); }

private:
    std::vector<T> v;
    std::size_t stride;
};

Answer 3

When working with multiple dimensional arrays the first thing that comes to mind is a Matrix. I will show 3 variations of my Matrix classes that are templates. In the first 2 cases, you will see that the data is stored in a single dimensional array, but is indexed based on a 2D conversion. In the third type I'm using just a single std::vector<Type> to hold all of the contents but I'm using another std::vector<size_t> to hold all of the strides for indexing into each dimension of the higher dimensional matrix.

The 1^st is a MxM - Matrix: - This will do any Square Matrix

template<class T, unsigned M>
class Matrix {
    static const unsigned Stride = M;
    static const Size = Stride * Stride;
    T data[Size] = {};

public:
    Matrix() {};
    Matrix( const T* dataIn ) {
        fillMatrix( dataIn );
    }

    void fillMatrix( const T* dataIn );
    void printMatrix();
};

template<class T, unsigned M>
void Matrix<T,M>::fillMatrix( const T* dataIn ) {
    for ( unsigned int i = 0; i < Size; i++ ) {
        this->data[i] = dataIn[i];
    }
}

template<class T, unsigned M>
void Matrix<T,M>::printMatrix() {
    for ( unsigned int i = 0; i < Stride; i++ ) {
        for ( unsigned int j = 0; j < Stride; j++ ) {
            std::cout << this->data[i*Stride + j] << " ";
        }
        std::cout << '\n';
    }
}

The 2^nd is a MxN - Matrix: - This will do any 2D Matrix

template<class T, unsigned M, unsigned N>
class Matrix {
private:
    static const unsigned Row = M;
    static const unsigned Col = N;
    static const unsigned Size = M * N;
    T data[Size] = {};

public:
    Matrix() {};
    Matrix( const T* dataIn ) {
        fillMatrix( dataIn );
    }

    void fillMatrix( const T* dataIn );
    void printMatrix();
};

template<class T, unsigned M, unsigned N>
void Matrix<T,M,N>::fillMatrix( const T* dataIn ) {
    for( unsigned int i = 0; i < Size; i++ ) {
        this->data[i] = dataIn[i];
    }
}

template<class T, unsigned M, unsigned N>
void Matrix<T,M,N>::printMatrix() {
    for( unsigned int i = 0; i < Row; i++ ) {
        for( unsigned int j = 0; j < Col; j++ ) {
            std::cout << this->data[i*Col + j] << " ";
        }
        std::cout << '\n';
    }
}

The 3^rd is a MxNx... - Matrix: This will do any Arbitrary Matrix. Note - This requires modern C++ with a compiler that support variadic templates! It looks something like this. The first two will compile and you can use as is. As for this one; I have not shown the entire class as this is only the tip of the iceberg. What I like to call a Volumetric Matrix is very robust and has too much source to post here and some of my functionality is not yet completed. It also relies on several other helper class templates and uses various other types of class templates that are all specifically related to matrices for its storage, logging, etc. but it's basic shell would look like this:

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... Arg>
    Matrix( Arg&&... as  ) noexcept;

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

}; // Matrix

It's nearly completed header file looks like this as this is still a work in progress and this only accounts for the actual storage of the matrix: I still have yet to work on any calculation aspects of it.

#pragma once

#include <vector>
#include <map>
#include <sstream>
#include <exception>
#include <iostream>
#include <numeric>
#include <algorithm>

const unsigned int EVEN = 0;
const unsigned int ODD = 1;

template<typename const std::size_t ... Dims> class DimensionPack;
template<typename ClassType, const std::size_t buffer>   class MatrixBuffer;
template<typename ClassType, const std::size_t ... Dims> class MatrixCell;
template<typename ClassType, const std::size_t ... Dims> class MatrixReference;
template<typename ClassType, const std::size_t ... Dims> class MatrixStorage;
template<typename ClassType, const std::size_t ... Dims> class MatrixAllocation;
template<typename ClassType, const std::size_t ... Dims> class MatrixLog;
template<typename ClassType, const std::size_t ... Dims> class MatrixFile;

template<typename ClassType, const std::size_t ... Dims>
class Matrix {
private:
    DimensionPack<Dims...> dp_;
    MatrixStorage<ClassType, Dims...> storage_;
    MatrixReference<ClassType, Dims...> reference_;
    MatrixAllocation<ClassType, Dims...> allocation_;

    const unsigned int numDimensions_ = dp_.total_dimensions;
    const unsigned int numElements_ = dp_.total_elements;
    std::vector<std::size_t> dimensions_ = dp.dimensions;
    std::vector<std::size_t> even_or_odd_ = dp_.even_or_odd;

public:
    Matrix() {}

    std::vector<unsigned int>& getDimensions() { return dimensions_; }
    std::vector<unsigned int>& getEvenOrOdd() { return even_or_odd_; }
    const std::size_t getNumberOfDimensions() const { return numDimensions_; }

    // Amount of fields must be equal to total matrix elements
    // Example: a 2x2 Matrix has 4 elements and a 3x3x3 has 27 
}; // Matrix

// DimensionPack & Helper Struct
struct MatrixDimensionOddOrEven {
    const std::size_t even_or_odd;
    explicit MatrixDimensionOddOrEven( unsigned int odd_or_even ) : even_or_odd( test( odd_or_even ) ) {}
private:
    const unsigned int test( unsigned int value ) const {
        if( value == 0 ) {
            std::ostringstream stream;
            stream << __FUNCTION__ << " invalid number: " << value << " must be >= 1\n";
            throw std::runtime_error( stream.str() );
        }
        return (((value % 2) == 0) ? EVEN : ODD);
    }

}; // typedef MatrixDimensionOddOrEven MatDimOddEven; 

template<const std::size_t ... Dims>
class DimensionPack {
public:
    std::vector<std::size_t> dimensions;
    std::vector<std::size_t> even_or_odd;
    const std::size_t total_dimensions = sizeof...(Dims);
    const std::size_t total_elements = countElements();

public:
    DimensionPack() : dimensions{ Dims... },
        even_or_odd{ MatrixDimensionOddOrEven{Dims}.even_or_odd... } {
    }

private:
    std::size_t countElements() {
        std::size_t val = 1; // Don't Init to 0 otherwise multiplication won't work here!
        for( std::size_t n = 0; n < dimensions.size(); n++ ) {
            val *= dimensions[n];
        }
        return val;
    }
}; // DimensionPack

template<std::size_t>
struct const_size_t {
    using type = std::size_t;
};

template<typename ClassType, const std::size_t... DimCoords>
class MatrixCell {
    std::vector<std::size_t> coordinateIndices_;
    ClassType data_;

public:
    MatrixCell() : coordinateIndices_{ DimCoords... }, data_( 0 ) {}

    // template<typename const_size_t<Dims>::type... Args>
    void addItem( ClassType item, typename const_size_t<DimCoords>::type... coords ) {
        if( !(checkItem( coords... )) ) {
            std::ostringstream stream;
            stream << __FUNCTION__ << " Current index doesn't exist\n";
            throw std::runtime_error( stream.str() );
        } else {
            if( data_ != 0 ) {
                std::ostringstream stream;
                stream << __FUNCTION__ << " Item with a value of " << data_ << " already exists at this location\n";
                std::cerr << stream;
            } else {
                data_ = item;
            }
        }
    }

    // template<typename const_size<Dims>::type... Args>
    bool checkIndex( typename const_size_t<DimCoords>::type... coords ) {
        std::vector<std::size_t> vals{ coords... };
        static bool isValid = true;
        for( unsigned u = 0; u < coordinateIndices_.size(); u++ ) {
            if( vals[u] > coordinateIndices_[u] ) {
                isValid = false;
            }
        }
        return isValid;
    }
}; // MatrixCell

// Empty Abstract Base Class
template<typename ClassType = void>
class MatrixBase {
protected:
    MatrixBase() = default;
    virtual ~MatrixBase() = default;
}; // MatrixBase

// Used For Extremely Large Data Sets
template<typename ClassType, const std::size_t bufferSize>
class MatrixBuffer {
public:
    typedef std::vector<std::size_t> dimensions;
    typedef std::vector<std::vector<ClassType>> elements;

    std::map<dimensions, elements> matrixBuffer = std::map<dimensions, elements>().reserve( bufferSize );

}; // MatrixBuffer


// Stores all of the contents of the Matrix
template<typename ClassType, const std::size_t ... Dims>
class MartrixStorage : public MatrixBase<ClassType>, DimensionPack<Dims...> {

}; // MatrixStorage

// Used to reference the storage class of the Matrix
template<typename ClassType, const std::size_t ... Dims>
class MatrixReference : public MatrixBase<ClassType>, DimensionPack<Dims...> {

};

// Used only when the user wants to create a matrix in dynamic memory.
// It handles if a user wants to use shared_ptr or unique_ptr for its contained elements (... incomplete declaration)
template<typename ClassType, const std::size_t ... Dims>
class MatrixAllocation : public MatrixBase<ClassType>, DimensionPack<Dims...> {

};

// Used to log the matrix to the console or print it via some window or to a file
template<typename ClassType, const std::size_t ... Dims>
class MatrixLog : public MatrixBase<ClassType>, DimensionPack<Dims...> {

};

// Used to create the layout for a file structure both in writing to and reading from used in conjuction with MatrixLog
template<typename ClassType, const std::size_t ... Dims>
class MatrixFile : public MatrixBase<ClassType>, DimensionPack<Dims...> {

};