Multi-dimensional dimension type

Question

Introduction

When implementing a one-dimensional array, you need to keep track of the size. Such quantities are best represented by std::size_t:

std::size_t count;

Analogously, when implementing a multi-dimensional array, you need to store the dimensions. This time, a one-dimensional std::size_t does not suffice. You need multiple dimensions. Of course, something like this suffices:

std::array<std::size_t, N> dims;

but in my opinion, it makes more sense to use a dedicated type. As such, I implemented a multi-dimensional dimension type in C++17, so that you can use:

Dimensions<N> dims;

A common operation is to convert from multiple indices to one flat index. For example, given a 3 × 4 2-dimensional array indexed by 2-dimensional indices:

+--------+--------+--------+
| (0, 0) | (0, 1) | (0, 2) |
+--------+--------+--------+
| (1, 0) | (1, 1) | (1, 2) |
+--------+--------+--------+
| (2, 0) | (2, 1) | (2, 2) |
+--------+--------+--------+
| (3, 0) | (3, 1) | (3, 2) |
+--------+--------+--------+

The corresponding flat indices look like:

+----+----+----+
| 0 | 1 | 2 |
+----+----+----+
| 3 | 4 | 5 |
+----+----+----+
| 6 | 7 | 8 |
+----+----+----+
| 9 | 10 | 11 |
+----+----+----+

This operation is the core part. The at member function is provided, and operator() is also supported for convenience:

Dimensions<2> dims{4, 3};
dims(1, 2) // returns 5
dims.at({1, 2}) // returns 5

The practice in the standard library is that operator[] (in this case, operator()) does no error checking, whereas at throws an exception on out-of-range input. However, my principle is that error checking should be an opt-out feature instead of opt-in. As such, both operator() and at do error checking by default. It is even possible to do it manually:

dims.valid({1, 2}) // returns true
dims.valid({4, 2}) // returns false

That said, sometimes it is truly unnecessary, and I decided to trust the user in such cases. It is also possible to disable error checking if you know what you are doing:

dims.at(unchecked, {1, 2}) // returns 5, no error checking

This way, you don't accidentally bypass the check, but can do intentionally. Here, unchecked is an object used to disambiguate, similar to std::allocator_arg, std::in_place, etc.

Code

Here's the header dimension.hpp:

/**
 * @file dimension.hpp
 * Implements multi-dimensional utilities.
 */
#ifndef INC_DIMENSION_HPP_CAdUgZHijL
#define INC_DIMENSION_HPP_CAdUgZHijL
#include <array>
#include <cstddef>
#include <stdexcept>
#include <type_traits>
/**
 * L. F.'s library
 */
namespace LF_lib {
/**
 * Multi-dimensional utilities.
 */
namespace multi {
 /**
 * Tag type to indicate unchecked versions of functions.
 */
 struct unchecked_t {
 explicit unchecked_t() = default;
 };
 /**
 * Tag object to indicate unchecked versions of functions.
 */
 inline constexpr unchecked_t unchecked{};
 /**
 * Encapsulates @c N dimensions.
 * Aggregate type that only contains one public member of type <tt>std::array<std::size_t, N></tt>.
 * @c N can be zero.
 *
 * @tparam N The number of dimensions
 */
 template <std::size_t N>
 struct Dimension {
 using dimension_t = std::array<std::size_t, N>; ///< Type for dimensions.
 using index_t = std::array<std::size_t, N>; ///< Type for indices.
 dimension_t dimensions; ///< Stores the @c N dimensions.
 /**
 * @name Observers
 * @{
 */
 /**
 * Returns the number of dimensions.
 *
 * @return @c N
 */
 static constexpr std::size_t order() noexcept { return N; }
 /**
 * Returns the total size.
 *
 * @return The product of all dimensions
 */
 constexpr std::size_t size() const noexcept
 {
 std::size_t res = 1;
 for (std::size_t dim : dimensions)
 res *= dim;
 return res;
 }
 /**
 * @}
 */
 /**
 * @name Element access
 * @{
 */
 /**
 * Checks whether the given indices are in range.
 *
 * @param indices The indices
 *
 * @return @c true if <tt>indices[i] < dimensions[i]</tt> for <tt>i = 0, 1, 2, ..., N-1</tt>, @c false otherwise
 */
 constexpr bool valid(const index_t& indices) const noexcept
 {
 for (std::size_t i = 0; i < N; ++i)
 if (indices[i] >= dimensions[i])
 return false;
 return true;
 }
 /**
 * Returns the flat index of the element at @c indices.
 *
 * @param indices The indices
 *
 * @pre <tt>valid(indices)</tt>
 * @throw std::out_of_range At least one index is out of range
 *
 * @return <tt>(...((indices[0] * dimensions[1] + indices[1]) * dimensions[2] + indices[2]) * ...) * dimensions[N-1] + indices[N-1]</tt>
 */
 constexpr std::size_t at(const index_t& indices) const
 {
 if (!valid(indices))
 throw std::out_of_range{"LF_lib::multi::Dimension<N>::at "
 "indices out of range"};
 return at(unchecked, indices);
 }
 /**
 * Unchecked version of @c at.
 */
 constexpr std::size_t at(unchecked_t, const index_t& indices) const noexcept
 {
 std::size_t res = 0;
 for (std::size_t i = 0; i < N; ++i)
 res = res * dimensions[i] + indices[i];
 return res;
 }
 /**
 * Parentheses notation of @c at.
 * Let <tt>indices</tt> denote <tt>index_t{static_cast<std::size_t>(args)...}</tt>.
 *
 * @tparam Args The types of the indices
 * @param args The indices
 *
 * @pre <tt>sizeof...(Args) == N</tt>
 * @pre <tt>std::conjunction_v<std::is_convertible<Args, std::size_t>...></tt>
 * @pre <tt>valid(indices)</tt>
 * @return <tt>at(indices)</tt>
 * @throw std::out_of_range At least one index is out of range
 */
 template <typename... Args>
 constexpr std::size_t operator()(Args&&... args) const
 {
 static_assert(sizeof...(Args) == N,
 "LF_lib::multi::Dimension<N>::operator() "
 "must be called with N arguments");
 static_assert(std::conjunction_v<std::is_convertible<Args, std::size_t>...>,
 "LF_lib::multi::Dimension<N>::operator() "
 "must be called with arguments "
 "implicitly convertible to std::size_t");
 index_t indices{static_cast<std::size_t>(args)...};
 if (!valid(indices))
 throw std::out_of_range{"LF_lib::multi::Dimension<N>::operator() "
 "indices out of range"};
 return at(unchecked, indices);
 }
 /**
 * @}
 */
 };
 /**
 * Deduction guide.
 * Deduces <tt>Dimension<N></tt> for @c N arguments.
 */
 template <typename... Args>
 Dimension(Args...) -> Dimension<sizeof...(Args)>;
}
}
#endif

You can run Doxygen to generate the documentation. Here's a test, which is also an example of how Dimension can be used:

#include "dimension.hpp"
#include <type_traits>
using namespace LF_lib::multi;
int main()
{
 {
 constexpr Dimension<5> dim {1, 2, 3, 4, 5};
 static_assert(dim.order() == 5);
 static_assert(dim.size() == 120);
 static_assert(!dim.valid({1, 1, 1, 1, 1}));
 static_assert(dim.at({0, 1, 2, 3, 4}) == 119);
 static_assert(dim.at({0, 1, 2, 3, 4}) == dim.at(unchecked, {0, 1, 2, 3, 4}));
 // static_assert(dim.at({1, 1, 1, 1, 1}));
 static_assert(dim(0, 1, 2, 2, 4) == dim.at({0, 1, 2, 2, 4}));
 }
 {
 constexpr Dimension<0> dim = {};
 static_assert(dim.order() == 0);
 static_assert(dim.size() == 1);
 static_assert(dim.valid({}));
 static_assert(dim.at({}) == 0);
 static_assert(dim.at({}) == dim.at(unchecked, {}));
 static_assert(dim() == 0);
 }
 {
 static_assert(std::is_same_v<Dimension<5>, decltype(Dimension{1, 2, 3, 4, 5})>);
 // static_assert(std::is_same_v<Dimension<5>, decltype(Dimension(1, 2, 3, 4, 5))>);
 static_assert(std::is_same_v<Dimension<0>, decltype(Dimension{})>);
 static_assert(std::is_same_v<Dimension<0>, decltype(Dimension())>);
 }
}

• pacmaninbw: This may just be a style nit or a copy and past error, but I believe that the second namespace, starting with namespace multi { should be another level of indentation.
• Edward: On my machine with gcc 8.3.1, I get a compile error on the last line: error: cannot deduce template arguments for ‘Dimension’ from (). Which compiler are you using?
• Incomputable: @Edward, godbolt seems to be able to compile it. Perhaps there is a bug in gcc 8.3.1 with deduction guides? My intuition says that it should compile, but may be I am wrong, didn't thoroughly read standard.
• pacmaninbw: @Edward I can compile it in Visual Studio 2017 when using the C++17 standard.
• Edward: It also compiles cleanly with clang++ 7.0.1

Answer 1

Lovely clean readable code - nice. :-)

I don't agree with your bounds-checking philosophy (imposing either run-time overhead or syntactic clutter), but I'll respect your choice. I find it, um, interesting that although we have bounds checking, we still cheerfully allow our accessors at() and size() to overflow the range of std::size_t.

Review points, in no particular order:

• It's great that you provide a deduction guide; it seems a waste not to use that for at least one of the dim variables in the demo program!

• I get a compilation failure for the use of Dimension() default constructor:

  220508.cpp:204:71: error: cannot deduce template arguments for ‘Dimension’ from ()
   static_assert(std::is_same_v<Dimension<0>, decltype(Dimension())>);
  

  I think this is just a consequence of using struct initialisation, rather than declaring a constructor.

• It's slightly frustrating that only the () accepts unpacked arguments, and we need to write {..} to construct an index_t when using at() or valid().

• It's not necessary or particularly useful to mark a default constructor explicit - it can never be a conversion.

• L. F.: Great! Thank you! As to the second bullet, that's strange because I compiled it successfully. (demo)
• L. F.: Also, as to operator(): it is considered to be "convenience syntax" so I removed the { }. I used universal references because otherwise an object that is intended to be converted to size_t may be accidentally copied. For example, I may have an lvalue foo of non-copyable type Foo, and I want to make sure dim(foo) works. But it didn't really work out — I intended to use std::forward<Args>(args)... but seems I forgot it ...
• L. F.: I marked the default constructor explicit because I was imitating [allocator.tag] ... But good point anyway! :)
• Toby Speight: Actually, I think you were probably right to use the operator forwarding - a cast isn't a call, so shouldn't cause an unnecessary copy. I should withdraw that criticism!

Answer 2

Writing it down here so I don't forget it: there is a bug in the code about perfect forwarding. I wrote

template <typename... Args>
constexpr std::size_t operator()(Args&&... args) const
{
 // ...
 index_t indices{static_cast<std::size_t>(args)...};
 // ...
}

when it should be

template <typename... Args>
constexpr std::size_t operator()(Args&&... args) const
{
 // ...
 index_t indices{static_cast<std::size_t>(std::forward<Args>(args))...};
 // ...
}

Also, it is preferable to constrain the function with SFINAE instead of putting in static_asserts:

template <typename... Args, typename = std::enable_if_t<
 sizeof...(Args) == N &&
 std::conjunction_v<std::is_convertible<Args, std::size_t>...>
>>
constexpr std::size_t operator()(Args&&... args) const;