C++模板元编程实现选择排序

前言

模板元编程（template metaprogramming, TMP）是在编译期用类型和常量完成计算的技术。它的"变量"是类型与static constexpr值，"函数"是类模板特化，"循环"是递归实例化，"条件分支"是偏特化或if constexpr。用 TMP 实现选择排序，是一个能同时练到类型列表、元函数、递归终止和编译期断言的综合题目。

先说明两点预期。第一，TMP 版选择排序不会产生任何运行期排序代码，它产出的是一个新类型：元素按升序排列的类型列表。要把它变成运行期数据，还需要额外展开。第二，编译期计算有成本：每层递归都会实例化新模板，n个元素的选择排序大约需要 O(n²) 次实例化，递归深度为 O(n)。编译器对模板递归深度有默认上限（数百到一千量级，可用编译选项调整），元素过多会直接报"template instantiation depth exceeded"。

本文以 C++17 为基准，先搭类型列表和基础元函数，再实现min_index、remove_at和递归排序，最后给出 C++17constexpr函数的等价写法并比较两者适用场景。所有代码按标准语义推演，未经编译运行。

一、类型列表与编译期常量

TMP 里表示"一组类型"的常见载体是类型列表：

// 适用于 C++17
#include <cstddef>
#include <type_traits>

template <typename... Ts>
struct type_list {};

type_list没有任何成员，它只承载类型信息。编译期整数用std::integral_constant表示，std::integral_constant<int, 5>::value是常量 5，::type是它自己。为了少写几个字，可以起一个别名：

// 适用于 C++17
template <int V>
using ic = std::integral_constant<int, V>;

这样ic<5>就是一个"值为 5 的类型"。排序的对象就是type_list<ic<5>, ic<2>, ...>。

元函数通常写成类模板，用嵌套的type输出结果类型，用static constexpr成员输出值。调用时写typename foo<...>::type，其中的typename不能省——编译器默认不知道依赖模板参数的::type是类型还是静态成员，typename是在消除这个歧义。

二、四个基础元函数

求长度：用sizeof...直接数参数包。

// 适用于 C++17
template <typename List>
struct list_size;

template <typename... Ts>
struct list_size<type_list<Ts...>>
: std::integral_constant<std::size_t, sizeof...(Ts)> {};

按下标取类型：递归剥掉前面的元素。主模板只声明，两个偏特化分别处理"下标为 0"和"下标大于 0"。

// 适用于 C++17
template <std::size_t I, typename List>
struct list_at;

template <typename T, typename... Ts>
struct list_at<0, type_list<T, Ts...>> {
using type = T;
};

template <std::size_t I, typename T, typename... Ts>
struct list_at<I, type_list<T, Ts...>>
: list_at<I - 1, type_list<Ts...>> {};

拼接：把两个列表的包合并到一个新的type_list里。

// 适用于 C++17
template <typename A, typename B>
struct list_concat;

template <typename... As, typename... Bs>
struct list_concat<type_list<As...>, type_list<Bs...>> {
using type = type_list<As..., Bs...>;
};

删除指定下标：用一个累加器保存已扫描过的前缀，递归到目标位置时把该元素丢掉，再与剩余部分拼接。

// 适用于 C++17
template <std::size_t I, typename Acc, typename Rest>
struct remove_at_impl;

template <typename Acc, typename T, typename... Ts>
struct remove_at_impl<0, Acc, type_list<T, Ts...>> {
using type = typename list_concat<Acc, type_list<Ts...>>::type;
};

template <std::size_t I, typename Acc, typename T, typename... Ts>
struct remove_at_impl<I, Acc, type_list<T, Ts...>>
: remove_at_impl<I - 1,
typename list_concat<Acc, type_list<T>>::type,
type_list<Ts...>> {};

template <std::size_t I, typename List>
struct remove_at {
using type = typename remove_at_impl<I, type_list<>, List>::type;
};

remove_at_impl的第二个模板参数是"已经处理过的前缀"。每递归一层，前缀多一个元素，待处理列表少一个元素，I减一。当I归零时，当前列表的首元素就是要删除的那个，把前缀与Ts...拼接即可。

三、选择排序的递归实现

选择排序的步骤是：在剩余元素中找到最小值的下标，把它放到结果开头，对剩余部分递归。编译期版本需要两个比较器相关的元函数：less和min_index。

// 适用于 C++17
template <typename A, typename B>
struct value_less
: std::bool_constant<(A::value < B::value)> {};

template <typename List, std::size_t I, std::size_t Best,
template <typename, typename> class Less,
bool Done = (I >= list_size<List>::value)>
struct min_index_impl;

template <typename List, std::size_t I, std::size_t Best,
template <typename, typename> class Less>
struct min_index_impl<List, I, Best, Less, true> {
static constexpr std::size_t value = Best;
};

template <typename List, std::size_t I, std::size_t Best,
template <typename, typename> class Less>
struct min_index_impl<List, I, Best, Less, false> {
using current = typename list_at<I, List>::type;
using best = typename list_at<Best, List>::type;
static constexpr std::size_t next =
Less<current, best>::value ? I : Best;
static constexpr std::size_t value =
min_index_impl<List, I + 1, next, Less,
(I + 1 >= list_size<List>::value)>::value;
};

template <typename List, template <typename, typename> class Less>
struct min_index {
static constexpr std::size_t value =
min_index_impl<List, 1, 0, Less,
(list_size<List>::value <= 1)>::value;
};

这里用了一个bool Done参数作为递归终止开关。当I达到列表长度时，Done为真，命中第一个偏特化返回当前最优下标；否则命中第二个，比较current与best后继续。把终止条件做成模板参数的默认值，可以避免为"空列表"和"非空列表"分别写一套接口。

有了min_index，排序本身只有几行：

// 适用于 C++17
template <typename List, template <typename, typename> class Less,
bool Done = (list_size<List>::value <= 1)>
struct selection_sort_impl;

template <typename List, template <typename, typename> class Less>
struct selection_sort_impl<List, Less, true> {
using type = List; // 零个或一个元素，天然有序
};

template <typename List, template <typename, typename> class Less>
struct selection_sort_impl<List, Less, false> {
static constexpr std::size_t min_i = min_index<List, Less>::value;
using head = typename list_at<min_i, List>::type;
using rest = typename remove_at<min_i, List>::type;
using type = typename list_concat<
type_list<head>,
typename selection_sort_impl<rest, Less>::type>::type;
};

template <typename List, template <typename, typename> class Less>
using selection_sort_t = typename selection_sort_impl<List, Less>::type;

selection_sort_impl的第三个参数默认按列表长度计算，所以递归调用selection_sort_impl<rest, Less>时不必手动传终止标志。

最后的静态断言把结果"钉"在类型上：

// 适用于 C++17
using input = type_list<ic<5>, ic<2>, ic<9>, ic<1>, ic<5>, ic<3>>;
using sorted = selection_sort_t<input, value_less>;

static_assert(std::is_same_v<
sorted,
type_list<ic<1>, ic<2>, ic<3>, ic<5>, ic<5>, ic<9>>>, "sort failed");

static_assert在编译期检查类型是否完全一致。若排序逻辑写错，编译就会失败，而不是等到运行。

四、C++17 的 constexpr 替代方案

如果排序的只是整数，而不是"类型"，没有必要动用 TMP。C++14 起constexpr函数支持循环和局部变量，C++17 起std::array的非 const 下标也可在常量表达式中使用，因此可以直接写普通的循环版选择排序：

// 适用于 C++17
#include <array>
#include <cstddef>

template <std::size_t N>
constexpr std::array<int, N> sort_values(std::array<int, N> a) {
for (std::size_t i = 0; i + 1 < N; ++i) {
std::size_t m = i;
for (std::size_t j = i + 1; j < N; ++j) {
if (a[j] < a[m]) {
m = j;
}
}
int tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
return a;
}

constexpr auto result = sort_values(std::array<int, 5>{5, 2, 9, 1, 3});
static_assert(result[0] == 1 && result[4] == 9, "sort failed");

这段代码更短、更易读，编译期开销通常也更小。它和 TMP 版的区别在于能处理的对象：constexpr函数处理的是值，结果是一个常量数组；TMP 处理的是类型，结果是一个类型列表，可以继续参与类型计算（例如按类型选择重载、生成结构体字段）。选哪种取决于你要的是值还是类型。

代价与适用边界

TMP 的编译期计算不是"零成本"的。每个递归层都会产生新的模板实例，编译器要为它们做名字查找、替换和记录；n个元素的选择排序需要约 n²/2 次min_index内部的list_at求值，而每次list_at本身又是 O(n) 的递归。整体实例化数量随 n 增长很快。

递归深度同样需要注意。min_index_impl和selection_sort_impl都是线性递归，深度与元素个数同阶。超过编译器的默认上限会报错，可以通过命令行选项调整，但把上限调得很大往往意味着编译时间不可接受。

因此 TMP 适合元素数量小、且确实需要类型级结果的场景，例如固定字段的序列化描述、编译期注册表、维度检查。纯粹为了排序整数而用 TMP，属于技术练习，工程上应优先选constexpr函数或运行期std::sort。

常见坑点

1. 
   
2. ❌ 用运行期循环的思路写元函数，想在一个模板里"遍历"参数包。✅ 元函数靠递归实例化与偏特化推进，每层处理一个元素。
3. 
   

1. 
   
2. ❌ 在依赖名typename X<T>::type前漏写typename。✅ 编译器默认按值解释，必须显式标注这是类型。
3. 
   

1. 
   
2. ❌ 对空列表调用list_at<0, List>。✅ 先判断list_size，或在排序入口处理零/一个元素的终止情况。
3. 
   

1. 
   
2. ❌ 给函数模板写偏特化来实现分支。✅ 函数模板不支持偏特化；把逻辑放进类模板，或改用if constexpr。
3. 
   

1. 
   
2. ❌ 递归元函数只写递推分支，没有终止特化。✅ 必须有一个Done == true或空包的特化兜底，否则实例化无法停止。
3. 
   

1. 
   
2. ❌ 认为static_assert通过就意味着生成了运行期排序代码。✅ 编译期只完成类型计算，运行期没有任何排序动作；需要数据时还得自己展开。
3. 
   

1. 
   
2. ❌ 比较器在相等时返回true，破坏严格弱序。✅ 编译期less也必须是严格弱序，相等必须返回false，否则排序逻辑不成立。
3. 
   

1. 
   
2. ❌ 对几十个元素强行用 TMP 排序，编译时间失控。✅ 控制在少量元素，或改用constexpr函数、运行期算法。
3. 
   

总结

TMP 版选择排序的价值在于把"递归、特化、类型计算"这套机制完整走一遍：类型列表是数据结构，偏特化是分支，递归实例化是循环，static_assert是测试。真正写工程代码时，能用constexpr就用constexpr，只有在结果必须是类型时才请出模板元编程。