在编译时自动生成用于稀疏数组索引的 switch 语句

Question

有没有办法生成编译时 switch 语句来匹配索引？例如，如果我有一个序列 1,5,8 并且我想将它与 0,1,2 匹配，编译器是否可以在编译时生成一个函数，当给定 1,5,8 returns 分别为 0、1、2。为了更好地说明我想要什么，我准备了这个稀疏数组结构：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>();
}

我还希望能够传入运行时变量，这些变量将通过索引和 return 相应的索引进行切换。我解决这个问题的唯一想法是生成一个 Is... 序列的数组，然后使用带有 if 语句的 for 循环来 return 正确的索引。另一种选择是使用地图（但这也不是编译时）。 sparse_array 通常会非常小，我希望能够在编译时完成大部分事情。

Answer 1

是这样的吗？

static constexpr size_t idx(size_t i)
{
    size_t j = 0;
    if(!(... || (j++, i == Is))) {
        throw "Index out of range!";
    }
    return j-1;
}

阅读起来可能有点棘手，但如果我理解正确的话，应该可以按照你的意愿去做。实例化后，这基本上等同于一系列 if else 从左到右通过 Is.

中的索引

您可以通过将折叠表达式的主体分隔为 lambda 来使其更具可读性。您还应该将 throw 表达式替换为您认为合适的任何内容。

使用 constexpr 限定符，这也可以用于模板版本：

template<size_t I, auto s = idx(I)>
static constexpr size_t idx() {
    return s;
}

（将结果放在模板默认参数中保证编译时评估。）

这不是性能最好的代码，与手动编写的 switch 语句存在相同的问题。根据输入的可预测性，许多分支可能经常被错误预测，在这种情况下，（大部分）无分支版本会更可取。这可以通过适当修改折叠表达式来实现。

如果索引的数量不小，对于指令缓存局部性，通过正确构造的静态数组的循环将更可取：

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;
}

同样，最好替换循环中的早期退出。

如果数组更大，不仅使用带循环的声明数组，而且正确地对该数组执行二进制搜索可能会很有用。

可以使用 std::any_of、std::find 和 std::binary_search 等标准算法来代替手动搜索实现。然而，这些算法将 constexpr 仅在 C++20 中，因此这将限制此处的使用。

在编译时自动生成用于稀疏数组索引的 switch 语句

Automatically generating switch statements at compile time for sparse array indexing

c++

templates

sparse-matrix

c++17

index-sequence