5
\$\begingroup\$

Context:

I have already seen different implementation of multi-dimensional arrays, but most of them use that kind of access arr(i, j, k) while I find more natural arr[i][j][k] like what we have when we use non dynamic multi-dimensional raw arrays or containers of containers. And I really want contiguous data storage, which vectors of vectors (or arrays of pointers) do not offer.

So this implementation tries to mimic the best I can a true multi-dimensional raw array (and the underlying struct is), with some additions because it is moveable and copyable, and some drawbacks, because I could not implement pointer arithmetics.

Code:

template <class T, size_t Dims>
class MDynArrayBase
{

    // compute total size while storing intermediate sizes: accept size_t or int
    template<class...V>
    size_t calcsize(size_t* sizes, size_t first, V...others) {
        *sizes = first;
        return first * calcsize(sizes + 1, others...);
    }
    template<class...V>
    size_t calcsize(size_t* sizes, int first, V...others) {
        *sizes = first;
        return first * calcsize(sizes + 1, others...);
    }
    size_t calcsize(size_t* sizes) {
        return 1;
    }

    // action for destructor and operator = to recycle object
    void do_clean() {
        if (!view) {
            delete[] arr;
            delete[] sizes;
        }
    }

    // action for copy ctor and operator = (const &)
    void do_copy(const MDynArrayBase& src) {
        view = src.view;
        if (view) {
            arr = src.arr;
            sizes = src.sizes;
            rowsize = src.rowsize;
        }
        else {
            rowsize = src.rowsize;
            sizes = new size_t[Dims];
            for (size_t i = 0; i < Dims; i++) sizes[i] = src.sizes[i];
            arr = new T[sizes[0] * rowsize];
            for (size_t i = 0; i < sizes[0] * rowsize; i++) arr[i] = src.arr[i];
        }
    }

    // action for move ctor and operator = (&&)
    void do_move(MDynArrayBase&& src) {
        view = src.view;
        arr = src.arr;
        sizes = src.sizes;
        rowsize = src.rowsize;
        src.view = true;         // original is no longer owner
    }

protected:
    T* arr;          // 1D array of size dim1*dim2...*dimN
    size_t *sizes;   // size of all dimensions
    size_t rowsize;  // size of a row (cached)
    bool view;       // if true object is just a view on an ancestor's data
                     //  so it shall not delete anything in its dtor

    // protected virtual dtor to make the base class not directly constructible
    virtual ~MDynArrayBase() {
        do_clean();
    }

    // protected ctor used from operator []
    MDynArrayBase(T* arr, size_t *sizes, size_t rowsize)
        : arr(arr), sizes(sizes), rowsize(rowsize), view(true) {}

public:

    // normal ctor U shall only contain size_t or int for calcsize
    template<class...U>
    MDynArrayBase(size_t sz, U... others) {
        static_assert(1 + sizeof...(U) == Dims, "Wrong number of dimensions");
        sizes = new size_t[Dims];
        *sizes = sz;
        rowsize = calcsize(sizes+1, others...);
        arr = new T[rowsize * *sizes];
        view = false;
    }

    // empty ctor uses 1 for all dimensions
    MDynArrayBase() {
        sizes = new size_t[Dims];
        for (size_t i = 0; i < Dims; i++) sizes = 1;
        rowsize = 1;
        arr = new T[1];
        view = false;
    }
    // copy and move ctors and operator []
    MDynArrayBase(const MDynArrayBase& src) {
        do_copy(src);
    }
    MDynArrayBase(MDynArrayBase&& src) {
        do_move(std::move(src));
    }
    MDynArrayBase& operator = (const MDynArrayBase& src) {
        do_clean();
        do_copy(src);
    }
    MDynArrayBase& operator = (const MDynArrayBase&& src) {
        do_clean();
        do_move(std::move(src));
    }

    // return individual dimensions
    size_t size(size_t dim) const {
        return sizes[dim];
    }

    // return total size
    size_t size() const {
        return rowsize * sizes[0];
    }
};

// normal subclass for Dims > 1 : operator [] give a MDynArray of Dims-1 rank
template<class T, size_t Dims>
class MDynArray: public MDynArrayBase<T, Dims> {
    using MDynArrayBase<T, Dims>::arr;
    using MDynArrayBase<T, Dims>::sizes;
    using MDynArrayBase<T, Dims>::rowsize;

public:
    using MDynArrayBase<T, Dims>::MDynArrayBase; // inherits ctors

    // operator [] gives a view on a sub MDynArray
    MDynArray<T, Dims - 1> operator[] (size_t i) const {
        return MDynArray<T, Dims - 1>(arr + i * rowsize,
            sizes + 1, rowsize / sizes[1]);
    }

    // allows protected ctor from containing MDynArray
    friend class MDynArray<T, Dims + 1>;
};

// specialization for Dims == 1 : operator [] gives a T& or a T (if const)
template<class T>
class MDynArray<T, 1> : public MDynArrayBase<T, 1> {
    using MDynArrayBase<T, 1>::arr;
    //using MDynArrayBase<T, 1>::sizes;

public:
    using MDynArrayBase<T, 1>::MDynArrayBase;

    T& operator[] (size_t i) {
        return arr[i];
    }
    T operator[] (size_t i) const {
        return arr[i];
    }

    friend MDynArray<T, 2>;
};

template<class T, class...U>
MDynArray<T, sizeof...(U)> make_dyn_array(U...dims) {
    return MDynArray<T, sizeof...(U)>(dims...);
}

Questions:

I wonder whether this code follows modern C++ best practices. Notably, I find rather ugly the trick of derivating a base class to keep most part of the code common while allowing different signatures for the operator []: it yields a single element when the dimension is 1 and another array of dimension one below the original one when it is >1. But I could not find my way through enable_if constructs.

I have not use any C++14 feature here, but I would gladly accept any one that could lead to a cleaner code.

\$\endgroup\$
5
\$\begingroup\$
  1. The number of dimensions is a compile-time constant. There's no point in allocating an array to store them dynamically. You can use std::array instead.

  2. Member-functions like do_move, do_copy and do_clean (which act as constructors/destructors) are a smell. You can write cleaner and simpler code using the copy-and-swap idiom (The idea is to implement a custom swap function and a copy constructor and then pass the right-hand side object by value in assignment. A move assignment and move constructor become essentially one swap).

  3. This idiom will also solve the self-assignment problem. Your code is broken now. If one assigns an array to itself, it'll get destroyed and will be in an invalid state.

  4. Memory allocation using new and delete is not a good idea. Your code is not exception-safe. Let's go through this piece of code:

    sizes = new size_t[Dims];
    *sizes = sz;
    rowsize = calcsize(sizes+1, others...);
    arr = new T[rowsize * *sizes];
    view = false;  
    

    if the first allocation succeeds, but the second one throws, the destructor is never called so the sizes leak. Use can use smart pointers to take care of that. You could also use one vector to store the values, but that would require redesigning views.

  5. Your code makes an assumption that T has a default constructor. You can fix it by creating another constructor that takes the initial value. It also makes sense from a design point of view: one might want to create an array of ints filled with, say, 1's.

  6. arr = new T[rowsize * *sizes]; may leave the values uninitialized (it depends on the type of T), so using them afterwards without a prior initialization results in undefined behavior. Not sure if it's intended, but I'd always initialize it (with arr = new T[rowsize * *sizes]()).

  7. It also seems strange to me that the default size is 1 for all dimensions. It'd be more typical to have an empty array as the default.

  8. An operator[] should return const T& for a const object, not T to avoid making a copy which may be very expensive.

Summary

Managing memory is hard. Relying on standard practices and data structures can tremendously simplify it (in this case, they're: the copy-and-swap idiom, smart pointers and standard containers).

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for this extensive review! All points make sense and will help for a new version... \$\endgroup\$ – Serge Ballesta Aug 26 '17 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.