优化旋转std::index_sequence的类型特征，提升大N值场景下的多编译器兼容性

我最近碰到了一个类型特征实现的瓶颈：需要生成包含所有旋转版本std::index_sequence的type_pack——比如make_pack_of_rotating_index_sequences<3>最终要等价于type_pack<std::index_sequence<0,1,2>, std::index_sequence<1,2,0>, std::index_sequence<2,0,1>>。

但当N变大时（比如700+），不同编译器的表现差得离谱：Clang和ICX还能撑住，GCC和MSVC很早就编译失败或者超时了。我的目标是让GCC、Clang、ICX和MSVC这四个主流编译器都能轻松处理700+的旋转需求，而且在Compiler Explorer里不会超时。

最初的实现：递归继承逐个构建 #

最开始我用了递归继承的思路，逐个添加每个旋转后的index_sequence，代码如下：

#include <cstddef>
#include <utility>

template <class...> struct type_pack {}; // 实测用这个比tuple编译略快

namespace rot_detail {
template <class...> // 主模板，仅声明不实现
struct rot_help;

template <> // 空序列的入口与终止器
struct rot_help<std::index_sequence<>> {
    using type = type_pack<>;
};

// MSVC在N=1时需要单独处理，我尝试提交bug但没有权限...
template <std::size_t I0>
struct rot_help<std::index_sequence<I0>> {
    using type = type_pack<std::index_sequence<I0>>;
};

template <size_t I0, size_t... Is, class... Seqs> // 正常终止逻辑
struct rot_help<std::index_sequence<I0, Is...>, std::index_sequence<I0, Is...>, Seqs...> {
    using type = type_pack<Seqs...>;
};

template <size_t I0, size_t... Is> // 非空序列的入口
struct rot_help<std::index_sequence<I0, Is...>> 
    : rot_help<std::index_sequence<Is..., I0>, std::index_sequence<I0, Is...>, std::index_sequence<I0, Is...>> {};

template <size_t I0, size_t... Is, class End, class... Seqs> // 逐个构建旋转序列
struct rot_help<std::index_sequence<I0, Is...>, End, Seqs...> 
    : rot_help<std::index_sequence<Is..., I0>, End, Seqs..., std::index_sequence<I0, Is...>> {};
} // namespace rot_detail

template <size_t N>
using make_pack_of_rotating_index_sequences = typename rot_detail::rot_help<std::make_index_sequence<N>>::type;

这个实现的问题很明显：递归继承的深度和N成正比，N=700就需要700层递归，GCC和MSVC的模板递归处理能力本来就弱于Clang，自然很早就扛不住了。

尝试过的无效优化：批量生成两个旋转 #

我想着把递归深度砍半，试试一次生成两个旋转序列，但实际编译时间和支持的最大N值几乎没变化：

namespace rot_detail {
// 保留之前的rot_help特化...

template <class...> struct two;

template <size_t I0, size_t I1, size_t... Is, class End, class... Seqs>
struct two<std::index_sequence<I0, I1, Is...>, End, Seqs...> {
    using type = rot_help<std::index_sequence<Is..., I0, I1>, End, Seqs..., 
                          std::index_sequence<I0, I1, Is...>, 
                          std::index_sequence<I1, Is..., I0>>;
};

template <size_t I0, size_t... Is, class End, class... Seqs>
struct rot_help<std::index_sequence<I0, Is...>, End, Seqs...> 
    : std::conditional_t<
        std::same_as<std::index_sequence<Is..., I0>, End>,
        rot_help<End, End, Seqs..., std::index_sequence<I0, Is...>>,
        typename two<std::index_sequence<I0, Is...>, End, Seqs...>::type
    > {};
}

看来递归继承的思路本身就有瓶颈，得换个完全不同的实现方式。

优化方案：直接计算每个旋转序列，避免递归继承 #

核心思路是：每个旋转k对应的index_sequence，本质上就是(k+i)%N（i从0到N-1）的序列。我们可以直接生成每个旋转的序列，不需要依赖前一个旋转的结果，完全去掉递归继承。

优化后的代码如下：

#include <cstddef>
#include <utility>

template <class...> struct type_pack {};

namespace rot_detail {
// 生成单个旋转序列：第k个旋转（0 ≤ k < N）
template <std::size_t N, std::size_t K, std::size_t... Is>
constexpr auto make_single_rot_seq(std::index_sequence<Is...>) {
    return std::index_sequence<(K + Is) % N...>{};
}

template <std::size_t N, std::size_t K>
using single_rot_seq = decltype(make_single_rot_seq<N, K>(std::make_index_sequence<N>{}));

// 利用std::make_index_sequence生成所有旋转的k值，展开为type_pack
template <std::size_t N, std::size_t... Ks>
struct build_rot_pack {
    using type = type_pack<single_rot_seq<N, Ks>...>;
};

template <std::size_t N, class KSeq>
struct rot_pack_impl;

template <std::size_t N, std::size_t... Ks>
struct rot_pack_impl<N, std::index_sequence<Ks...>> {
    using type = typename build_rot_pack<N, Ks...>::type;
};
} // namespace rot_detail

template <std::size_t N>
using make_pack_of_rotating_index_sequences = 
    typename rot_detail::rot_pack_impl<N, std::make_index_sequence<N>>::type;

为什么这个方案更高效？ #

1. 完全消除递归继承：原方案的递归深度和N成正比，新方案利用std::make_index_sequence的展开能力，一次性生成所有需要的旋转序列，编译器不需要处理几百层的递归继承结构。
2. 每个序列独立计算：每个旋转序列的元素都是直接通过(K+Is)%N计算得到的，不需要依赖前一个序列的结果，减少了编译时的依赖链。
3. 天然支持所有N值：原方案里针对MSVC N=1的特殊处理也可以去掉了，这个方案对N=0、1、700的情况都能正确处理。

实测下来，这个方案在GCC、Clang、ICX和MSVC上都能轻松处理700+的N值，而且在Compiler Explorer里不会超时——终于实现了跨编译器的一致表现。

内容来源于stack exchange