Feedback wanted!
I’m always glad about feedback. If you spot an error in this post, let me know and I’ll fix it.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.
Article obsolete!
This article was written in a time before C++23. C++23 solves the problem described in this article with the wonderful
std::mdspan
class. I recommend using that instead of the solution described here.
Moreover, C++23 finally allows you to overload operator[]
with multiple parameters.
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 values1. 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:
Table::operator[]
is called. It returnsMultiDimensionalIndex
. Our utility class stores the parameter toTable::operator[]
(i.e. the row number). It also overloads the subscript operator itself.MultiDimensionalIndex::operator[]
is called with the column index. Our struct knows that it now has all values it needs and callsTable::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 likee[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 beint
andTs...
is{float, double}
. -
We now look at
take<2 - 1, typelist<int>, typelist<float, double>
.Here
N
is deduced to be1
.Us...
is{int}
.T
is deduced to befloat
andTs...
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 justtypelist<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
}:
Expression | Type | Values to store |
---|---|---|
foo[0] | MultiDimensionalIndex<Foo, 1, int, float, std::string> | (foo, 0) |
foo[0][2.f] | MultiDimensionalIndex<Foo, 2, int, float, std::string> | (foo, 0, 2.f) |
foo[0][2.f][“Bar”] | MultiDimensionalIndex<Foo, 3, int, float, std::string> | (foo, 0, 2.f, “Bar”) |
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!
Footnotes
-
C++23 solves this problem by allowing overloading the subscript operator with more than one parameter. ↩