基础复习
先上个对 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 (int j = firstIndex + 1; j <= lastIndex; ++j) {
ElemType key = seq[j];
int i = j - 1;
// Change {<} to {>} when comparing {key} and {seq[i]}:
while (i >= firstIndex && key > seq[i]) {
seq[i + 1] = seq[i];
--i;
}
seq[i + 1] = key;
}
}
对于问题 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)
定义以下的类:
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& a, const MyStruct& b) const { return a.aa > b.bb; }
};
称 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& a, const T& b) const { return a < b; }
};
template<>
struct good_less<MyStruct>
{
bool operator()(const MyStruct& a, const MyStruct& b) const { return a.aa < b.bb; }
};
有了函数对象, 我们可以泛化算法中的谓语:
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, bad_less<MyStruct>());
// Descending order:
insertionSort_03(arr_MyStruct, 0, 3, bad_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 之前, 其实这只是一个函数重载而已. 给个差不多的伪代码出来:
// Pseudocode for definition of std::sort (with only 2 arguments):
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 ElemType>
bool operator()(const ElemType& a, const ElemType& b) const { return a < b; }
};
template<class ElemType, 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);
}