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())>);
  }
}

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.

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;