3
\$\begingroup\$

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())>);
  }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – pacmaninbw May 19 at 15:19
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Edward May 19 at 15:20
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Incomputable May 19 at 16:21
  • 1
    \$\begingroup\$ @Edward I can compile it in Visual Studio 2017 when using the C++17 standard. \$\endgroup\$ – pacmaninbw May 19 at 16:36
  • 1
    \$\begingroup\$ It also compiles cleanly with clang++ 7.0.1 \$\endgroup\$ – Edward May 19 at 16:40
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Great! Thank you! As to the second bullet, that's strange because I compiled it successfully. (demo) \$\endgroup\$ – L. F. Jun 24 at 11:20
  • \$\begingroup\$ 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 ... \$\endgroup\$ – L. F. Jun 24 at 11:24
  • \$\begingroup\$ I marked the default constructor explicit because I was imitating [allocator.tag] ... But good point anyway! :) \$\endgroup\$ – L. F. Jun 24 at 11:26
  • \$\begingroup\$ 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! \$\endgroup\$ – Toby Speight Jun 24 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.