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

Question

有没有一种方法可以生成编译时切换语句，用于匹配索引？例如，如果我有一个序列1,5,8，并且我想将其与0,1,2匹配，那么编译器是否可以在编译时生成一个函数，当给定1,5,8时，该函数分别返回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>();
}

我希望还能够传入运行时变量，这些变量将通过带有索引的开关并返回相应的索引。我解决这个问题的唯一想法是生成一个Is...序列的数组，然后用if语句进行for循环，以返回正确的索引。另一种选择是使用映射(但这也不是编译时(。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中的索引。

通过将fold表达式的主体分离为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之类的标准算法来代替手动搜索实现。然而，这些算法仅在C++20中为constexpr，因此这将限制此处的使用。