How to Store a Variable Number of Objects Known at Compile Time in C++
How to store a variable number of objects known at compile time?
This is a question that Fluent C++ reader John Koniarik sent in to me by email. Here was his exact problem, reproduced with his permission:
I would like to efficiently store n-dimensional simplexes. I have defined Simplex< unsigned n > as key data structure. (It has std::array< Point, n + 1> inside ). I need a storage that looks something like:
template< unsigned n >
class SimplexStorage
{
std::vector< Simplex< 1 > > vec1;
std::vector< Simplex< 2 > > vec2;
....
std::vector< Simplex< n > > vecn;
}
And on the top of storing the collections, John also needs to be able to access the k-th one:
template< size_t n >
class SimplexStorage
{
public:
template<int k>
std::vector<Simplex<k>>& getSimplexes()
{
// ????
It’s independent from the code itself, but a simplex in a space of dimension n is a polygon with n + 1 points. For example it would be a line segment in dimension 1, a triangle in dimension 2, a tetrahedron in dimension 3, and so on (with an “and so on” that requires to think in spaces of higher dimensions, but anyway).
How to store the various collections of simplexes of dimensions 1 to n in a structure? How do we access the k-th one, for k between 1 and n? And how to write all this in an expressive way?
What follows is a possible answer to those three questions. If you see how to improve it, or if you know a different answer altogether, we’re happy to read about it in the comments section at the bottom.
And a big thanks to John for asking that great question!
Storing some T<m>s
The question of storing the collections of simplexes comes down to representing a collection of objects parametrized by a number. And this number is known at compile-time.
Accessing the k-th element of a compile-time collection sounds a bit like accessing the k-th element of a std::tuple, by std::get<k>, doesn’t it?
So let’s use a tuple. We would like it to look like this:
template<size_t n>
std::tuple<std::vector<Simplex<1>>,
std::vector<Simplex<2>>,
std::vector<Simplex<3>>,
...
std::vector<Simplex<n>>>;
But the above syntax is not legal C++. Here is a more conventional C++ syntax:
template<size_t... ks> using SimplexStorage = std::tuple<std::vector<std::tuple<ks>>...>;
This tuple would expand to the one we want, if only we could instantiate it with the following syntax:
SimplexStorage<1, 2, 3, ... n>;
But now this is not a legal C++ syntax.
So we need to find a way generate a compile-time sequence of integers from 1 to n, and use them as parameters of SimplexStorage.
Generating a compile-time sequence of integers
C++14 brings a utility template called std::index_sequence, that holds a sequence of integers in its template parameters. And it can be constructed with numbers from 0 to n – 1 with std::make_index_sequence<n>.
To illustrate, consider the following two functions:
template<size_t... ks>
void f(std::index_sequence<ks...>)
{
}
template<size_t n>
void g()
{
f(std::make_index_sequence<n>{});
}
Calling g<5>, for instance, constructs a std::make_index_sequence<5>, which is an alias for std::index_sequence<0, 1, 2, 3, 4>. So in that case, the variadic pack of f, <size_t... ks>, would be <0, 1, 2, 3, 4>.
That looks interesting for us, because this is the sort of variadic pack we would like to instantiate our SimplexStorage with.
We can’t extract a variadic pack from a function though. One way to fit the pack into the SimplexStorage is to instantiate it right there:
template<size_t... ks>
SimplexStorage<ks...> f(std::index_sequence<ks...>)
{
return SimplexStorage<ks...>;
}
In fact, this creates a collections of simplex from dimension 0 to dimension n – 1, but dimension 0 doesn’t mean anything (or does it?) and we need collection from 1 to n. So let’s add 1 to each member of our variadic pack. And also rename f and g into something more explicit:
template<size_t... ks>
SimplexStorage<(1 + ks)...> make_storage(std::index_sequence<ks...>)
{
return SimplexStorage<(1 + ks)...>{};
}
template<size_t N>
auto make_storage()
{
return make_storage(std::make_index_sequence<N>{});
}
Now we have a function that creates a SimplexStorage of size n, with the right template parameters.
But it’s not a function itself we need, but rather its return type!
There is only one step to go there: decltype. We are going to create an alias that resolves to the decltype of calling make_storage with a template parameter n. This alias is really what we would like to call SimplexStorage, but this name is already taken.
So let’s rename our current SimplexStorage to SimplexStorageImpl, because it turns out to be merely an intermediary step:
template< size_t... ks >
using SimplexStorageImpl = std::tuple<std::vector<Simplex<ks>>...>;
template<size_t... ks>
static SimplexStorageImpl<(1 + ks)...> make_storage(std::index_sequence<ks...>)
{
return SimplexStorageImpl<(1 + ks)...>{};
}
template<size_t N>
static auto make_storage()
{
return make_storage(std::make_index_sequence<N>{});
}
and keep SimplexStorage for the final type:
using SimplexStorage = decltype(make_storage<n>());
Retrieving the simplexes of dimension m
We need a method getSimplexes to retrieve the collections of simplexes of dimension m. There are several ways to go about that. We could add a free function that takes a SimplexStorage and returns the right element of the tuple, or make SimplexStorage a class that contains the tuple and offers a getSimplexes method.
In order to encapsulate the storage representation, let’s go for the class. This leads to our final code:
template< size_t n >
class SimplexStorage
{
public:
template<int k>
std::vector<Simplex<k>> & getSimplexes()
{
return std::get<k-1>(storage_);
}
private:
template< size_t... ks >
using StorageImpl = std::tuple<std::vector<Simplex<ks>>...>;
template<size_t... ks>
static StorageImpl<(1 + ks)...> make_storage(std::index_sequence<ks...>)
{
return StorageImpl<(1 + ks)...>{};
}
template<size_t N>
static auto make_storage()
{
return make_storage(std::make_index_sequence<N>{});
}
using Storage = decltype(make_storage<n>());
Storage storage_;
};
If you find the private part too long, you could choose to get rid of one indirection, the overload of make_storage that takes no parameter:
template< size_t n >
class SimplexStorage
{
public:
template<int k>
std::vector<Simplex<k>> & getSimplexes()
{
return std::get<k-1>(storage_);
}
private:
template< size_t... ks >
using StorageImpl = std::tuple<std::vector<Simplex<ks>>...>;
template<size_t... ks>
static StorageImpl<(1 + ks)...> make_storage(std::index_sequence<ks...>)
{
return StorageImpl<(1 + ks)...>{};
}
using Storage = decltype(make_storage(std::make_index_sequence<n>{}));
Storage storage_;
};
But it makes the line with the using declaration a little harder to understand.
Here is all the code in a Coliru if you’d like to play around with it.
A big thanks to John for this great question. If you would also like me to look at your design problem, you can send it to me via email at jonathan@fluentcpp.com. And if you see how to improve the above design, please participate to the discussion in the comments section below!
You may also like
Don't want to miss out ? Follow:
Share this post!
