基础复习
先上个对 int 类型数组的插入排序:
void insertionSort_01(int* seq, int firstIndex, int lastIndex) { for (int j = firstIndex + 1; j <= lastIndex; ++j) { int key = seq[j]; int i = j - 1; while (i >= firstIndex && key < seq[i]) { seq[i + 1] = seq[i]; --i; } seq[i + 1] = key; } } - 提出问题: 如果想排
double类型数组怎么办?
可以重载一个 double 版本:
void insertionSort_01_b(double* seq, int firstIndex, int lastIndex) { ... } 当然, 更好的方式是利用 C++ 的模板泛化元素类型:
template<class ElemType> void insertionSort_02(ElemType* seq, int firstIndex, int lastIndex) { ... } 步入正题
接着提出两个问题:
- 1 是否一定要求升序排列
- 2 ElemType 对象是否一定能使用
operator<
为解决问题 1, 我们可以额外写个降序排列版本:
template<class ElemType> void insertionSort_02_b(ElemType* seq, int firstIndex, int lastIndex) { for (...) { ... // Change {<} to {>} when comparing {key} and {seq[i]}: while (i >= firstIndex && key > seq[i]) { ... } ... } } 对于问题 2, 我们举个例子.
现有:
struct MyStruct { int aa; int bb; }; MyStruct arr_MyStruct[4] = { {1,4},{3,1},{9,-1},{12,0} }; 要求对 arr_MyStruct 中的元素以 MyStruct::aa 排序.
对于 C++ 新手来说, 这是一个比较难解决的问题, 也是问题 2 聚焦的关键.
对问题 1 的处理中, 我们将 "比较" 这个谓语 (predicate) 从 operator< 替换为 opeartor>;
这给了我们一些提示: 是否可以像我们用模板来泛化元素类型那样泛化谓语?
提出概念: 函数对象 (function object)
定义类 bad_greater:
// Omit the definition of class <MyStruct>. struct bad_greater { // {operator()} should be defined as a const method, // in order to make it available to <const bad_greater> instances. bool operator()(const MyStruct& left, const MyStruct& right) const { return left.aa > right.aa; } }; 称 bad_greater 所创建的实例为函数对象, 可以参考以下使用案例:
// Omit the definition of class <MyStruct>. MyStruct arr_MyStruct[4] = { {1,4},{3,1},{9,-1},{12,0} }; bad_greater compare; std::cout << compare(arr_MyStruct[0], arr_MyStruct[1]) << std::endl; // Use anonymous instance: std::cout << bad_greater()(arr_MyStruct[0], arr_MyStruct[1]) << std::endl; bad_greater 之所以 bad, 是因为其唯独提供对类 MyStruct 实例的比较.
定义一个模板类 good_less 并对 MyStruct 偏特化以解决这个问题:
// Omit the definition of class <MyStruct>. template<class T> struct good_less { bool operator()(const T& left, const T& right) const { return left < right; } }; template<> struct good_less<MyStruct> { bool operator()(const MyStruct& left, const MyStruct& right) const { return left.aa < right.aa; } }; 有了函数对象, 我们可以泛化算法中的谓语:
template<class ElemType, class _Pred> void insertionSort_03(ElemType* seq, int firstIndex, int lastIndex, const _Pred& compare) { for (...) { ... while (... && compare(key, seq[i])) { ...; } ... } } 调用函数 insertionSort_03() 时, 我们要注意, 编译器能直接根据传入参数推断模板的实例化类型; 因此无需提供额外的模板类参数:
// Omit the definition of class <MyStruct>. // Omit the definition of class <good_less>. // Omit the definition of class <good_greater>. MyStruct arr_MyStruct[4] = { {1,4},{3,1},{9,-1},{12,0} }; // Ascending order: insertionSort_03(arr_MyStruct, 0, 3, good_less<MyStruct>()); // Descending order: insertionSort_03(arr_MyStruct, 0, 3, good_greater<MyStruct>()); // Also works for array with orther types: double arr_double[4] = { 1,9.1,0.9,-3.1 }; insertionSort_03(arr_MyStruct, 0, 3, good_greater<double>()); std::sort() 的升降序排序
std::sort() 和我们的 insertionSort_03() 一样泛化的谓语, 而且 STL 还提供了类 std::greater 和 std::less 等用于定义函数对象.
升降序的使用方法参考以下代码:
#include <algorithm> #include <functional> double arr_double[4] = { 1,9.1,0.9,-3.1 }; // Ascending order: std::sort(arr_double, arr_double + 4); // Ascending order: std::sort(arr_double, arr_double + 4, std::less<double>()); // Descending order: std::sort(arr_double, arr_double + 4, std::greater<double>())); 你可能会问: 为什么第一个例子不用和之前说的一样, 传入一个函数对象?
这没什么高深的, 在 C++14 之前, 其实只是额外提供了一个只有两个参数的函数重载而已.
给个差不多的伪代码出来:
std::sort(seq_begin, seq_end){ std::sort(seq_begin, seq_end, std::less()); } C++14 之后在谓语类和 std::sort() 的定义上用了点小 trick, 下面给点启发性的例子 (如果不感兴趣, 你可以跳过这段):
template<class T = void> struct less { template<class T> bool operator()(const T& a, const T& b) const { return a < b; } }; template<..., class _Pred = less<void>> void sort(..., const _Pred& compare = {}) { ... } 说简单点, 就是 less 给了一个默认模板实例化类型 void; 而真正进行比较的 operator() 又是一个模板. 调用 sort 时, 不用考虑第三个参数 (函数对像) 具体是什么类型, 反正 operator() 在比较时会自行实例化.
可以参考以下使用案例:
// Under C++ 14 (or later) standard. #include <algorithm> #include <functional> double arr_double[4] = { 1,9.1,0.9,-3.1 }; std::sort(arr_double, arr_double + 4); // std::less<void> std::sort(arr_double, arr_double + 4, std::less()); // std::less<void> std::sort(arr_double, arr_double + 4, std::less<double>()); // std::less<double> int arr_int[4] = { 1,3,4,0 }; std::sort(arr_double, arr_double + 4, std::less()); // std::less<int> std::sort() 排其他类型实例
如果看懂了前面的内容, 想必你也能够猜出来怎么实现这个问题了.
注意, std::less 之类的谓语类型说到底就是结构体, 和我们上面实现的 good_less 没啥区别. 所以如果我们还是要排序上文提到的 MyStruct 数组:
// Omit the definition of class <MyStruct>. // Omit the definition of class <good_less>. // Omit the definition of class <good_greater>. #include <algorithm> MyStruct arr_MyStruct[4] = { {1,4},{3,1},{9,-1},{12,0} }; // Ascending order: std::sort(arr_MyStruct, arr_MyStruct + 4, good_less<MyStruct>()); // Descending order: std::sort(arr_MyStruct, arr_MyStruct + 4, good_greater<MyStruct>()); 统一指针和迭代器
作为一个 STL 使用者, 难免会遇到指针与迭代器不统一的问题. 例如以下例子:
// Use pointer: int arr_int[] = ...; std::sort(arr_int, ...); // Use iterator: std::vector<int> arr_vector = ...; std::sort(arr_vector.begin(), ...); 解决方式之一是统一泛化指针类型和迭代器类型, 这里把它们都当作类 _RandIt .
我们还是以最开始的 insertionSort 为例, 给出示范代码.
需要注意的是, 通过迭代器和指针获取元素类型 (用来定义 key )时, decltype 会保留解引用 (dereference) 后留下的引用 & (也就是说 decltype(arr_int[0]) 得到的类型不是 int 而是 int& ); 因此需要调用 std::remove_reference 来删除类型中的引用.
using index = long long; template<class _RandIt, class _Pr = std::less<void>> void insertionSort(_RandIt seq, index firstIndex, index lastIndex, const _Pr& comp = {}) { for (index j = firstIndex + 1; j <= lastIndex; ++j) { typename std::remove_reference<decltype(*seq)>::type key = seq[j]; index i = j - 1; while (i >= firstIndex && comp(key, seq[i])) { seq[i + 1] = seq[i]; --i; } seq[i + 1] = key; } } 再给个归并排序的代码吧! 就说到这里 (计组完全没学, 寄).
using index = long long; template<class _RandIt, class _Pr> void merge(_RandIt seq, index subAFirst, index subALast, index subBLast, auto MAX, auto MIN, const _Pr& comp) { auto END = comp(1, 2) ? MAX : MIN; size_t sizeSubA = subALast - subAFirst + 2; size_t sizeSubB = subBLast - subALast + 1; auto subA = new typename std::remove_reference<decltype(*seq)>::type[sizeSubA]; std::copy(seq + subAFirst, seq + subALast + 1, subA); subA[sizeSubA - 1] = END; auto subB = new typename std::remove_reference<decltype(*seq)>::type[sizeSubB]; std::copy(seq + subALast + 1, seq + subBLast + 1, subB); subB[sizeSubB - 1] = END; // Merge two subsequences to origin {seq[subAFirst : subBLast]}: for (index k = subAFirst, i = 0, j = 0; k <= subBLast; ++k) { if (i >= sizeSubA || j >= sizeSubB) return; // Merge: if (comp(subA[i], subB[j])) { seq[k] = subA[i]; ++i; } else { seq[k] = subB[j]; ++j; } } delete[] subA; delete[] subB; } template<class _RandIt, class _Pr = std::less<void>> void mergeSort(_RandIt seq, index firstIndex, index lastIndex, auto MAX, auto MIN, const _Pr& comp = {}) { if (firstIndex >= lastIndex) return; index mid = (firstIndex + lastIndex) / 2; mergeSort(seq, firstIndex, mid, MAX, MIN, comp); mergeSort(seq, mid + 1, lastIndex, MAX, MIN, comp); merge(seq, firstIndex, mid, lastIndex, MAX, MIN, comp); } 
