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.

• Deduplicator: Should move-assignment really be forbidden?
• maddouri: Since the class does have a move constructor, I assume you're talking about operator=(array&& rhs). I'm not sure. Especially since all attributes are const (at the exception of _dataOwner). But I guess it might make sense if the rhs has exactly the same number of dimensions and the same lengths in each dimension.

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.

• maddouri: Cool, thanks for the review! I'll try to fix the issues you mentioned while waiting of others to give their opinions (hopefully :) ). I do agree that, even though I was going for a "minimal" implementation, a few attributes are redundant. Concerning the index calculation from at()'s integer list (which I do actually check, in validateIndexRanges()): I still think it's better to have the coefficients precomputed (but I'll need to support that with performance measurements...). As you mentioned, having operator() and at() is probably better than the (evil) macro (which I hate :) )
• maddouri: I'm going to have to re-read your comment on "Compile time checking", I'm not yet familiar with the approach you've mentioned. Finally, I'm going to research the "Iterators" feature and see how I could integrate it in the next... iteration of this class.
• Deduplicator: Regarding bounds-checking: We often have a DEBUG-toggle enabling all kinds of extra-assertions, even if performance or layout-compatibility must be sacrificed to allow that. (So, there's the debug and the non-debug flavor, which are just barely API-compatible.)
• maddouri: Thanks. It does make sense to enable extra verification for the debug version. I'll definitely keep that in mind for round 2 of this code review!
• maddouri: @Barry : Quick followup: isn't all_same supposed to actually be template <bool b, bool... bs> using all_same = std::is_same<bool_pack<b, bs...>, bool_pack<bs..., b>>; ? (because, in your version, all_same<false, false, false>::value == false whereas it should be true.