A utility class for multi-dimensional operator[]

Sometimes you have data-structures that are multi-dimensional in nature. A classic example might be a matrix or a cube. Alas, there’s no built-in way in the language to deal with multi dimensional array-like access. In this blog post we’re going to develop a little utility class that you can use for exactly that.

Problem Statement

In C++, the language provides the subscript operator operator[] that one can overload to allow array-like indexing into their own classes. In C++20 it’s not possible to overload the operator with multiple values¹. This can be a bit annoying because you always have to implement helper classes to be able to overload operator[]:

struct Table {
    //Not great since we probably don't want to implement the type Row,
    //since it's only used for overloading operator[] itself.
    [[nodiscard]]
    Row operator[](std::size_t index) const noexcept;

    //Only legal in C++ >= C++23
    [[nodiscard]]
    Cell operator[](std::size_t row, std::size_t col) const noexcept;
};

What if we could write a generic type MultiDimensionalIndex that acts as a proxy and overloads operator[] in a sensible way? One wouldn’t have to implement a helper class every time and could instead use this helper struct. Syntactically, it should look like this: table[2][4].

Our utility struct works like this:

1. Table::operator[] is called. It returns MultiDimensionalIndex. Our utility class stores the parameter to Table::operator[] (i.e. the row number). It also overloads the subscript operator itself.
2. MultiDimensionalIndex::operator[] is called with the column index. Our struct knows that it now has all values it needs and calls Table::get(row, col).

Solution

If this still is a bit too abstract, then let’s just dive into the code:

template<typename T, std::size_t Index, typename... Args>
requires (sizeof...(Args) >= 2 && sizeof...(Args) >= Index)
struct MultiDimensionalIndex {
    
    constexpr auto operator[]( /* type of Args[Index] */ index)
    -> MultiDimensionalIndex<T, Index + 1, Args...> {
        // TODO
    }
};

We create a new struct called MultiDimensionalIndex. It has three template parameters:

• T, the type of the class that we want to enable multi-dimensional indexing for.
• The parameter pack Args. It represents the types of indices in the order that they appear. That way we can support indexing with different types (e.g. allow expressions like e[2]["foo"][13.f]).
• Lastly Index points to the index of the parameter type that we want to get next.

The idea is that we return MultiDimensionalIndex with Index incremented by one until we reach sizeof...(Args) == Index - 1. Using concepts, we require that we have at least a 2D structure and that Index doesn’t grow too large.

The first puzzle piece we need to solve is how to get the type of the n-th parameter in Args. We can do this using std::tuple_element:

#include <tuple>

template <int N, typename... Ts>
using NthTypeOf = typename std::tuple_element<N, std::tuple<Ts...>>::type;

constexpr auto operator[](NthTypeOf<Index, Args...> index) {
    /* ... */
}

Fun with template meta-programming: typelist

When writing this article, I hit a roadblock here. I wanted to split Args after the n-th child. We’re going to see why this is useful in a second. I tried for two days, until I asked on StackOverflow. I’m really happy with the answers I got and ended up using the Boost.Mp11 solution. However, I found the answer I linked above way cooler and thus for the remainder of the blog post I’m going to go with that. Adapting it to Boost.Mp11 is left as an exercise to the reader.

The problem I ended up having was that variadic parameter packs in C++ aren’t first class citizens. We can make them citizens by creating a new type:

template <class... Ts> struct typelist;

Note that typelist is declared, but not defined. The reason is that we just use it for metaprogramming purposes.

Let’s now put our typelist to use and implement take. The operation take should just return a typelist with the first N arguments.

template <size_t N, class, class> struct take;

// (2)
template <class Take, class Drop>
struct take<0, Take, Drop>  {
    using type = Take;
};

// (1)
template <size_t N, class T, class... Ts, class... Us>
requires(N > 0)
struct take<N, typelist<Us...>, typelist<T, Ts...>> {
    using type = typename take<N - 1, typelist<Us..., T>, typelist<Ts...>>::type;
};

First, we declare take which takes an index N and two classes. The first class is used as a Take list. It essentially stores all types that we want to keep. The second class is used as a Drop list. In here we store all types that we still need to process. The idea in essence is now to shift types from the Drop to the Take list.

Let’s try this with take<2, typelist<>, typelist<int, float, double>>::type:

• We use the first template specialization. N is deduced to be 2. Us... is empty, T is deduced to be int and Ts... is {float, double}.

• We now look at take<2 - 1, typelist<int>, typelist<float, double>.

  Here N is deduced to be 1. Us... is {int}. T is deduced to be float and Ts... is deduced to be {double}.

• We now look at take<1 - 1, typelist<int, float>, typelist<double>>.

  Note how we now use the template specialization marked with (2) in the above code. Thus, our final type is just typelist<int, float>.

We can introduce a nice using declaration to make take a bit nicer:

template <size_t N, class... Ts>
using take_t = typename take<N, typelist<>, typelist<Ts...>>::type;

From now on we can now just write take_t<2, int, float, double> to get typelist<int, float>. Awesome!

Utility class: make_ctor

Another useful piece of code we’re going to need in a moment is make_ctor. It looks like this:

template <class Ts> 
struct make_ctor;

template <class... Ts>
struct make_ctor<typelist<Ts...>> {
    constexpr make_ctor(Ts... ts) : tuple(ts...) {}

    std::tuple<Ts...> tuple;
};

It uses typelist to define a std::tuple called tuple and a constexpr constructor that fills the tuple with values. It is meant to be used as a utility base class.

Putting everything together

For our class to work, we need to remember which values are already known. In other words: Depending on Index we need to save all values that came before Index.

Consider the example type Foo, that stores values in a 3d cube of {int × float × std::string}:

We use make_ctor to store the values that we already have. Note that we also store a const reference to T!

template <typename T, int Index = 0, typename... Args>
requires (sizeof...(Args) >= 2 && sizeof...(Args) >= Index)
struct MultiDimensionalSubscript : make_ctor<take_t<Index + 1, const T&, Args...>> {
    using make_ctor<take_t<Index + 1, const T&, Args...>>::make_ctor;

    // ...
};

Now we can start implementing operator[]. First, we check if Index is smaller than Args. Then we use std::make_from_tuple to call MultiDimensionalIndex’s constructor with the values stored in the member tuple and the index we just got. We use std::tuple_cat to append index to tuple.

constexpr auto operator[](NthTypeOf<Index, Args...> index) {
    if constexpr (Index == (sizeof...(Args)) - 1) {
        // ...
    } else {
        return std::make_from_tuple<
            MultiDimensionalSubscript<T, Index + 1, Args...>
        > (
            std::tuple_cat(
                make_ctor<take_t<Index + 1, const T&, Args...>>::tuple, 
                std::make_tuple(index)
            )
        );
    }
}

The last thing we need to do now is to implement the actual getting of the values. I opted for a free-floating function get that in turn calls some function in T. You might choose to do it differently, though.

if constexpr (Index == (sizeof...(Args)) - 1) {
    return std::apply(
        get,
        std::tuple_cat(
            make_ctor<take_t<Index + 1, const T&, Args...>>::tuple, 
            std::make_tuple(index)
        )
    );
} else { /* ... */}

Final Example: A Cube

Finally, I want to leave you with an example of the class in action:

struct Cube {
    constexpr MultiDimensionalSubscript<Cube, 1, int, int, float> operator[](int i) {
        return {*this, i};
    }

    float GetElement(int x, int y, int z) const;
};

constexpr auto get(const Matrix3d& c, int x, int y, float z) {
    return c.GetElement(x, y, z);
}

int main(int, char**) {
    Cube c;

    // Compiler optimizes this to c.GetElement(2, 19, 16)!
    std::cout << c[2][19][16];
}

I hope this proves to be useful for you. I’m not entirely happy with some parts of this implementation and I might revisit it in the future. See you then!