Simple multi-dimensional Array class in C++11

Question

The new version of the code can be reviewed in Simple multi-dimensional Array class in C++11 - follow-up.

---

The following code implements a simple multi-dimensional array class (hyper_array::array).

I modeled most (if not all) the feature on the orca_array.hpp header by Pramod Gupta after watching his talk at this year's cppcon.

I think that orca_array is fine. However, a more generic implementation might prove interesting as well (e.g. reducing code repetition, gaining more efficiency through compile-time computations/verification and allowing more dimensions (even though the relevance of the latter feature is debatable)).

The element type and the number of dimensions is given at compile-time. The length along each dimension is specified at run-time.

As a start, there are 2 configuration options:

• HYPER_ARRAY_CONFIG_Check_Bounds: controls run-time checking of index bounds,
• HYPER_ARRAY_CONFIG_Overload_Stream_Operator: enables/disables the overloading of operator<<(std::ostream&, const hyper_array::array&).

The implementation requires some C++11 features and uses very basic template (meta)programming and constexpr computation when possible.

I have mainly the following goals:

• Self-contained (no dependency to external libraries), single-header implementation
• Minimal code repetition (if any) and clarity/"readability" of implementation
• Conforming to "good" programming practices in modern C++ while developing a solution that might prove interesting to use for others
• Clean API "that makes sense" to the user
• As much compile-time computation/evaluation/input validation as possible (template-metaprogramming, constexpr?)
• Maximum efficiency while remaining written in standard C++11 (I made an exception once for std::make_unique(), but I'll probably remove it),
• Allow inclusion in STL containers while still being efficient

My current concerns are:

• I'm sure that many computations could be done and for loops could be unwound at compile time, but I haven't wrapped my head around template metaprogramming yet to come up with an appropriate solution,
• Performance,
• The API: it's still very basic, but I'm open to suggestions for making it more relevant (orca_array was just my starting point).

Run The Code Online

hyper_array.hp`

#pragma once

// make sure that -std=c++11 or -std=c++14 ... is enabled in case of clang and gcc
#if (__cplusplus < 201103L)  // C++11 ?
    #error "hyper_array requires a C++11-capable compiler"
#endif

// <editor-fold desc="Configuration">
#ifndef HYPER_ARRAY_CONFIG_Check_Bounds
/// Enables/disables run-time validation of indices in methods like [hyper_array::array::at()](@ref hyper_array::array::at())
/// This setting can be overridden by defining `HYPER_ARRAY_CONFIG_Check_Bounds` before the inclusion
/// of this header or in the compiler arguments (e.g. `-DHYPER_ARRAY_CONFIG_Check_Bounds=0` in gcc and clang)
#define HYPER_ARRAY_CONFIG_Check_Bounds 1
#endif

#ifndef HYPER_ARRAY_CONFIG_Overload_Stream_Operator
/// Enables/disables `operator<<()` overloading for hyper_array::array
#define HYPER_ARRAY_CONFIG_Overload_Stream_Operator 1
#endif
// </editor-fold>

// <editor-fold desc="Includes">
// std
//#include <algorithm>  // used during dev, replaced by compile-time equivalents in hyper_array::internal
#include <array>        // std::array for hyper_array::array::dimensionLengths and indexCoeffs
#include <memory>       // unique_ptr for hyper_array::array::_dataOwner
#if HYPER_ARRAY_CONFIG_Overload_Stream_Operator
#include <ostream>      // ostream for the overloaded operator<<()
#endif
#if HYPER_ARRAY_CONFIG_Check_Bounds
#include <sstream>      // stringstream in hyper_array::array::validateIndexRanges()
#endif
#include <type_traits>  // template metaprogramming stuff in hyper_array::internal
// </editor-fold>


/// The hyper_array lib's namespace
namespace hyper_array
{

// <editor-fold defaultstate="collapsed" desc="Internal Helper Blocks">
/// Helper functions for hyper_array::array's implementation
/// @note Everything related to this namespace is subject to change and must not be used by user code
namespace internal
{
    /// Checks that all the template arguments are integral types using `std::is_integral`
    template <typename T, typename... Ts>
    struct are_integral
    : std::integral_constant<bool,
                             std::is_integral<T>::value
                             && are_integral<Ts...>::value>
    {};

    template <typename T>
    struct are_integral<T>
    : std::is_integral<T>
    {};

    /// Compile-time sum
    template <typename T>
    constexpr T ct_plus(const T x, const T y)
    {
        return x + y;
    }

    /// Compile-time product
    template <typename T>
    constexpr T ct_prod(const T x, const T y)
    {
        return x * y;
    }

    /// Compile-time equivalent to `std::accumulate()`
    template
    <
        typename    T,  ///< result type
        std::size_t N,  ///< length of the array
        typename    O   ///< type of the binary operation
    >
    constexpr T ct_accumulate(const ::std::array<T, N>& arr,  ///< accumulate from this array
                              const size_t first,             ///< starting from this position
                              const size_t length,            ///< accumulate this number of elements
                              const T      initialValue,      ///< let this be the accumulator's initial value
                              const O&     op                 ///< use this binary operation
                             )
    {
        // https://stackoverflow.com/a/33158265/865719
        return (first < (first + length))
             ? op(arr[first],
                  ct_accumulate(arr,
                                first + 1,
                                length - 1,
                                initialValue,
                                op))
             : initialValue;
    }

    /// Compile-time equivalent to `std::inner_product()`
    template
    <
        typename T,      ///< the result type
        typename T_1,    ///< first array's type
        size_t   N_1,    ///< length of the first array
        typename T_2,    ///< second array's type
        size_t   N_2,    ///< length of the second array
        typename O_SUM,  ///< summation operation's type
        typename O_PROD  ///< multiplication operation's type
    >
    constexpr T ct_inner_product(const ::std::array<T_1, N_1>& arr_1,  ///< perform the inner product of this array
                                 const size_t  first_1,                ///< from this position
                                 const ::std::array<T_2, N_2>& arr_2,  ///< with this array
                                 const size_t  first_2,                ///< from this position
                                 const size_t  length,                 ///< using this many elements from both arrays
                                 const T       initialValue,           ///< let this be the summation's initial value
                                 const O_SUM&  op_sum,                 ///< use this as the summation operator
                                 const O_PROD& op_prod                 ///< use this as the multiplication operator
                                )
    {
        // same logic as `ct_accumulate()`
        return (first_1 < (first_1 + length))
             ? op_sum(op_prod(arr_1[first_1], arr_2[first_2]),
                      ct_inner_product(arr_1, first_1 + 1,
                                       arr_2, first_2 + 1,
                                       length - 1,
                                       initialValue,
                                       op_sum, op_prod))
             : initialValue;
    }
}
// </editor-fold>

/// A multi-dimensional array
/// Inspired by [orca_array](https://github.com/astrobiology/orca_array)
template
<
    typename ElementType,  ///< elements' type
    size_t   Dimensions    ///< number of dimensions
>
class array
{
    // Types ///////////////////////////////////////////////////////////////////////////////////////

public:
    using SizeType  = size_t;  ///< used for measuring sizes and lengths
    using IndexType = size_t;  ///< used for indices

    // Attributes //////////////////////////////////////////////////////////////////////////////////

    // <editor-fold desc="Static Attributes">
public:
    static constexpr SizeType dimensions = Dimensions;
    // </editor-fold>

    // <editor-fold desc="Class Attributes">
public:
    // ::std::array's are used  here mainly because they are initializable
    // from `std::initialzer_list` and they support move semantics
    // cf. hyper_array::array's constructors
    // I might replace them with a "lighter" structure if it satisfies the above 2 requirements

    const ::std::array<SizeType, Dimensions> dimensionLengths;  ///< number of elements in each dimension
    const SizeType                           dataLength;        ///< total number of elements in [data](@ref data)
    const ::std::array<SizeType, Dimensions> indexCoeffs;       ///< coefficients to use when computing the index
                                                                ///< C_i = \prod_{j=i+1}^{n-2} L_j  if i in [0, n-2]
                                                                ///<     | 1                        if i == n-1
                                                                ///<
                                                                ///< where n   : Dimensions - 1  (indices start from 0)
                                                                ///<     | C_i : indexCoeffs[i]
                                                                ///<     | L_j : dimensionLengths[j]
                                                                ///< @see at()
private:
    /// handles the lifecycle of the dynamically allocated data array
    /// The user doesn't need to access it directly
    /// If the user needs access to the allocated array, they can use [data](@ref data) (constant pointer)
    std::unique_ptr<ElementType[]> _dataOwner;
public:
    /// points to the allocated data array
    ElementType* const                 data;
    // </editor-fold>

    // methods /////////////////////////////////////////////////////////////////////////////////////

public:

    /// It doesn't make sense to create an array without specifying the dimension lengths
    array()             = delete;

    /// no copy-construction allowed (orca_array-like behavior)
    array(const array&) = delete;

    /// enable move construction
    /// allows inclusion of hyper arrays in e.g. STL containers
    array(array<ElementType, Dimensions>&& other)
    : dimensionLengths (std::move(other.dimensionLengths))
    , dataLength       {other.dataLength}
    , indexCoeffs      (std::move(other.indexCoeffs))
    , _dataOwner       {other._dataOwner.release()}   // ^_^
    , data             {_dataOwner.get()}
    {}

    /// the usual way for constructing hyper arrays
    template <typename... DimensionLengths>
    array(DimensionLengths&&... dimensions)
    : dimensionLengths{{static_cast<SizeType>(dimensions)...}}
    , dataLength{internal::ct_accumulate(dimensionLengths,
                                          0,
                                          Dimensions,
                                          static_cast<SizeType>(1),
                                          internal::ct_prod<SizeType>)}
    , indexCoeffs([this] {
            ::std::array<SizeType, Dimensions> coeffs;
            coeffs[Dimensions - 1] = 1;
            for (SizeType i = 0; i < (Dimensions - 1); ++i)
            {
                coeffs[i] = internal::ct_accumulate(dimensionLengths,
                                                    i + 1,
                                                    Dimensions - i - 1,
                                                    static_cast<SizeType>(1),
                                                    internal::ct_prod<SizeType>);
            }
            return coeffs;  // hopefully, NRVO should kick in here
      }())
    #if (__cplusplus < 201402L)  // C++14 ?
    , _dataOwner{new ElementType[dataLength]}  // std::make_unique() is not part of C++11 :(
    #else
    , _dataOwner{std::make_unique<ElementType[]>(dataLength)}
    #endif
    , data{_dataOwner.get()}
    {
        // compile-time input validation
        // can't put them during dimensionLengths' initialization, so they're here now
        static_assert(sizeof...(DimensionLengths) == Dimensions,
                      "The number of dimension lengths must be the same as "
                      "the array's number of dimensions (i.e. \"Dimentions\")");
        static_assert(internal::are_integral<
                          typename std::remove_reference<DimensionLengths>::type...
                      >::value,
                      "The dimension lengths must be of integral types");
    }

    /// Returns the length of a given dimension at run-time
    SizeType length(const size_t dimensionIndex) const
    {
        #if HYPER_ARRAY_CONFIG_Check_Bounds
        if (dimensionIndex >= Dimensions)
        {
            throw std::out_of_range("The dimension index must be within [0, Dimensions-1]");
        }
        #endif

        return dimensionLengths[dimensionIndex];
    }

    /// Compile-time version of [length()](@ref length())
    template <size_t DimensionIndex>
    SizeType length() const
    {
        static_assert(DimensionIndex < Dimensions,
                      "The dimension index must be within [0, Dimensions-1]");

        return dimensionLengths[DimensionIndex];
    }

    /// Returns the element at the given index tuple
    /// Usage:
    /// @code
    ///     hyper_array::array<double, 3> arr(4, 5, 6);
    ///     arr.at(3, 1, 4) = 3.14;
    /// @endcode
    template<typename... Indices>
    ElementType& at(Indices&&... indices)
    {
        return data[rawIndex(std::forward<Indices>(indices)...)];
    }

    /// `const` version of [at()](@ref at())
    template<typename... Indices>
    const ElementType& at(Indices&&... indices) const
    {
        return data[rawIndex(std::forward<Indices>(indices)...)];
    }

    /// Returns the actual index of the element in the [data](@ref data) array
    /// Usage:
    /// @code
    ///     hyper_array::array<int, 3> arr(4, 5, 6);
    ///     assert(&arr.at(3, 1, 4) == &arr.data[arr.rawIndex(3, 1, 4)]);
    /// @endcode
    template<typename... Indices>
    IndexType rawIndex(Indices&&... indices) const
    {
        #if HYPER_ARRAY_CONFIG_Check_Bounds
        return rawIndex_noChecks(validateIndexRanges(std::forward<Indices>(indices)...));
        #else
        return rawIndex_noChecks({static_cast<IndexType>(indices)...});
        #endif
    }

private:

    #if HYPER_ARRAY_CONFIG_Check_Bounds
    template<typename... Indices>
    ::std::array<IndexType, Dimensions> validateIndexRanges(Indices&&... indices) const
    {
        // compile-time input validation
        static_assert(sizeof...(Indices) == Dimensions,
                      "The number of indices must be the same as "
                      "the array's number of dimensions (i.e. \"Dimentions\")");
        static_assert(internal::are_integral<
                          typename std::remove_reference<Indices>::type...
                      >::value,
                      "The indices must be of integral types");

        // runtime input validation
        ::std::array<IndexType, Dimensions> indexArray = {{static_cast<IndexType>(indices)...}};

        // check all indices and prepare an exhaustive report (in oss)
        // if some of them are out of bounds
        std::ostringstream oss;
        for (size_t i = 0; i < Dimensions; ++i)
        {
            if ((indexArray[i] >= dimensionLengths[i]) || (indexArray[i] < 0))
            {
                oss << "Index #" << i << " [== " << indexArray[i] << "]"
                    << " is out of the [0, " << (dimensionLengths[i]-1) << "] range. ";
            }
        }

        // if nothing has been written to oss then all indices are valid
        if (oss.str().empty())
        {
            return indexArray;
        }
        else
        {
            throw std::out_of_range(oss.str());
        }
    }
    #endif

    IndexType rawIndex_noChecks(::std::array<IndexType, Dimensions>&& indexArray) const
    {
        // I_{actual} = \sum_{i=0}^{N-1} {C_i \cdot I_i}
        //
        // where I_{actual} : actual index of the data in the data array
        //       N          : Dimensions
        //       C_i        : indexCoeffs[i]
        //       I_i        : indexArray[i]
        return internal::ct_inner_product(indexCoeffs, 0,
                                          indexArray, 0,
                                          Dimensions,
                                          static_cast<IndexType>(0),
                                          internal::ct_plus<IndexType>,
                                          internal::ct_prod<IndexType>);
    }

};

// <editor-fold desc="orca_array-like declarations">
template<typename ElementType> using array1d = array<ElementType, 1>;
template<typename ElementType> using array2d = array<ElementType, 2>;
template<typename ElementType> using array3d = array<ElementType, 3>;
template<typename ElementType> using array4d = array<ElementType, 4>;
template<typename ElementType> using array5d = array<ElementType, 5>;
template<typename ElementType> using array6d = array<ElementType, 6>;
template<typename ElementType> using array7d = array<ElementType, 7>;
// </editor-fold>

}

#if HYPER_ARRAY_CONFIG_Overload_Stream_Operator
/// Pretty printing to STL streams
/// Should print something like
/// @code
///     [Dimensions:1];[dimensionLengths: 5 ];[dataLength:5];[indexCoeffs: 1 ];[data: 0 1 2 3 4 ]
/// @endcode
template <typename T, size_t D>
std::ostream& operator<<(std::ostream& out, const hyper_array::array<T, D>& ha)
{
    out << "[Dimensions:" << ha.dimensions << "]";

    out << ";[dimensionLengths: ";
    for (auto& dl : ha.dimensionLengths)
    {
        out << dl << " ";
    }
    out << "]";

    out << ";[dataLength:" << ha.dataLength << "]";

    out << ";[indexCoeffs: ";
    for (auto& ic : ha.indexCoeffs)
    {
        out << ic << " ";
    }
    out << "]";

    out << ";[data: ";
    for (typename hyper_array::array<T, D>::IndexType i = 0; i < ha.dataLength; ++i)
    {
        out << ha.data[i] << " ";
    }
    out << "]";

    return out;
}
#endif

Test program

// g++ -std=c++11 -std=c++11 -fdiagnostics-show-option -Wall -Wextra -Wpedantic -Werror -Wconversion hyper_array_playground.cpp -o hyper_array_playground

#include <iostream>
#include <vector>

#include "hyper_array/hyper_array.hpp"


using namespace std;

int main()
{
    // 3d array
    {
        hyper_array::array3d<double> a{2, 3, 4};

        int c = 0;
        for (size_t i = 0; i < a.length<0>(); ++i)          // hyper_array
        {                                                   // should
            for (size_t j = 0; j < a.length<1>(); ++j)      // probably
            {                                               // implement
                for (size_t k = 0; k < a.length<2>(); ++k)  // some
                {                                           // kind
                    a.at(i, j, k) = c++;                    // of
                }                                           // iterator
            }                                               // to prevent
        }                                                   // so much typing

        cout << a << endl;
        cout << "(a.length(1) == a.length<1>()): " << (a.length(1) == a.length<1>()) << endl;
    }

    // 1D array
    {
        hyper_array::array1d<double> a{5};

        int         c = 0;
        for (size_t i = 0; i < a.length<0>(); ++i)
        {
            a.at(i) = c++;
        }

        cout << a << endl;
    }

    // size w.r.t. std::array
    {
        constexpr size_t elementCount = 10;
        hyper_array::array1d<double> aa{hyper_array::array1d<double>{elementCount}};

        // 40 bytes bigger than std::array...
        cout << "sizeof(aa):         " << (sizeof(aa) + (elementCount*sizeof(double))) << endl;
        cout << "sizeof(std::array): " << sizeof(std::array<double, elementCount>) << endl;

    }

    // in STL containers (e.g. std::vector)
    {
        vector<hyper_array::array2d<double>> v;
        v.emplace_back(hyper_array::array2d<double>{1,2});
        v.push_back(hyper_array::array2d<double>{2,1});
    }


    cout << "done" << endl;
}

---

New versions of hyper_array can now be found on Github.

Answer 1

I think your class isn't nearly as useful enough as it could be due to your choices in member variables. Furthermore, it's less efficient than it could be. Also the code is written in a style that overcomplicates the problem.

Member Variables

Your members are:

std::unique_ptr<ElementType[]>
ElementType* const
const std::array<SizeType, Dimensions>
const SizeType
const std::array<SizeType, Dimensions>

This choice makes the class noncopyable and nonassignable. But why? There's nothing inherent about a multidimensional array that suggests it shouldn't be assignable or copyable. You make some members public. There's no reason to do that. Particularly bad is data - which is redundant with _dataOwner.

You should strive to make your class as generic as possible. To that end I suggest you simply have two members, both private:

ElementType* data;
std::array<size_t, Dimensions> dimensions;

You can derive dataLength and indexCoeffs from dimensions if need be, and since you'd have to iterate over the array to do anything anyway, I don't see what precomputing saves you.

This also allows you do support copying and moving.

Forwarding References

Forwarding references are a great choice for function templates when you can take objects by lvalue or rvalue and do the cheapest correct thing possible in all cases. However, everywhere that you are using them, the objects getting past in must be integral types (I don't see you checking this, but you should). There is no different between copying and moving an integral type, so simply take everything by value. That saves you from having to do all of the std::forward<>-ing. For example:

template <class... Indices>
ElementType& at(Indices... indices)
{
    return data[rawIndex(indices...)];
}

Bounds Checking

You introduce a macro for whether or not to do bounds checking. However, convention from the standard library suggests that we just provide functions that DO range checking and functions that don't. at() should throw std::out_of_range, and operator() should never throw:

template <typename... Indices>
ElementType& operator()(Indices... indices) {
    // nothrow implementation
}

template <typename... Indices>
ElementType& at(Indices... indices)
{
    some_range_checking(indices...);
    return (*this)(indices...);
}

Compile time checking

First, a cleaner way to write are_integral would be to use the bool_pack trick:

template <bool... > struct bool_pack { };

template <bool... b>
using all_true = std::is_same<bool_pack<true, b...>, bool_pack<b..., true>>;

With:

template <typename... T>
using are_all_integral = all_true<std::is_integral<T>::value...>;

And you should actually use that metafunction as part of the signature of every function! That is preferred to a simple static_assert since any reflection-style operations on your class would actually yield the correct result:

template <typename.... DimensionLengths,
          typename = std::enable_if_t<are_all_integral<DimensionLengths...>::value && sizeof...(DimensionLengths) == Dimensions>
          >
array(DimensionLengths... )
{ ... }

Otherwise, you would get something weird like std::is_constructible<array<int, 4>, std::string> being true.

Iterators

An important part of writing a container is writing iterators for it. You may just provide general iterators that just go over the whole array front to end. Or you may want to support arrays that iterate over a single dimension and provide a proxy object to a multi-dimensional array of one dimension less. Either would be good to have.