3
\$\begingroup\$

When creating little games or other programs I often need multidimensional arrays. Usually I just do the simple std::vector<std::vector<T>> thing for simplicity's sake. However, this runs way more allocations and the data is not stored in one contiguous location, which brings some drawbacks with it. To fix this I wanted to create a multidimensional array view, with which I can just have something along the following lines (with an example of an array transformed to a 3x3 matrix):

std::vector<int> vec{ /* ... */ };
MDSpan<int, 3, 3> view{ vec.data() };
view[1][2] = 123;

My first approach was only templated on the datatype, but not the dimensions. This allowed for dynamic resizing and reshaping of the view, but it didn't allow for the multiple subscript operators returning different types, either new views, or values if the span is one-dimensional.

After that I restructured my code to be templated on the dimensions as well, which got rid of the previously mentioned subscript problem and additionally got compile time constant evaluation possibilities.

#pragma once

#include <concepts>
#include <utility>
#include <array>

template <template<typename, auto...> typename U, typename V, auto first, auto... others>
struct DropFirstPackValue {
    using type = U<V, others...>;
};
template <template<typename, auto...> typename U, typename V, auto first, auto... others>
using DropFirstPackValue_t = DropFirstPackValue<U, V, first, others...>::type;

template <typename T, std::size_t... strides>
    requires (sizeof...(strides) > 0)
class MDSpan {
public:
    constexpr MDSpan() = default;
    constexpr MDSpan(T* begin) {
        reset(begin);
    }
    
    constexpr void reset(T* begin) {
        m_begin = begin;
    }
    
    constexpr const T& at(std::integral auto... indices) const requires(sizeof...(strides) == sizeof...(indices)) {
        const std::array arr{ indices... };
        std::size_t offset{};
        for (std::size_t i{}, size{ arr.size() }; i < size; ++i) {
            offset += getStridesProduct(size - 1 - i) * arr[i];
        }

        return *(m_begin + offset);
    }
    constexpr T& at(std::integral auto... indices) requires(sizeof...(strides) == sizeof...(indices)) {
        return const_cast<T&>(std::as_const(*this).at(indices...));
    }
    constexpr const T& operator[](std::size_t index) const requires(sizeof...(strides) == 1) {
        return at(index);
    }
    constexpr T& operator[](std::size_t index) requires(sizeof...(strides) == 1) {
        return at(index);
    }
    
    constexpr auto operator[](std::size_t index) requires(sizeof...(strides) > 1) {
        const std::size_t offset{ getStridesProduct(dimensions()) };
        T* begin{ m_begin + index * offset };
        return DropFirstPackValue_t<MDSpan, T, strides...>{ begin };
    }

    constexpr T* data() {
        return m_begin;
    }
    constexpr auto begin() {
        return Iterator{ *this };
    }
    constexpr auto end() {
        return Iterator{ *this, stride(0) };
    }

    constexpr static std::size_t dimensions() {
        return m_strides.size();
    }
    constexpr static std::size_t stride(std::size_t index) {
        return m_strides[index];
    }

    constexpr bool empty() const {
        return !m_begin;
    }
    constexpr operator bool() const {
        return !empty();
    }

    constexpr bool operator==(const MDSpan& other) const {
        return m_begin == other.m_begin;
    }
    constexpr bool operator!=(const MDSpan& other) const {
        return !(*this == other);
    }

private:
    constexpr static std::size_t getStridesProduct(std::size_t index) {
        std::size_t product{ 1 };
        for (std::size_t i{}; i + 1 < index; ++i) {
            product *= stride(dimensions() - 1 - i);
        }
        return product;
    }

private:
    T* m_begin;
    inline constexpr static std::array m_strides{ strides... };

private:
    class Iterator {
    public:
        constexpr Iterator operator++(int) {
            return Iterator{ m_owner, m_index++ };
        }
        constexpr Iterator operator++() {
            ++m_index;
            return *this;
        }
        constexpr Iterator operator--(int) {
            return Iterator{ m_owner, m_index-- };
        }
        constexpr Iterator operator--() {
            --m_index;
            return *this;
        }

        constexpr auto operator*() {
            return m_owner[m_index];
        }

        constexpr bool operator==(const Iterator& other) const {
            return m_owner == other.m_owner && m_index == other.m_index;
        }
        constexpr bool operator!=(const Iterator& other) const {
            return !(*this == other);
        }

    private:
        constexpr Iterator(MDSpan& owner, std::size_t index = 0)
            : m_owner{ owner }, m_index{ index } {
        }
        friend class MDSpan;

    private:
        MDSpan& m_owner;
        std::size_t m_index;
    };
};

I would appreciate any kind of review and criticism, but have some specific questions, too:

  1. MDSpan::operator[] returning a sub-view could be marked as const, since it does not modify this in any way. However it still grants access to the underlying data. The same applies for MDSpan::data(), MDSpan::begin() and MDSpan::end(). Therefore it should not be const in my opinion. Is this the right decision?

  2. In the non-const version of MDSpan::at() I use the const one with a const_cast. Since I am just dropping the previously applied const qualifier, this should be well defined, but is it good practice to do so?

  3. MDSpan::Iterator::operator*() and MDSpan::operator[] return new MDSpan objects, and not references. Is there a way to work around this? While those MDSpans are lightweight and you can still achieve the same as with references, since those are views, there might still be some confusion as in e.g. range based for loops not being able to use references.

  4. In my first approach, the dynamic one, I was checking for indexing out of bounds via assert() from <cassert>, however, since my static one should be able to be used as constexpr, I can't do this anymore so I dropped all checks, which makes it more lightweight as well. Should I still keep the checks, or maybe switch to exceptions instead and just use the preprocessor to enable/disable error checking for debug/release builds? And if I use bounds checking, should I disallow access with greater/equal indices to one of the strides or only disallow indexing which would access not owned memory?

(I know about C++23's std::mdspan, but wanted to implement my own multidimensional view. This is just for private projects and might even not get used at all.)
\$\endgroup\$
4
  • \$\begingroup\$ Welcome to Code Review! Incorporating advice from an answer into the question violates the question-and-answer nature of this site. You could post improved code as a new question, as an answer, or as a link to an external site - as described in I improved my code based on the reviews. What next?. I have rolled back the edit, so the answers make sense again. \$\endgroup\$ Commented Feb 2 at 18:02
  • \$\begingroup\$ @TobySpeight I am sorry if I somehow invalidated your answer, but I am pretty sure that I edited my question before you posted your answer, which should be ok, since the tour only states, that you should not edit a question after an answer has been posted. \$\endgroup\$
    – Joel
    Commented Feb 2 at 18:09
  • \$\begingroup\$ It does appear that the detector scored a false-positive here. It looks like your edit was while I was still writing the answer. Not sure what to do here, since the changes actually invalidate one of your specific questions that I answered! \$\endgroup\$ Commented Feb 2 at 18:13
  • \$\begingroup\$ I've asked in the 2nd Monitor for advice. \$\endgroup\$ Commented Feb 2 at 18:16

1 Answer 1

2
\$\begingroup\$

Overall impression: well-written and well presented. It's pretty clear what's going on. I would have liked to have seen the unit tests, too - that generally helps reviewers.


The constructor default-initialises m_begin, then assigns. It's better to use a real initialiser:

    constexpr MDSpan(T* begin)
        m_begin{begin}
    {
    }

*(m_begin + offset) is more conventionally written m_begin[offset].


We could really use a constructor for creating a MDSpan<const T> from MDSpan<T> where T is non-const.


To make Iterator fully functional, it needs a public default constructor and the crucial members for its traits to work:

    public:
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::bidirectional_iterator_tag;

It shouldn't be too hard to make it satisfy the requirements for a random access iterator, which can improve its utility with standard algorithms.


The span class lacks cbegin()/cend(). I mention that because iterator should convert to const_iterator but not vice versa, which can be slightly tricky if we template the iterator to avoid writing it out twice.

Reverse iterator functions would also be good to have, and trivially implemented using std::make_reverse_iterator().


Answering the specific questions:

  1. I agree that the subview [] operator mustn't be const if it allows read-write access to elements. However, we could provide a const version that provides a subview of const T elements. Use concepts to avoid collision when T is already const.

  2. That's safe, but when you move to C++23, be aware of deducing this, which is the modern way to write a single member function for both const and mutable objects.

  3. We could overload the operators for different number of dimensions, using constraints.

  4. As a user, I wouldn't expect to pay the cost of bounds checking unless I specifically ask for it. That's the main difference between at() and [] in standard collections, for example.

    I would throw std::out_of_range from the at() member when attempting to access outside the bounds of the span (regardless of whether that's within the underlying object, it's clearly erroneous - std::string_view is a good model to imitate for this).

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for your review! I will definitely look into your suggestions. I haven't ever bothered with iterators up to now and this is the first one I have written, so thank you for your recommendations. To be honest I am self thought and never learned how to do unit tests. I just had a container and tested each method after implementing it in main() and removed the code afterwards again. Would you suggest any testing framework or resource to get started with it? \$\endgroup\$
    – Joel
    Commented Feb 3 at 20:38
  • \$\begingroup\$ There are several frameworks - I've worked with Google Test and Qt's QTest frameworks; I've seen Catch2; there are probably others. You don't need a framework, but any of these libraries will provide utilities to make writing tests easier. Search around Test-driven development for a test-first way of thinking - I find that helpful for tasks of this kind. \$\endgroup\$ Commented Feb 3 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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