Is there a way to generate compile-time switch statements, for matching indices? For example if I have a sequence 1,5,8 and I want to match it to 0,1,2, is there a way the compiler can generate a function at compile time, which when given 1,5,8 returns respectively 0,1,2. To better illustrate what I want, I have prepared this sparse array structure: https://godbolt.org/z/QpWVST
#include <tuple>
#include <limits>
template<size_t depth, size_t Idx, size_t I, size_t...Is>
size_t get_idx()
{
static_assert(Idx==I || sizeof...(Is)>0, "Index not found.");
if constexpr(Idx==I) return depth;
else return get_idx<depth+1, Idx,Is...>();
}
template<typename T, size_t... Is>
struct sparse_array
{
constexpr static size_t N = sizeof...(Is);
constexpr static size_t size() { return N; }
T e[N];
constexpr sparse_array() : e{} {}
template<typename...type_pack>
constexpr sparse_array(const type_pack&... pack) : e{ pack... }
{
static_assert(sizeof...(type_pack) == size(), "Argument count must mach array size.");
}
template<size_t I>
constexpr size_t idx()
{
return get_idx<0, I, Is...>();
}
size_t idx(const size_t i)
{
// how to achieve somethig like this?
return idx<i>();
}
constexpr T& at(size_t idx)
{
return e[idx];
}
};
template<typename T, size_t...Is>
auto make_dense_array(std::index_sequence<Is...>&& seq)
{
return sparse_array<T, Is...>{};
}
template<typename T, size_t N>
using dense_array = decltype(make_dense_array<T>(std::declval<std::make_index_sequence<N>>()));
size_t test()
{
dense_array<int, 3> a;
sparse_array<int,1,5,8> b;
return b.idx<8>();
}
I want to be able to also pass in runtime variables, which would go through a switch with the indices and return the appropriate corresponding index. The only idea I have for solving this, involves generating an array of the Is... sequence, and then having a for loop with if statements in order to return the correct index. The other option being, using a map (but this is also not compile-time). The sparse_array would in general be very small, and I would have liked to be able to do most things compile time.
Something like this?
static constexpr size_t idx(size_t i)
{
size_t j = 0;
if(!(... || (j++, i == Is))) {
throw "Index out of range!";
}
return j-1;
}
It might be a bit tricky to read, but should do what you want, if I understood correctly. After instantiation this is basically equivalent to a series of if else going left-to-right through the indices in Is.
You can make it more readable by separating the body of the fold expression into a lambda. You should also replace the throw expression with whatever is sensible for you.
With the constexpr qualifier this can be reused for the template version as well:
template<size_t I, auto s = idx(I)>
static constexpr size_t idx() {
return s;
}
(Putting the result in the template default argument guarantees compile time evaluation.)
This will not be the most well-performing code, sharing the same problems a manually written switch statement has. Depending on the predictability of the inputs, the many branches may be often mispredicted, in which case a (mostly) branchless version would be preferable. This can be achieved by modifying the fold expression appropriately.
If the number of indices is not small, a loop through a properly constructed static array would be preferable for instruction cache locality:
static constexpr size_t idx(size_t i)
{
static constexpr std::array ind{Is...};
size_t j = 0;
for(; j < ind.size() && i != ind[j]; j++);
if(j == ind.size())
throw "Index out of range!";
return j;
}
Again, it might be preferable to replace the early exit in the loop.
If the array is even larger, it might be useful to not only use a declared array with loop, but implement binary search on that array properly.
Standard algorithms like std::any_of, std::find and std::binary_search could be used instead of the manual search implementations. However these algorithms will be constexpr only in C++20 and so this would limit the use here.