C++实践排序函数模板项目的参考方法

前言

「排序函数模板」听起来像课堂练习：写一个template<class T> void sort(T* data, int n)，里面套两层循环。真正放进项目后，问题会变成另一副样子：数据可能来自std::vector、std::array、原生数组甚至自定义容器；比较规则可能是「按分数降序、分数相同按学号升序」；调用方可能传std::list，而std::list不支持随机访问，套用std::sort直接编译失败；模板定义放在.cpp里还会链接失败。

常见的误解有两个。第一，把「泛型」理解成「把类型换成T就完事」，忽略了算法对迭代器类别和比较器语义的约束。第二，认为std::sort一定稳定，或者认为比较器返回true就是「相等」。前者是事实错误——std::sort不保证稳定，需要稳定用std::stable_sort；后者是逻辑错误——比较器必须满足严格弱序（strict weak ordering），写<=会破坏它，属于未定义行为。

本文按「模板形态、约束、项目组织、完整示例」来讲，重点放在如何把排序封装成一个可复用、可测试的组件，而不是重复实现快速排序。代码基准为 C++17，涉及 C++20 的约束写法会单独标注。

一、函数模板的基本形态

最简单的泛型排序封装接受一对迭代器和一个比较器：

// 适用于 C++17
#include <algorithm>
#include <functional>
#include <iterator>
#include <type_traits>

template <class RandomIt, class Compare = std::less<>>
void sort_range(RandomIt first, RandomIt last, Compare comp = Compare{}) {
using category = typename std::iterator_traits<RandomIt>::iterator_category;
static_assert(std::is_base_of<std::random_access_iterator_tag, category>::value,
"sort_range requires random access iterators");
std::sort(first, last, comp);
}

这里有三处设计决定。第一，参数用迭代器对而不是容器，这样原生数组、std::vector、std::deque、std::array都能用同一份代码。第二，比较器默认值是std::less<>，它是透明比较器（transparent comparator），operator()是模板，能按实参类型推导，不需要先统一成某个具体类型。第三，static_assert把「迭代器类别不对」的错误提前到编译期，并给出一句人类可读的提示，而不是让std::sort内部展开出一屏模板错误。

std::iterator_traits在 C++17 中仍是获取迭代器属性的标准方式；C++20 引入了std::iter_value_t、std::iter_reference_t等别名模板，以及std::random_access_iterator概念，写法会更直接。C++20 的版本可以写成：

// 需要 C++20
#include <algorithm>
#include <concepts>
#include <functional>
#include <iterator>

template <std::random_access_iterator RandomIt, class Compare = std::less<>>
requires std::sortable<RandomIt, Compare>
void sort_range20(RandomIt first, RandomIt last, Compare comp = Compare{}) {
std::sort(first, last, comp);
}

std::sortable是<iterator>中定义的概念（C++20），它同时约束迭代器可解引用、可交换，且比较器能作用于元素。各编译器对 concepts 的支持从 C++20 发布前后陆续完善，使用前应查自己工具链的支持表。

二、约束：迭代器类别与比较器语义

迭代器类别决定能用哪个算法

标准库的排序算法对迭代器有明确要求：

std::list和std::forward_list没有随机访问迭代器，不能传给std::sort，但它们各自提供了成员sort()，内部通常用归并排序，且是稳定的。这是「容器提供专用算法」的典型例子：链表排序用归并可以在 O(1) 额外空间下完成节点重排，而快速排序依赖随机访问。

因此，一个「通用排序入口」如果只接受随机访问迭代器，就必须在文档里写清楚；如果想同时支持链表，应当在重载里检测容器类型，或者干脆要求调用方自己选择算法。试图用std::advance模拟随机访问会把 O(N log N) 退化成 O(N²)，不要这么做。

比较器必须是严格弱序

比较器comp(a, b)的语义是「a 是否严格排在 b 前面」。严格弱序要求：

• 
  
• 不可自反：comp(a, a)必须为false；
• 
  
• 非对称：若comp(a, b)为真，则comp(b, a)必须为假；
• 
  
• 传递：若comp(a, b)与comp(b, c)为真，则comp(a, c)为真；
• 
  
• 等价关系传递：若a与b互不构成「小于」，b与c也互不构成「小于」，则a与c也必须互不构成「小于」。
• 
  

写return a <= b;违反第一条：comp(a, a)返回true。这会让std::sort的内部循环越过边界，属于未定义行为，症状可能是崩溃、死循环，也可能看起来正常。正确写法是return a < b;。多字段排序时，用「先比主键，相等再比次键」的短路写法：

// 适用于 C++17
struct Student {
int score;
int id;
};

struct ByScoreThenId {
bool operator()(const Student& lhs, const Student& rhs) const {
if (lhs.score != rhs.score) {
return lhs.score > rhs.score; // 分数降序
}
return lhs.id < rhs.id; // 学号升序
}
};

注意降序只改主键的比较方向，次键仍保持升序。若两处都写反，整体顺序会和预期相反。C++20 可以用operator<=>配合std::tie简化，但三路比较的返回类型和类别要写对，不确定时手写if更稳妥。

浮点与 NaN

比较器里涉及double时，NaN 会破坏严格弱序：NaN < x与x < NaN都为假，NaN与任何值「等价」，等价关系不再传递。若数据可能含 NaN，应先过滤或定义明确的排序规则，不要把 NaN 直接丢给std::sort。

三、项目组织：头文件、实现与测试

模板代码的项目结构通常如下：

sort_project/
include/
sort_utils.hpp
tests/
test_sort.cpp
CMakeLists.txt

因为模板定义必须对实例化点可见，sort_utils.hpp里直接写完整定义。测试文件包含它并调用具体类型。CMakeLists.txt只需要把include加入头文件搜索路径、把测试源文件编成可执行文件：

cmake_minimum_required(VERSION 3.16)
project(sort_project LANGUAGES CXX)

add_library(sort_utils INTERFACE)
target_include_directories(sort_utils INTERFACE ${CMAKE_CURRENT_SOURCE_DIR}/include)
target_compile_features(sort_utils INTERFACE cxx_std_17)

add_executable(test_sort tests/test_sort.cpp)
target_link_libraries(test_sort PRIVATE sort_utils)

INTERFACE库适合纯头文件的模板组件：它不产出目标文件，只把包含路径和编译特性传递给使用方。这样测试和将来的正式程序共享同一份配置，不会出现「测试能编、主程序编不过」的情况。

测试不依赖第三方框架也能做：用assert或自定义的检查宏，覆盖空区间、单元素、全部相等、已排序、逆序、含重复键这几种输入。模板代码尤其要测「不同类型」：int、std::string、自定义结构体各来一组，才能确认比较器和迭代器约束没有被写死。

性能方面不要凭感觉下结论。需要比较两种实现时，用std::chrono::steady_clock取时间戳，重复多次取中位数，并说明输入规模、数据分布、编译选项和机器环境。std::sort的比较次数是 O(N log N)，但常数受数据分布影响；已排序输入对某些实现反而更慢，因为枢轴选择策略不同。这些都是「应当自己测量」的问题，本文不给任何具体倍数。

四、完整示例：带检查的排序封装

下面把前面的要点合成一个可直接放进项目的头文件。它提供三个入口：迭代器版本、容器版本、稳定排序版本，并在编译期拒绝非随机访问迭代器。

// 适用于 C++17
#ifndef SORT_UTILS_HPP
#define SORT_UTILS_HPP

#include <algorithm>
#include <functional>
#include <iterator>
#include <type_traits>
#include <utility>

namespace sort_utils {

template <class Iter>
using category_t = typename std::iterator_traits<Iter>::iterator_category;

template <class Iter>
constexpr bool is_random_access_v =
std::is_base_of<std::random_access_iterator_tag, category_t<Iter>>::value;

template <class RandomIt, class Compare = std::less<>>
void sort_range(RandomIt first, RandomIt last, Compare comp = Compare{}) {
static_assert(is_random_access_v<RandomIt>,
"sort_range requires random access iterators; "
"use the container's own sort() for std::list");
std::sort(first, last, comp);
}

template <class RandomIt, class Compare = std::less<>>
void stable_sort_range(RandomIt first, RandomIt last, Compare comp = Compare{}) {
static_assert(is_random_access_v<RandomIt>,
"stable_sort_range requires random access iterators");
std::stable_sort(first, last, comp);
}

template <class Container, class Compare = std::less<>>
void sort_container(Container& container, Compare comp = Compare{}) {
using std::begin;
using std::end;
sort_range(begin(container), end(container), comp);
}

} // namespace sort_utils

#endif

sort_container里用了using std::begin; using std::end;再以无限定方式调用，这是让 ADL 找到自定义容器begin/end的标准手法。对原生数组，std::begin/std::end也有重载，所以int a[10]; sort_container(a);同样可用。

测试文件可以这样写：

// 适用于 C++17
#include "sort_utils.hpp"

#include <cassert>
#include <string>
#include <vector>

int main() {
std::vector<int> empty;
sort_utils::sort_container(empty);
assert(empty.empty());

std::vector<int> one{42};
sort_utils::sort_container(one);
assert(one.size() == 1 && one[0] == 42);

std::vector<int> values{3, 1, 2, 1, 5};
sort_utils::sort_container(values);
assert((values == std::vector<int>{1, 1, 2, 3, 5}));

std::vector<int> descending{5, 4, 3, 2, 1};
sort_utils::sort_container(descending, std::greater<>{});
assert((descending == std::vector<int>{5, 4, 3, 2, 1}));

int raw[]{4, 2, 9};
sort_utils::sort_container(raw);
assert(raw[0] == 2 && raw[1] == 4 && raw[2] == 9);
}

std::greater<>同样是透明比较器，配合sort_container的默认模板参数可以省去写具体类型。断言在NDEBUG定义后会被移除，所以正式发布版本不应只靠assert做校验；测试构建保持未定义NDEBUG即可。

一个容易忽略的细节：assert((values == std::vector<int>{1, 1, 2, 3, 5}))外层多了一对括号。原因是assert是宏，参数里的逗号会被当成宏参数分隔符，模板实参列表中的逗号尤其容易触发；加括号是最简单的规避方式。C++ 里更现代的做法是用测试框架的CHECK宏，它们通常用可变参数宏处理了这个问题。

常见坑点

1. 
   
2. ❌ 把std::sort用在std::list上。
3. 
   

✅std::list只有双向迭代器，不能传给std::sort；用它自己的sort()成员函数。

1. 
   
2. ❌ 比较器写return a <= b;。
3. 
   

✅ 必须严格弱序，写return a < b;；<=会让comp(a, a)为真，属于未定义行为。

1. 
   
2. ❌ 以为std::sort稳定，相等元素的相对顺序不变。
3. 
   

✅std::sort不保证稳定；需要稳定用std::stable_sort。

1. 
   
2. ❌ 模板函数定义放.cpp，头文件只留声明。
3. 
   

✅ 定义必须对实例化点可见；放头文件、.tpp，或在.cpp里显式实例化。

1. 
   
2. ❌ 多字段比较时把主键和次键都写成降序。
3. 
   

✅ 逐字段明确方向；if短路写法最不容易出错。

1. 
   
2. ❌ 用std::advance在链表上模拟随机访问再排序。
3. 
   

✅ 复杂度会退化，链表应用成员sort()；泛型入口应在编译期限制迭代器类别。

1. 
   
2. ❌ 浮点数据含 NaN 时直接排序。
3. 
   

✅ NaN 破坏严格弱序；先过滤或定义明确规则。

1. 
   
2. ❌ 只看「能编译」就认为模板正确。
3. 
   

✅ 覆盖空区间、单元素、重复元素、已排序、逆序，并用多种元素类型实例化。

总结

把排序封装成模板，核心不是「让代码少写几个类型」，而是把约束表达清楚：迭代器类别、比较器语义、稳定性要求。约束写得越明确，误用越早在编译期暴露，运行期的怪异行为就越少。项目层面则要记住模板的编译模型——定义可见性决定链接成败，INTERFACE目标决定配置一致性，边界测试决定泛型代码是否真的泛型。