Automatically generating switch statements at compile time for sparse array indexing

Question

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.

Answer 1

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.