# 第6章 算法
## 6.1算法概观
算法指在有限的步骤，解决逻辑或数学上的问题。
算法复杂度可以用 Big-Oh 标记方式：如果有任何正常常数 `c` 和 `N0`，使得当 `$ N ≥ N_{0} $` 时，`$ T(N) ≤ cF(N) $`，那么我们便可将 `$ T(N) $` 的复杂度表示为 `O(F(N))`。
质变算法（mutating algorithm）指运算过程中会更改区间内的元素内容。
所有 STL 泛型算法的前两个参数都是一对迭代器（iterator），通常称为 `first` 和 `last`，用以标示算法的操作区间。STL 习惯采用前闭后开区间表示法，写成 `[first, last)`，表示区间涵盖 `first` 至 `last` 之间所有元素。这个 `[first, last)` 区间的必要条件是，必须能够经 increment 操作符反复作用，从 `first` 到达 `last`。
许多 STL 算法不只支持一个版本，这一类算法的某个版本采用缺省运算行为，另一个版本提供额外参数，接收外界传入一个仿函数（functor），以便采用其他策略。
质变算法通常提供两个版本：一个是 in-place 版，就地改变其操作对象；另一个是 copy 版，将操作对象的内容复制一份副本，然后在副本上进行修改并返回该副本。
## 6.2 算法的泛化过程
算法的泛化：把操作对象的型别加以抽象，把操作对象的标示法和区间目标的移动行为抽象化，整个算法也就在一个抽象层面上工作。
``` c++
template <class Iterator, class T>
Iterator find(Iterator begin, Iterator end, const T& value) {
while (begin != end && *begin != value)
++begin;
return begin;
```
## 6.3 数值算法
客户端需要包含表头 `<numeric>`，SGI 将它们实现于 `<stl_numeric.h>` 文件中。
## 6.4 基本算法
STL 标准规格并没有区分基本算法和复杂算法，但 SGI 却把常用的一些算法定义于 `<stl_algobase.h>`，其它算法定义于 `<stl_algo.h>`。
SGI STL 的 copy 算法使用了函数重载、型别特性、偏特化等编程技巧用于加强效率。
首先对于原生指针进行了重载，内部实现直接进行内存拷贝。
``` c++
// 完全泛化版本
template <class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result) {
return __copy_dispatch<InputIterator, OutputIterator>()(first, last, result);
}
// 针对原生指针的重载
inline char* copy(const char* first, const char* last, char* result) {
memmove(result, first, last - first);
return result + (last - first);
}
inline char* copy(const wchar_t* first, const wchar_t* last, char* result) {
memmove(result, first, sizeof(wchar_t) * (last - first));
return result + (last - first);
}
```
其次泛化版本的 copy 函数调用了一个 `__copy_dispatch()`，该函数有一个完全泛化版本和两个偏特化版本：
```c++
template <class InputIterator, class OutputIterator>
struct __copy_dispatch {
OutputIterator operator()(InputIterator first, InputIterator last, OutputIterator result) {
return __copy(first, last, result, iterator_category(first));
}
};
// 偏特化版本（1），两个参数都是 T* 指针形式
template <class T>
struct __copy_dispatch<T*, T*> {
T* operator()(T* frist, T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result, t());
}
};
// 偏特化版本（2），第一个参数为 const T*指针形式，第二个参数为 T* 指针形式
template <class T>
struct __copy_dispatch<const T*, T*> {
T* operator()(const T* frist, const T* last, T* result) {
typedef typename __type_traits<T>::has_trivial_assignment_operator t;
return __copy_t(first, last, result, t());
}
};
template <class T>
inline T* __copy_t(const T* first, const T* last, T* result, __true_type) {
memmove(result, first, sizeof(T) * (last - frist));
return result + (last - first);
}
template <class T>
inline T* __copy_t(const T* first, const T* last, T* result, __false_type) {
return __copy_d(first, last, result, (ptrdiff_t*), 0);
}
```
如果指针所指对象拥有 non-trivial assignment operator，复制操作就一定得通过它来进行，但如果指针所指对象拥有的是 trivial assignment operator，复制操作可以不通过它，直接以最快的内存对拷贝方式 `memmove`。
泛化版本的 copy 分两种实现，一种是以迭代器等同与否，决定循环是否继续，速度慢；以 n 决定循环的执行次数（n 为距离），速度快。
## 6.5 set 相关算法
STL 一共提供四种与 set 相关的算法，`sorted range` 是这些算法的前提：
* 并集（union）：`$ S_1 \cup S_2 $`；
* 交集（intersection）: `$ S_1 \cap S_2$`；
* 差集（difference）：出现于 `$ S_1$` 但不出现与 `$ S_2 $` 的每一个元素；
* 对称差集（symmetric difference）：出现于 `$ S_1$` 但不出现与 `$ S_2 $` 的每一个元素，以及出现于 `$ S_2$` 但不出现与 `$ S_1 $` 的每一个元素；
## 6.6 heap 算法
包括 `make_heap()`、`pop_heap()`、`push_heap()`、`sort_heap()`等，定义在 `<stl_algo.h>` 头文件中。
## 6.7 其他算法
`remove` 移除 `[first, last)` 之中所有与 value 相等的元素，这一算法并不真正从容器中删除那些元素，而是将每一个不与 value 相等的元素轮番赋值给 first 之后的空间。
`sort` 在数据量大时采用 Quick Sort，分段递归排序。一旦分段后的数据量小于某个门槛，为避免 Quick Sort 的递归调用带来过大的额外负荷（overhead），就改用 Insertion Sort。如果递归层次过深，还会改用 Heap Sort。
Insertion Sort 以双层循环的形式进行。外循环遍历整个序列，每次迭代决定出一个子区间：内循环遍历子区间，将子区间内的每一个逆转对（inversion），倒转过来。这个算法的复杂度为 `$ O(N^2) $`，但是当数据量很少时，却有不错的效果。
Quick Sort 算法是目前已知最快的排序法，平均复杂度为 `$ O(NlogN) $`，最坏情况下将达 `$ O(N^2) $`，不过 IntroSort 可将最坏情况推到 `$ O(NlogN) $`。
Quick Sort 算法流程：
1. 如果 S 的元素个数为 0 或 1，结束。
2. 取 S 中的任何一个元素，当作枢轴（pivot）v。
3. 将 S 分割为 L，R，使 L 内的每一个元素都小于 或等于 v，R 内的每一个元素都大于或等于 v。
4. 对L，R递归执行 Quick Sort。
最坏情况发生在 分割（partitioning）时产生一个空的子空间。
为了避免“元素当初输入时不够随机”，最理想最稳当的方式就是取整个序列的头、尾中央三个位置的元素，以其中值（median）作为枢轴。这种做法称为 median-of-three partitioning。
**Partitioning**：令头端迭代器 `first` 向尾部移动，尾端迭代器 `last` 向头部移动。当 `*first` 大于或等于枢轴时就停下来，当 `*last` 小于或等于枢轴时也停下来，然后检验两个迭代器是否交错。如果 `first` 仍然在左而 `last` 仍然在右，就将两者元素互换，然后各自调整一个位置再继续进行相同的行为。如果发现两个迭代器交错，则以 `first` 为轴将序列分为左右两半。
``` c++
template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(
RandomAccessIterator first, RandomAccessIterator last, T pivot) {
while (true) {
while (*first < pivot) ++first;
--last;
while (pivot < *last) --last;
if (!(fist < last)) return first;
iter_swap(first, last);
++fist;
}
};
```
**threshold** 在小数据量的情况下，简单的 Insertion Sort 可能快过 Quick Sort，因为 Quick Sort 会为了极小的子序列而产生许多的函数递归调用。
Introspective Sorting（内省式排序），简称 IntroSort，其行为在大部分情况下几乎与 median-of-3 Quick Sort 完全相同。但是当分割行为有恶化为二次行为的倾向时，能够自我侦测，转而改用 Heap Sort。
``` c++
template <class RandomAcessIterator, class T, class Size>
void __introsort_loop(RandomAcessIterator first, RandomAcessIterator last, T*, Size depth_limit) {
while (last - first > __stl_threshold) { // __stl_threshold = 16
if (depth_limit == 0) {
partial_sort(first, last, last); // do Heap Sort
return;
}
--depth_limit;
... // do Quick Sort
}
}
```
**nth_element** 的实现为不断以 median-of-3 三点中值为枢轴将序列分割成 L 和 R，nth 落在哪一边，就继续对该子序列进行分割，直到分割后的子序列长度不大于 3，便执行 Insertion Sort。
**Merge Sort**：首先将区间对半分割，左右两端各自排序，在利用 `inplace_merge` 重新组合为一个完整的有序序列。对半分割的操作可以递归进行，直到每一段的长度为 0 或 1。
Merge Sort 的复杂度为 `$ O(NlogN) $`。虽然和 Quick Sort 是一样的，但因为 Merge Sort 需借用额外的内存，而且在内存之间移动数据也会耗费不少时间，所以Merge Sort 的效率比不上 Quick Sort。
