Multi-dimensional container using operator[]

Question

This is a late followup to a previous question of mine on same subject.

Context:

I want to have a tool that allows to use all the C++ goodies (algorithms, for loop on containers, etc.) on a multidimensional contiguous array whose sizes are only known at run time. That immediately means that std::arrays are off (compile time sizes), as are vectors of vectors (not contiguous data). That also means that the common solution multi_array(i, j, k) is also off because of no natural iterators and direct members.

I ended with a bunch a classes:

• a full container class (MDynArray) with all copy/move semantics provided the underlying type has - in order to mimic standard containers, allocator is configurable
• a sub objects class (MSubArray) which accesses (read-write) the memory of its parent and tries to mimic the operations of a sequencial direct access standard container (operator[] and iterators)
• iterator and const_iterator classes for MSubArray (MDynArray being a subclass of it)

• a builder class (ArrayBuilder), because I want to be able to

  • build a new dynamic array from scratch
  • have it copy an existing raw array
  • have it use (no copy here) an existing raw array taking or not ownership

  and could not find a way to declare constructors or static factory methods for those different use cases

Code

Here is my current code (yes it is quite long...)

#include <type_traits>
#include <algorithm>
#include <exception>
#include <stdexcept>
#include <memory>
#include <utility>

namespace DynArray {

    using std::allocator;
    using std::allocator_traits;

    //Forward declarations
    template <class T, int dims, class Allocator>
    class MDynIteratorBase;
    template <class T, int dims, int cnst, class Allocator,
        class U = typename std::conditional<cnst == 1,
        const MSubArray<T, dims, Allocator>, MSubArray<T, dims, Allocator>>::type>
    class MDynIterator;

    // Base: contains the data and declares types
    template <class T, int dims, class Allocator>
    class MDynArrayBase {
    public:
        using value_type = T;
        using allocator_type = Allocator;
        using pointer = typename allocator_traits<Allocator>::pointer;
        using const_pointer = typename allocator_traits<Allocator>::const_pointer;
        using reference = T&;
        using const_reference = const T&;
        using size_type = typename allocator_traits<Allocator>::size_type;
        using difference_type = typename allocator_traits<Allocator>::difference_type;
    protected:
        T* arr;
        size_type *sizes;
        size_type rowsize;

        MDynArrayBase(T* arr, size_type* sizes, size_type rowsize)
            : arr(arr), sizes(sizes), rowsize(rowsize) {}

    public:
        virtual ~MDynArrayBase() {}
    };

    // Sub array: all the logic of accesses but do not manage (de-/)allocation
    template <class T, int dims, class Allocator>
    class MSubArray : public MDynArrayBase<T, dims, Allocator> {
    protected:
        using MDynArrayBase<T, dims, Allocator>::arr;
        using MDynArrayBase<T, dims, Allocator>::sizes;
        using MDynArrayBase<T, dims, Allocator>::rowsize;

        MSubArray(T* arr, size_type* sizes, size_type rowsize)
            : MDynArrayBase<T, dims, Allocator>(arr, sizes, rowsize) {}

    public:
        using iterator = typename MDynIterator<T, dims-1, 0, Allocator>;
        using const_iterator = typename MDynIterator<T, dims-1, 1, Allocator>;

        // access to member
        MSubArray<T, dims-1, Allocator> operator[] (size_type i) {
            MSubArray<T, dims-1, Allocator> child(arr + rowsize * i,
                sizes + 1, rowsize / sizes[1]);
            return child;
        }
        const MSubArray<T, dims-1, Allocator> operator[] (size_type i) const {
            MSubArray<T, dims-1, Allocator> child(arr + rowsize * i,
                sizes + 1, rowsize / sizes[1]);
            return child;
        }

        // access to internal data, arr and sizes and number of dimensions
        size_type size(size_type i = 0) const {
            if (i >= dims) {
                throw std::out_of_range("Illegal dimension");
            }
            if (sizes == nullptr) return 0;
            return sizes[i];
        }
        size_type tot_size() const {
            if (sizes == nullptr) return 0;
            return sizes[0] * rowsize;
        }
        T* data() {
            return arr;
        }
        const T* data() const {
            return arr;
        }
        constexpr int getdims() const {
            return dims;
        }

        // iterators
        iterator begin() {
            return iterator(arr, sizes + 1,
                rowsize / sizes[1]);
        }
        iterator end() {
            iterator tmp = begin();
            tmp += sizes[0];
            return tmp;
        }
        const_iterator cbegin() const {
            return const_iterator(arr, sizes + 1,
                rowsize / sizes[1]);
        }
        const_iterator cend() const {
            const_iterator tmp = cbegin();
            tmp += sizes[0];
            return tmp;
        }
        friend class MSubArray<T, dims + 1, Allocator>;
        friend class iterator;
        friend class const_iterator;
        friend class MDynIteratorBase<T, dims, Allocator>;
    };

    // specialization for 1D: members are true T objects
    template <class T, class Allocator>
    class MSubArray<T, 1, Allocator> : public MDynArrayBase<T, 1, Allocator> {
    protected:
        using MDynArrayBase<T, 1, Allocator>::arr;
        using MDynArrayBase<T, 1, Allocator>::sizes;

        MSubArray(T* arr, size_type* sizes, size_type rowsize)
            : MDynArrayBase<T, 1, Allocator>(arr, sizes, rowsize) {}

    public:
        using iterator = typename T*;
        using const_iterator = typename const T*;

        ~MSubArray() {}
        T& operator[] (size_type i) {
            return arr[i];
        }
        const T& operator[] (size_type i) const {
            return arr[i];
        }

        // same for size and arr, dims
        size_t size(size_t i = 0) {
            if (i != 0) {
                throw std::out_of_range("Illegal dimension");
            }
            if (sizes == nullptr) return 0;
            return sizes[0];
        }
        size_type tot_size() const {
            if (sizes == nullptr) return 0;
            return sizes[0];
        }
        T* data() {
            return arr;
        }
        const T* data() const {
            return arr;
        }
        constexpr int getdims() const {
            return 1;
        }

        //iterators
        iterator begin() {
            return arr;
        }
        iterator end() {
            return arr + sizes[0];
        }
        const_iterator cbegin() const {
            return arr;
        }
        const_iterator cend() const {
            return arr + sizes[0];
        }
        friend class MSubArray<T, 2, Allocator>;
        friend class iterator;
        friend class const_iterator;
        friend class MDynIteratorBase<T, 1, Allocator>;
    };

    // forward declaration for the builder class
    template <class T, class Allocator = std::allocator<T> >
    class ArrayBuilder;

    // Full array, must manage allocation/deallocation of resources
    template <class T, int dims, class Allocator = allocator<T> >
    class MDynArray : public MSubArray<T, dims, Allocator> {
        using MSubArray<T, dims, Allocator>::arr;
        using MSubArray<T, dims, Allocator>::sizes;
        using MSubArray<T, dims, Allocator>::rowsize;

        bool ownarr;          // if true, arr have to be deleted
        Allocator alloc;      // internal allocator

        // allocates a T array and optionaly copy-initializes its elements
        static T* clone(T* src, size_type tot, Allocator alloc) {
            T* dst = allocator_traits<Allocator>::rebind_traits<T>::allocate(
                alloc, tot);
            size_type i;
            try {
                if (src != nullptr) {
                    for (i = 0; i < tot; i++) {
                        allocator_traits<Allocator>::rebind_traits<T>::construct(
                            alloc, dst + i, src[i]);
                    }
                }
                else {
                    for (i = 0; i < tot; i++) {
                        allocator_traits<Allocator>::rebind_traits<T>::construct(
                            alloc, dst + i);
                    }
                }
            }
            catch(std::exception &) {
                while (i-- > 0) {
                    allocator_traits<Allocator>::rebind_traits<T>::destroy(
                        alloc, dst + i);
                }
                allocator_traits<Allocator>::rebind_traits<T>::deallocate(alloc,
                    dst, tot);
                throw;
            }
            return dst;
        }

        MDynArray(T* arr, size_type* sizes, size_type rowsize, bool ownarr,
            const Allocator& alloc)
            : MSubArray<T, dims, Allocator>(arr, sizes, rowsize),
            ownarr(ownarr), alloc(alloc) {}
    public:
        // copy/move ctors and assignment (rule of 5)
        MDynArray(const MDynArray<T, dims, Allocator>& other) 
            : MSubArray(nullptr, nullptr, 0) {
            alloc = other.alloc;
            ownarr = true;
            sizes = new size_type[dims];
            std::copy(other.sizes, other.sizes + dims, sizes);
            rowsize = other.rowsize;
            try {
                arr = clone(other.arr, rowsize * sizes[0], alloc);
            }
            catch (std::exception&) {
                delete[] sizes;
            }
        }
        MDynArray(MDynArray<T, dims, Allocator>&& other)
            : MSubArray(nullptr, nullptr, 0), alloc(Allocator()), ownarr(false) {
            swap(other);
        }
        MDynArray<T, dims, Allocator>& operator = (
            const MDynArray<T, dims, Allocator>& other) {
            MDynArray<T, dims, Allocator> tmp(other);
            swap(tmp);
            return *this;
        }
        MDynArray<T, dims, Allocator>& operator = (
            MDynArray<T, dims, Allocator>&& other) {
            swap(other);
            return *this;
        }
        ~MDynArray() {
            if (ownarr) {
                delete[] arr;
            }
            delete[] sizes;
        }
        void swap(MDynArray<T, dims, Allocator>& other) {
            using std::swap;

            swap(arr, other.arr);
            swap(sizes, other.sizes);
            swap(rowsize, other.rowsize);
            swap(ownarr, other.ownarr);
            swap(alloc, other.alloc);
        }
        friend class ArrayBuilder<T, Allocator>;
    };

    // auxilliary class to build new MDynArray objects, possibly copying
    //  moving (take ownership) or just using a pre-existing array
    template <class T, class Allocator>
    class ArrayBuilder {
    public:
        using size_type = typename allocator_traits<Allocator>::size_type;
    private:
        Allocator alloc;

        template <class...U>
        static size_type calc_size(size_type *sizes, size_type first,
            U...others) {
            if (sizes != nullptr) *sizes = first;
            return first * calc_size(sizes + 1, others...);
        }
        static size_type calc_size(size_type *sizes, size_type first) {
            if (sizes != nullptr) *sizes = first;
            return first;
        }
    public:
        ArrayBuilder(const Allocator& alloc = Allocator()) : alloc(alloc) {}

        template <class T, class ...U>
        MDynArray<T, sizeof...(U)+1, Allocator> dynUseArray(T* arr,
            size_type first, U...others) {
            constexpr size_t dims = sizeof...(U)+1;
            size_type *sizes = new size_type[dims];
            size_type tot = calc_size(sizes, first, others...);
            size_type rowsize = tot / sizes[0];
            return MDynArray<T, dims, Allocator>(arr, sizes, rowsize,
                false, alloc);
        }
        template <class T, class ...U>
        typename std::enable_if<std::is_copy_constructible<T>::value,
            MDynArray<T, sizeof...(U)+1, Allocator>>::type
            dynCopyArray(T* arr, size_type first, U...others) {
            constexpr size_t dims = sizeof...(U)+1;
            size_type *sizes = new size_type[dims];
            size_type tot = calc_size(sizes, first, others...);
            T* dst;
            try {
                dst = MDynArray<T, dims, Allocator>::clone(arr, tot, alloc);
            }
            catch (std::exception&) {
                delete[] sizes;
                throw;
            }
            return MDynArray<T, sizeof...(U)+1, Allocator>(dst, sizes,
                tot / sizes[0], true, alloc);
        }
        template <class ...U>
            MDynArray<T, sizeof...(U)+1, Allocator>
            dynBuildArray(size_type first, U...others) {
            constexpr size_t dims = sizeof...(U)+1;
            size_type *sizes = new size_type[dims];
            size_type tot = calc_size(sizes, first, others...);
            T* dst;
            try {
                dst = MDynArray<T, dims, Allocator>::clone(nullptr, tot, alloc);
            }
            catch (std::exception&) {
                delete[] sizes;
                throw;
            }
            return MDynArray<T, sizeof...(U)+1, Allocator>(dst, sizes,
                tot / sizes[0], true, alloc);
        }
        template <class T, class ...U>
            MDynArray<T, sizeof...(U)+1, Allocator> dynMoveArray(T* arr,
                size_type first, U...others) {
            MDynArray<T, dims, Allocator> tmp = dynUseArray(arr,
                first, other...);
            tmp.ownarr = true;
            return tmp;
        }
    };

    // base class for both iterator and const_interator to ease comparisons
    template <class T, int dims, class Allocator>
    class MDynIteratorBase {
        using itbase = typename MDynIteratorBase<T, dims, Allocator>;

    public:
        using size_type = typename allocator_traits<Allocator>::size_type;
        using difference_type =
            typename allocator_traits<Allocator>::difference_type;

    protected:
        MSubArray<T, dims, Allocator> elt;
        size_type sz;

        MDynIteratorBase(T* arr, size_type *sizes, size_type rowsize) :
            elt(arr, sizes, rowsize), sz(sizes[0] * rowsize) {}

    public:
        bool operator ==(const itbase& other) const {
            return (elt.arr == other.elt.arr) && (elt.sizes == other.elt.sizes)
                && (elt.rowsize == other.elt.rowsize);
        }
        bool operator != (const itbase& other) const {
            return !operator ==(other);
        }
        bool operator <(const itbase& other) const {
            return elt.arr < other.elt.arr;
        }
        bool operator >(const itbase& other) const {
            return elt.arr > other.elt.arr;
        }
        bool operator <=(const itbase& other) const {
            return !operator >(other);
        }
        bool operator >=(const itbase& other) const {
            return !operator <(other);
        }

    protected:
        itbase& add(difference_type i) {  // implemented once in the base class
            elt.arr += i * sz;
            return *this;
        }

    };

    // iterator if cnst == 0 or const_iterator if cnst == 1, U is the value_type
    template <class T, int dims, int cnst, class Allocator, class U>
    class MDynIterator: public MDynIteratorBase<T, dims, Allocator> {
        using base = typename MDynIteratorBase<T, dims, Allocator>;
        using base::elt;
        using iterator = typename MDynIterator<T, dims, cnst, Allocator, U>;

        using difference_type = typename base::difference_type;
        using value_type = typename U;
        using pointer = typename U*;
        using reference = typename U&;
        using iterator_category = std::random_access_iterator_tag;

        MDynIterator(T* arr, size_type *sizes, size_type rowsize) :
            base(arr, sizes, rowsize) {}

    public:

        // a default ctor (to mimic standard iterators)
        MDynIterator(): base(nullptr, nullptr, 0) {}

        //convert an (non const) iterator to a const_iterator
        template <class X = T, typename = std::enable_if<cnst == 1>::type>
        MDynIterator(MDynIterator<T, dims, 1 - cnst, Allocator>& other)
            : base(other) {}

        // all operations of an iterator
        reference operator * () {
            return elt;
        }
        pointer operator -> () {
            return &elt;
        }
        const reference operator * () const {
            return elt;
        }
        const pointer operator -> () const {
            return &elt;
        }
        iterator& operator ++() {
            this->add(1);
            return *this;
        }
        iterator& operator --() {
            this->add(-1);
            return *this;
        }
        iterator operator ++(int) {
            iterator tmp = *this;
            this->add(1);
            return tmp;
        }
        iterator operator --(int) {
            iterator tmp = *this;
            this->add(-1);
            return tmp;
        }
        iterator& operator += (difference_type i) {
            this->add(i);
            return *this;
        }
        iterator operator + (difference_type i) {
            iterator tmp = *this;
            tmp.add(i);
            return tmp;
        }
        iterator operator -= (difference_type i) {
            return operator += (-i);
        }
        iterator operator - (difference_type i) {
            return operator + (-i);
        }

        value_type operator [] (difference_type i) {
            return *(*this + i);
        }
        const value_type operator [] (difference_type i) const {
            return *(*this + i);
        }

        friend class MSubArray<T, dims+1, Allocator>;
    };
}

Questions:

I tried hard to remain as close as I could to standard components (containers and iterators) but may have followed a wrong path somewhere and would really like to know where

I tried to follow modern C++ patterns but coming from good old C I may have fallen in some anti pattern and would really like to know

I would anyway be interested by any improvement

Disclaimer:

Reverse iterators are (still) not implemented. I may implement them in a later version but the question is a priori not about that point.

After Incomputable's comment, I have realized that MDynIterator did not fullfill the requirements for a bidirectional iterator because it was a stashing iterator. I do not want to change the code immediately but it will be declared as a simple forward iterator. But that also means that std::reverse_iterator adaptor is not usable here...

Unit tests

After Toby Speight'comment, I have realized that test could be helpful here. Here is the current tests using MSVC 2017 test framework

#include "stdafx.h"
#include "CppUnitTest.h"
#include "../mdynarray/mdynarray.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

namespace UnitTest1
{       
    using namespace DynArray;
    TEST_CLASS(UnitTest1)
    {
    public:

        TEST_METHOD(useArr)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynUseArray(arr, 3, 4, 5);
            l = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 5; k++) {
                        Assert::AreSame(dynarray[i][j][k], arr[l++]);
                    }
                }
            }
        }

        TEST_METHOD(copyArr)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynCopyArray(arr, 3, 4, 5);
            l = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 5; k++) {
                        Assert::AreEqual(dynarray[i][j][k], arr[l]);
                        Assert::AreNotSame(dynarray[i][j][k], arr[l]);
                        l++;
                    }
                }
            }
        }

        TEST_METHOD(buildArr)
        {
            ArrayBuilder<int> builder;
            auto dynarray = builder.dynBuildArray(3, 4, 5);
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 5; k++) {
                        Assert::AreEqual(dynarray[i][j][k], 0);
                    }
                }
            }
        }

        TEST_METHOD(copyCtor)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynUseArray(arr, 3, 4, 5);
            auto dyn2 = dynarray;
            l = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 5; k++) {
                        Assert::AreEqual(dyn2[i][j][k], arr[l]);
                        Assert::AreNotSame(dyn2[i][j][k], arr[l]);
                        l++;
                    }
                }
            }
        }

        TEST_METHOD(moveCtor)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynUseArray(arr, 3, 4, 5);
            auto dyn2 = std::move(dynarray);
            Assert::AreEqual(dynarray.size(), 0u);
            l = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 5; k++) {
                        Assert::AreSame(dyn2[i][j][k], arr[l]);
                        l++;
                    }
                }
            }
        }

        TEST_METHOD(copyAssign)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynUseArray(arr, 3, 4, 5);
            auto dyn2 = builder.dynBuildArray(3, 4, 5);
            dyn2 = dynarray;
            l = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 5; k++) {
                        Assert::AreEqual(dyn2[i][j][k], arr[l]);
                        Assert::AreNotSame(dyn2[i][j][k], arr[l]);
                        l++;
                    }
                }
            }
        }

        TEST_METHOD(moveAssign)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynUseArray(arr, 3, 4, 5);
            auto dyn2 = builder.dynBuildArray(3, 4, 5);
            dyn2 = std::move(dynarray);
            Assert::AreEqual(dynarray[1][1][1], 0);   // Beware implementation test
            l = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 5; k++) {
                        Assert::AreSame(dyn2[i][j][k], arr[l]);
                        l++;
                    }
                }
            }
        }

        TEST_METHOD(nonConstIter)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynUseArray(arr, 3, 4, 5);
            l = 0;
            for (auto& it1 : dynarray) {
                for (auto& it2 : it1) {
                    for (auto& it3 : it2) {
                        Assert::AreSame(it3, arr[l]);
                        l++;
                        it3 = l;             // control it is not const...
                    }
                }
            }
        }

        TEST_METHOD(constIter)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynUseArray(arr, 3, 4, 5);
            l = 0;
            for (auto it1 = dynarray.cbegin(); it1 != dynarray.cend(); it1++) {
                for (auto it2 = it1->cbegin(); it2 != it1->cend(); it2++) {
                    for (auto it3 = it2->cbegin(); it3 != it2->cend(); it3++) {
                        Assert::AreSame(*it3, arr[l]);
                        l++;
                        // *it3 = l;           // does not compile
                    }
                }
            }
        }

        TEST_METHOD(convConstIterator)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynUseArray(arr, 3, 4, 5);

            auto it = dynarray.begin();
            MDynArray<int, 3>::const_iterator cit = it;

            //it = (MDynArray<int, 3>::iterator) cit;  // does not compile

            it += 1;
            cit += 1;
            Assert::IsTrue(it > dynarray.begin());
            Assert::IsTrue(it == cit);
            Assert::IsTrue(cit == it);
        }

        TEST_METHOD(revIterator)
        {
            ArrayBuilder<int> builder;
            int arr[60];
            int l = 0;
            for (int& i : arr) {
                i = l++;
            }
            auto dynarray = builder.dynUseArray(arr, 3, 4, 5);
            l = 0;

            for (auto it1 = dynarray.rbegin(); it1 != dynarray.rend(); it1++) {
                for (auto it2 = it1->rbegin(); it2 != it1->rend(); it2++) {
                    for (auto it3 = it2->rbegin(); it3 != it2->rend(); it3++) {
                        Assert::AreSame(*it3, arr[59 - l]);
                        l++;
                        *it3 = l;           // control non constness
                    }
                }
            }
        }

    };
}

Answer 1

This would be much easier to review if there were more useful comments (saying "forward declarations" in front of a bunch of forward declarations is not all that useful) or - more importantly - some actual code showing how these classes are intended to be used in practice. Whether or a class (hierarchy) is well designed depends almost entirely on how it's going to be used.

I'm a little hazy on the intention here, so this might be off, but it sounds like you're basically trying to create a class (hierarchy) that is - very roughly put - a container whose internal storage is a pointer to an array and a flag for whether the container owns it or not, and whose value type is a sub-array of the container (and in the degenerate case where it's a 1D array, the value type is T).

That's the understanding I am going to base the review on, so if that's wrong... well, then take the review with a grain of salt.

General overview

You seem to be conflating the concepts of Container and View. A container owns its contents; a view does not.

In your class hierarchy, MDynArray appears to be the only container... sorta-kinda. MSubArray appears to be a view. (And MDynArrayBase probably isn't intended to be part of the public interface.)

By combining these two different concepts into a single inheritance hierarchy, you've created a bit of a Frankenstein's monster. As just one example of the problems this causes (and there will be many more during the course of the review): If I create my own array then use it with MDynArray with the ownarr set to false (or if I use dynUseArray() in ArrayBuilder), I'm still having to deal with allocators... even though I'm not actually doing any allocating. Almost all of the complexity in your code is due to this dual concept juggling.

I suggest that what you really want is just a view.

Imagine if all you had was a single mdarray_view (short for "multidimensional array view") class (possibly with a single specialization for 1D arrays). This would be roughly equivalent to your current MSubArray. Forget about owning elements or allocators. Just allow the view to work with any contiguous data.

I could use a vector as the underlying data store for dynamic stuff:

auto data = std::vector<int>(27);
auto matrix3x3x3 = mdarray_view<int, 3>{data, 3, 3, 3};
matrix3x3x3[2][1][0] = 10;
auto m = matrix3x3x3[1]; // m is a mdarray_view<int, 2>

or instead of a vector I could have made data an array... and all of the above could be constexpr and done at compile time.

Note that this is basically identical to what you already have, in terms of functionality. The only additional thing your code does is that instead of a vector or an array, data could be a MDynArray. That's literally it. And MDynArray is basically a highly inefficient vector, so you're not really missing much.

As far as I can tell, this would satisfy every one of your stated design goals, with probably five times less code.

If you really want a container as well as a view, that's fine... but there's no reason it has to be in same the inheritance hierarchy. (A real world example is std::string and std::string_view, a related container and view, but neither inherits from the other. Notably, string_view has no allocator.) The only thing that gives you is that you can pass the MDynArray container to functions expecting a MSubArray view... but that's specious, because if you wanted to do that, you could create a MSubArray directly from the MDynArray anyway and it would be exactly the same thing.

So my general overview suggestion is: Forget trying to make both a container and a view. Just make a view, and let users use whatever containers they want.

Now with that said, let's move on to the code itself.

MDynArrayBase

using value_type = T;

This is a complex point to start off with... but your types are essentially views (or containers), and they're claiming to provide a view of Ts. Except... they don't really. If I do *m.begin() (where m is a derived class of MDynArrayBase) I don't get a reference to T. I get a MSubArray<T, dims-1, Allocator>. (Unless dims is 1, in which case I do get a reference to T.)

Just consider this supposedly simple function:

auto get_first_item(MDynArray<int, 3, std::allocator<int>>& a) ->
    MDynArray<int, 3, std::allocator<int>>::value_type
{
    return *a.begin();
}

This won't compile, because the value_type is int, but the actual return type is MSubArray<int, 2, std::allocator<int>>.

This opens a whole can of worms because the allocator is supposedly something that allocates T, but the view's items - as found by iterating through from begin() to end() are probably something else entirely. So what is it a view of? Is it a view of T, or sub-arrays?

The "correct" thing to do would probably be to require an allocator that allocates the sub-arrays, and use rebind internally to actually allocate T arrays. value_type, pointer, reference, and so on would all be based on the sub-array type... not T. Of course, that makes things really messy, because you couldn't just do:

MyDynArray<T, Dims, Allocator = std::allocator<T>>

You'd have to do:

MyDynArray<T, Dims, Allocator = std::allocator<MSubArray<T, Dims - 1, some_other_allocator>>>

And now you see the pickle.

So you're forced to use allocator<T> as the template parameter, but then you have to rebind all the typedefs to... something. And you're back in the pickle jar. You've got a real mess on your hands.

Once again, the complexity and confusion here comes from the fact that you're mashing views and containers into one thing. MSubArray is just a view - it doesn't need allocators. If it didn't have them, you wouldn't have recursive allocator definitions. You'd just have:

MyDynArray<T, Dims, Allocator = std::allocator<MSubArray<T, Dims - 1>>>

Still very clunky, but at least possible now. (Alternatively, you could take an allocator of T and use rebind() for the typedefs; that would work now, too.) value_type would be MSubArray<T, Dims - 1>, and so on. The get_first_item() function above would now work.

T* arr;
size_type *sizes;
size_type rowsize;

I'm not sure what the point of rowsize is - it seems like it's meant to be the size of the top-level sub-array. arr I gather is meant to be sometimes pointing to owned memory, sometimes not.

But sizes, as near as I can determine, is always meant to point to owned memory. In that case, it should really be a smart pointer - probably unique_ptr<size_type[]>. But you can go one better, because sizes is always meant to point to an array of dims elements, so why not just skip the indirection and use array<size_type, dims>.

The constructor seems like it could be both constexpr and noexcept.

virtual ~MDynArrayBase() {}

Don't declare defaulted functions like this. Use default:

virtual ~MDynArrayBase() = default;

The benefit of this is that using default makes it trivially destructible - using empty braces does not.

MSubArray

MSubArray<T, dims-1, Allocator> operator[] (size_type i) {
    MSubArray<T, dims-1, Allocator> child(arr + rowsize * i,
        sizes + 1, rowsize / sizes[1]);
    return child;
}

You can probably save yourself a lot of repetition:

MSubArray<T, dims-1, Allocator> operator[] (size_type i) {
    return { arr + rowsize * i, sizes + 1, rowsize / sizes[1] };
}

I would recommend not using default arguments for this:

size_type size(size_type i = 0) const {
    if (i >= dims) {
        throw std::out_of_range("Illegal dimension");
    }
    if (sizes == nullptr) return 0;
    return sizes[i];
}

The reason is that size() is a key function for containers, so you want to make it as safe and as fast as possible. I would suggest having a regular size() function that is noexcept, and then your extended size() function.

size_type size(size_type i) const {
    if (i >= dims)
        throw std::out_of_range{"Illegal dimension"};
    return sizes[i];
}

size_type size() const noexcept { return sizes[0]; }

Also, you keep checking sizes for nullptr... but you don't actually set it to nullptr anywhere (except when when it's about to be overwritten or destroyed). It's good that you're checking, but what you're checking for is a situation that should never happen... so this is really a job for assert(). (I didn't include assert() checks in the code above.) It is certainly not a good idea to silently return zero for something that is clearly a sign of a serious bug.

iterator begin() {
    return iterator(arr, sizes + 1,
        rowsize / sizes[1]);
}

You also need a version of begin() for const objects that returns const_iterator. Same for end().

Almost every member of both classes could be noexcept and constexpr.

MDynArray

Allocator alloc;

You should look into the empty base optimization - it's especially handy for allocators since allocators are very often stateless.

static T* clone(T* src, size_type tot, Allocator alloc) {
    // ...
    catch(std::exception &) {
        // ... (cleanup) ...
        throw;
    }

You don't want to catch std::exception here. You want to catch all exceptions. You want catch (...).

MDynArray(const MDynArray<T, dims, Allocator>& other) 
    : MSubArray(nullptr, nullptr, 0) {
    alloc = other.alloc;
    ownarr = true;
    sizes = new size_type[dims];
    std::copy(other.sizes, other.sizes + dims, sizes);
    rowsize = other.rowsize;
    try {
        arr = clone(other.arr, rowsize * sizes[0], alloc);
    }
    catch (std::exception&) {
        delete[] sizes;
    }
}

This is a really nasty function, due almost entirely to the fact that you're not using smart pointers. Exception safety is a beast. I can see one problem, but I can't be sure there aren't others.

The problem I see is that you first default construct the allocator, then copy it. That's not a good idea. First, allocators are not required to have default constructors. Second, you should probably look into allocator_traits<Allocator>::select_on_container_copy_construction().

There may be a way to eliminate virtually all of this complexity.

First, you'll have to implement an allocator deleter. (I know, there really should be one standardized, but the paper hasn't been approved yet.)

Second, get rid of ownarr. Replace it with unique_ptr<T[], allocator_deleter<Allocator>> arr_; (or whatever you want to name it). I realize it seems silly to keep the pointer in two places - arr and arr_ - but this is because the inheritance path for MDynArray includes both a non-owning view and an owning container.

While you're at it, refactor clone to return a unique_ptr<T[], allocator_deleter<Allocator>>, and use one internally for dst. That will help simplify that function a bit.

Third, either make sizes an array<size_type, dims> as suggested previously, or change it to be unique_ptr<size_type[], allocator_deleter<Allocator>>. It should be a smart pointer at least. And it makes no sense to select an allocator for MDynArray only to have it turn around and use the standard allocator for sizes. For simplicity, I recommend using an array.

If you do these things, this copy constructor simplifies to:

MDynArray(const MDynArray<T, dims, Allocator>& other) 
    : MSubArray{nullptr, other.sizes, other.rowsize}
    , alloc{allocator_traits<Allocator>::select_on_container_copy_construction(other.alloc)} {
    arr_ = clone(other.arr, rowsize * sizes[0], alloc);
    arr = arr_.get();
}

and you have no more exception safety worries.

And that's not all. Your move constructor, move assignment, and destructor can now be defaulted.

Smart pointers are magic.

ArrayBuilder

I confess I don't understand the point of this class. You say it's because you couldn't make constructors or static methods to handle all your use cases... but you could almost copy-paste the three functions you've got into MDynArray.

I have to guess what your sticking points are. I'm assuming it's either handling a variable number of size arguments, or that plus an optional allocator argument.

Let me use ArrayBuilder<T, Allocator>::dynUseArray() as the example. If that were moved to be a static method in MDynArray, its signature would probably change to:

template <typename... SizeType>
MDynArray dynUseArray(T* arr, SizeType... sizes);

The obvious first step is to ensure you have the right number of sizes:

template <typename... SizeType>
auto dynUseArray(T* arr, SizeType... sizes) ->
    enable_if_t<(sizeof...(sizes) == dims), MDynArray>;

Next you'll want to ensure that all the types in SizeType... are convertible to size_type. For that you could make a traits class all_are_convertible<T, U...> that just checks that std::is_convertible<U, T> is true for every U in the pack:

template <typename... SizeType>
auto dynUseArray(T* arr, SizeType... sizes) ->
    enable_if_t<(sizeof...(sizes) == dims) && all_are_convertible<size_type, SizeType...>::value, MDynArray>;

For even more clarity, you can wrap both checks up in a single type trait is_n_sizes<N, SizeType, T...>:

template <typename... SizeType>
auto dynUseArray(T* arr, SizeType... sizes) ->
    enable_if_t<is_n_sizes<dims, size_type, SizeType...>::value, MDynArray>;

Lastly there's the issue of allocator arguments. Those are usually handled with allocator_arg_t. You'd just need a pair of functions:

template <typename... SizeType>
auto dynUseArray(std::allocator_arg_t, Allocator const& alloc, T* arr, SizeType... sizes) ->
    enable_if_t<is_n_sizes<dims, size_type, SizeType...>::value, MDynArray>;

template <typename... SizeType>
auto dynUseArray(T* arr, SizeType... sizes) ->
    enable_if_t<is_n_sizes<dims, size_type, SizeType...>::value, MDynArray>
{
    return dynUseArray(std::allocator_arg, Allocator{}, arr, sizes...);
}

And there you go.

If you go with sizes data member as an array, the implementation if the main function above would be something like:

template <typename... SizeType>
auto dynUseArray(std::allocator_arg_t, Allocator const& alloc, T* arr, SizeType... sizes) ->
    enable_if_t<is_n_sizes<dims, size_type, SizeType...>::value, MDynArray>
{
    return MDynArray{
        arr, // arr : non-owning pointer to data
        std::array<size_type, dims>{sizes...}, // sizes

        // rowsize? : if you need this, it looks like just
        // std::accumulate or std::reduce with std::multiplies
        // and the sizes array

        nullptr, // arr_ : smart pointer set to null because non-owning
        alloc // allocator
    };
}

And you'd call it like:

// 3 x 3 x 3 array
auto buffer = std::vector<int>(27);
auto m3x3x3 = MDynArray<int, 3>::dynUseArray(buffer.data(), 3, 3, 3);

// 5 x 4 array with allocator
auto buf2 = std::array<float, 20>{};
auto ma5x4 = MDynArray<int, 2, my_allocator>::dynUseArray(std::allocator_arg, my_allocator{}, buf2.data(), 5, 4);

And similar logic for the other 3 functions.

You could even make them all constructors, if you want, with tags to differentiate.

MDynIteratorBase

The iterator types have to be the most confusing parts of this entire code base, and that's saying a lot. The logical place to define them would be inside MSubArray (the non-specialized version). Instead they're defined almost 300 lines later... spread over two classes... except with some template arguments defined over 300 lines previously in the forward declarations... and of course everything is friended, so I can't just read the iterator code, I also need to read everything else in between. To figure out what's going on with those iterators, I almost literally have to jump back and forth to every extreme while reading every line of your code. And... they're just iterators, and not even particularly complex ones at that. There's no need for that level of complexity.

All of this complexity would vanish if you defined the iterator class inside MSubArray. No more code spread all over the place, no more friending everything, no more forward declarations... you wouldn't even need two iterator classes anymore.

Iterators in general are mostly boilerplate, so there normally wouldn't be much to comment on. However, as usual, the mixing of views and containers in your inheritance tree complicates things.

using itbase = typename MDynIteratorBase<T, dims, Allocator>;

You don't really need this typedef. Within the class you can just use MDynIteratorBase... no template params.

MSubArray<T, dims, Allocator> elt;

Iterators are supposed to be lightweight pointers into data structures... but your iterators literally are the data structures, and then some. This is because you're doing some dodgy stuff with regards to references and values - you can't actually have your iterator return a reference to what it's supposed to be pointing to, because it's actually just pointing directly into the guts of the parent object. So you fake it by keeping an item internal to the iterator that you can return references to.

Rather than this, you should probably just accept that your iterators are not like standard vector iterators or list iterators or like most iterators in the standard library. Your iterators are like vector<bool> iterators - they work with proxy objects. In your array class, reference is not T& (as I've already explained) or even value_type&, which is MSubArray<T, dims - 1, Allocator>&. Your reference is a view object: MSubArray<T, dims - 1, Allocator> (note: no &).

Thus your iterators, like vector<bool>'s, should return proxy objects. Not references to anything. You'll also need pointer proxies.

bool operator ==(const itbase& other) const {
    return (elt.arr == other.elt.arr) && (elt.sizes == other.elt.sizes)
        && (elt.rowsize == other.elt.rowsize);
}
// ...
bool operator <(const itbase& other) const {
    return elt.arr < other.elt.arr;
}

Operators should normally be defined outside the class. This makes things a lot easier, too, if your iterator has an implicit conversion to const_iterator, which it should. Then you just need to define operator==(const_iterator, const_iterator), and implicit conversions will take care of mixed comparisons.

But the more important problem here is that your operator< doesn't respect the same rules as operator==. Either it's necessary to check sizes and rowsize for equality or it's not. (It is, because you can create two MDynArrays that are using the same memory, but viewing it as differently sized arrays.)

template <class T, int dims, int cnst, class Allocator, class U>

cnst should really be bool, not int.

Summary

The main issue is that you are trying to make one class (hierarchy) that is too many different things at once. If you're making a multidimensional array view and a multidimensional array container, that's fine... but those are two very different things, with very different responsibilities and usage patterns. You can't really slam them both into a single type.

And if you have to give one up, the logical choice is the container. If you're already making a view that can work with arbitrary data, what do you gain from making a container as well? Any container that holds contiguous data will work, so there's nothing to gain from rolling your own except grief.

If you abandon the idea of building a container and instead only make views, ~80% of the complexity of this code will vanish.

The remaining complexity will be due to the fact that you're going to need reference and pointer proxies, because you can't have true references or pointers due to your view data being structured while the actual underlying data is not. And you can't even really "cheat" the way you do (by having the iterators hold the entire data structure internally), because that will make the reference type different between the main class and its iterators. All of that is a pain, and it will make your views harder to use (just like vector<bool>), but them's the breaks.

Answer 2

The God-object

I really wanted to make sure I was not using anti patterns before keeping on...

Well, you're a bit late on that. The anti-pattern began when you defined the array's responsibilities:

I want to be able to

• build a new dynamic array from scratch

• have it copy an existing raw array

• have it use (no copy here) an existing raw array taking or not ownership

Your multi-dimensional array is an example of the god-object anti-pattern, where an object has too many functions, leading to complex, unmaintainable code.

Separation of concern

As @Indi pointed out, you need to separate two different concerns: storing/owning data on the one hand, viewing it on the other hand. It doesn't mean you can't cope with the different use-cases you've described.

Fundamentally, a dynamic contiguous multi-dimensional array is two things: a vector of dimensions' sizes, and a contiguous one-dimensional array. So let's go through your use-cases:

gather data from network and return a dynamic array declaring its dimensions.

auto gather_multi_dimensional_array_from_network(Connection& c) {
    std::vector<double> data;
    std::vector<std::size_t> dimensions;
    // ...
    return std::pair{ data, dimensions }; // c++17 or specify underlying types
}

wrap (no ownership here) an existing array coming from a C API

template <typename T>
auto wrap_array_with_multi_dimensional_view(T* array, std::size_t array_size) {
    std::vector<std::size_t> dimensions = deduce_dimensions(array, array_size);
    return std::pair{ array, dimensions };
}

At that point (not having introduced any new object) you already have a lot of what you were looking for: iterators, algorithm compatibility, dynamic storage, non-owning pointer, etc.

What you still need is a way to go from the returned pairs to a multi-dimensional view. That's quite easy: either you get a pointer/iterator and a vector of dimensions, and you're set; or you get a container and a vector of dimensions: then you apply std::begin to the container and you're back to the first case. Distinguishing between an iterator and a container can be done with SFINAE for now, and you'll be able to rely on concepts soon enough:

struct MDView {
    template <typename Iterator>
    MDView(Iterator it, const std::vector<int>& dimensions) {...}
    // insert multi-dimensional viewing capabilities here
};

template <typename Source>
auto make_mdv(const Source& src, const std::vector<int>& dimensions) ->  decltype( MDView(std::begin(src), dimensions) ) {
    MDView res(std::begin(src), dimensions); 
    return res;
}

template <typename Source>
auto make_mdv(const Source& src, const std::vector<int>& dimensions) ->  decltype( *Source(), MDView(src, dimensions) ) {
    MDView res(src, dimensions); 
    return res;
}

One iterator and the vector of the dimensions' sizes are enough to fetch an element from given indices.

Conclusion

I understand quite well that it isn't the review you were looking for (@Indi's is much better) and that throwing away code you sweated for is painful (and the more complex the code is, the more sweat you shed on it), but you really ask too much from a single class.