參考自侯捷的《stl源碼剖析》
stl算法主要分為非可變序列算法（指不直接修改其所操作的容器內容的算法），可變序列算法（指可以修改它們所操作的容器內容的算法），排序算法（包括對序列進行排序和合並的算法、搜索算法以及有序序列上的集合操作），數值算法（對容器內容進行數值計算）。
1.非可變序列算法
stl中的非可變序列算法有：for_each(), find(), find_if(), adjacent_find(), find_first_of(), count(), count_if(), mismatch(), equal(), search(), search_n(), find_end()。
for_each()：它用來遍歷一個序列中的元素，對指定序列中的每一個元素執行所定義的function操作，源碼如下：
template <class _InputIter, class _Function>
_Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
__STL_REQUIRES(_InputIter,
_InputIterator);
for
( ; __first != __last; ++__first)
__f(*__first);
return
__f;
}
注意他返回的是__f，可以這樣用他：
struct print{
int count;
print(){count=0;}
void operator()(int x)
{ /* function*/;}
};
print p = for_each(lt.begin(),lt.end(),print());
find()：用來查找指定序列中是否存在某個元素__val，並返回迭代器位置（如果不存在，返回end()），源碼如下:
template <class _InputIter, class _Tp>
inline _InputIter find(_InputIter __first, _InputIter __last,
const _Tp& __val,
input_iterator_tag)
{
while
(__first != __last && !(*__first == __val))
++__first;
return
__first;
}
find_if()：弄清楚find()的實現原理，就不難理解find_if()，這個函數返回使定義的函數__pred為真時迭代器的位置，同樣如果全為假，則返回end()，源碼如下:
template <class _InputIter, class _Predicate>
inline _InputIter find_if(_InputIter __first, _InputIter __last,
_Predicate __pred,
input_iterator_tag)
{
while
(__first != __last && !__pred(*__first))
++__first;
return
__first;
}
adjacent_find()：這個函數用來查找指定序列中是否有兩個連續的元素相等（或使__pred為真），並返回迭代器的位置，注意是返回第一個元素的位置，如果沒有，則返回end().函數有兩個形式，分別是相等和謂詞判斷,源碼如下：
/* 沒有謂詞判斷，即只判斷相等否*/
template <class _ForwardIter>
_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_EqualityComparable);
if (__first == __last)
return __last;
_ForwardIter __next = __first;
while(++__next != __last) {
if (*__first == *__next)
return __first;
__first = __next;
}
return __last;
}
/*有謂詞判斷，是否滿足__pred*/
template <class _ForwardIter, class _BinaryPredicate>
_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,
_BinaryPredicate __binary_pred) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,
typename iterator_traits<_ForwardIter>::value_type,
typename iterator_traits<_ForwardIter>::value_type);
if (__first == __last)
return __last;
_ForwardIter __next = __first;
while(++__next != __last) {
if (__binary_pred(*__first, *__next))
return __first;
__first = __next;
}
return __last;
}
謂詞判斷注意：__pred函數是需要兩個參數的。
find_first_of()：此函數用於查找指定序列中的元素是否存在一個元素，也在另一個序列元素中（就是查找是否存在交集），或是否各有一元素滿足指定函數__comp,源碼如下：
// find_first_of, with and without an explicitly supplied comparison function.
template <class _InputIter, class _ForwardIter>
_InputIter find_first_of(_InputIter __first1, _InputIter __last1,
_ForwardIter __first2, _ForwardIter __last2)
{
__STL_REQUIRES(_InputIter,
_InputIterator);
__STL_REQUIRES(_ForwardIter,
_ForwardIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL,
bool,
typename
iterator_traits<_InputIter>::value_type,
typename
iterator_traits<_ForwardIter>::value_type);
for
( ; __first1 != __last1; ++__first1)
for
(_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
if
(*__first1 == *__iter)
return
__first1;
return
__last1;
}
template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
_InputIter find_first_of(_InputIter __first1, _InputIter __last1,
_ForwardIter __first2, _ForwardIter __last2,
_BinaryPredicate __comp)
{
__STL_REQUIRES(_InputIter,
_InputIterator);
__STL_REQUIRES(_ForwardIter,
_ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPredicate,
bool,
typename
iterator_traits<_InputIter>::value_type,
typename
iterator_traits<_ForwardIter>::value_type);
for
( ; __first1 != __last1; ++__first1)
for
(_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
if
(__comp(*__first1, *__iter))
return
__first1;
return
__last1;
}
count():此函數用於計算某個元素在指定序列中出現的次數,此函數有兩種形式，第二種是把指定的n以引用的方式傳進去，從而得出n。源碼不難，很好理解，如下：
/*這個是傳應用n，是沒有返回值的*/
template <class _InputIter, class _Tp, class _Size>
void count(_InputIter __first, _InputIter __last, const _Tp& __value,
_Size& __n) {
__STL_REQUIRES(_InputIter,
_InputIterator);
__STL_REQUIRES(typename
iterator_traits<_InputIter>::value_type,
_EqualityComparable);
__STL_REQUIRES(_Tp,
_EqualityComparable);
for
( ; __first != __last; ++__first)
if
(*__first == __value)
++__n;
}
/*這個只有三個參數，是有N作為返回值的*/
template <class _InputIter, class _Tp>
typename iterator_traits<_InputIter>::difference_type
count(_InputIter __first, _InputIter __last, const _Tp& __value) {
__STL_REQUIRES(_InputIter,
_InputIterator);
__STL_REQUIRES(typename
iterator_traits<_InputIter>::value_type,
_EqualityComparable);
__STL_REQUIRES(_Tp,
_EqualityComparable);
typename
iterator_traits<_InputIter>::difference_type __n = 0;
for
( ; __first != __last; ++__first)
if (*__first == __value)
++__n;
return
__n;
}
count_if():和count()一樣，只不過是多了一個謂詞判斷，查找的是滿足謂詞判斷__pred的值的個數，源碼如下：
/*引用，沒有返回值*/
template <class _InputIter, class _Predicate, class _Size>
void count_if(_InputIter __first, _InputIter __last, _Predicate __pred,
_Size& __n) {
__STL_REQUIRES(_InputIter,
_InputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate,
bool,
typename
iterator_traits<_InputIter>::value_type);
for
( ; __first != __last; ++__first)
if
(__pred(*__first))
++__n;
}
/*有返回值*/
template <class _InputIter, class _Predicate>
typename iterator_traits<_InputIter>::difference_type
count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
__STL_REQUIRES(_InputIter,
_InputIterator);
__STL_UNARY_FUNCTION_CHECK(_Predicate,
bool,
typename
iterator_traits<_InputIter>::value_type);
typename
iterator_traits<_InputIter>::difference_type __n = 0;
for
( ; __first != __last; ++__first)
if
(__pred(*__first))
++__n;
return
__n;
}
mismatch()：此函數用於找出指定序列中首個不等於另一個序列（或首個使謂詞判斷為假）的元素的位置，注意是返回的兩個地址。
equal()：和mismatch函數一樣，不過他返回的是bool值，false和true。
search():此函數在一個指定的序列中匹配另一個序列，有兩種形式，同上，有一種是謂詞判斷的：源碼如下:
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2)
{
__STL_REQUIRES(_ForwardIter1,
_ForwardIterator);
__STL_REQUIRES(_ForwardIter2,
_ForwardIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL,
bool,
typename
iterator_traits<_ForwardIter1>::value_type,
typename
iterator_traits<_ForwardIter2>::value_type);
//
Test for empty ranges
if
(__first1 == __last1 || __first2 == __last2)
return
__first1;
//
Test for a pattern of length 1.
_ForwardIter2
__tmp(__first2);
++__tmp;
if
(__tmp == __last2)
return
find(__first1, __last1, *__first2);
//
General case.
_ForwardIter2
__p1, __p;
__p1
= __first2; ++__p1;
_ForwardIter1
__current = __first1;
while
(__first1 != __last1) {
__first1
= find(__first1, __last1, *__first2);
if
(__first1 == __last1)
return
__last1;
__p
= __p1;
__current
= __first1;
if
(++__current == __last1)
return
__last1;
while
(*__current == *__p) {
if
(++__p == __last2)
return
__first1;
if
(++__current == __last1)
return
__last1;
}
++__first1;
}
return
__first1;
}
template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2,
_BinaryPred __predicate)
{
__STL_REQUIRES(_ForwardIter1,
_ForwardIterator);
__STL_REQUIRES(_ForwardIter2,
_ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPred,
bool,
typename
iterator_traits<_ForwardIter1>::value_type,
typename
iterator_traits<_ForwardIter2>::value_type);
//
Test for empty ranges
if
(__first1 == __last1 || __first2 == __last2)
return
__first1;
//
Test for a pattern of length 1.
_ForwardIter2
__tmp(__first2);
++__tmp;
if
(__tmp == __last2) {
while
(__first1 != __last1 && !__predicate(*__first1, *__first2))
++__first1;
return
__first1;
}
//
General case.
_ForwardIter2
__p1, __p;
__p1
= __first2; ++__p1;
_ForwardIter1
__current = __first1;
while
(__first1 != __last1) {
while
(__first1 != __last1) {
if
(__predicate(*__first1, *__first2))
break;
++__first1;
}
while
(__first1 != __last1 && !__predicate(*__first1, *__first2))
++__first1;
if
(__first1 == __last1)
return
__last1;
__p
= __p1;
__current
= __first1;
if
(++__current == __last1) return __last1;
while
(__predicate(*__current, *__p)) {
if
(++__p == __last2)
return
__first1;
if
(++__current == __last1)
return
__last1;
}
++__first1;
}
return
__first1;
}
search_n():他所做的工作是在指定序列中查找是否有n個連續元素與給定元素相等（或使得謂詞判斷為真），使用時要注意參數順序，源碼余下：
template <class _ForwardIter, class _Integer, class _Tp>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_EqualityComparable);
__STL_REQUIRES(_Tp, _EqualityComparable);
if (__count <= 0)
return __first;
else {
__first = find(__first, __last, __val);
while (__first != __last) {
_Integer __n = __count - 1;
_ForwardIter __i = __first;
++__i;
while (__i != __last && __n != 0 && *__i == __val) {
++__i;
--__n;
}
if (__n == 0)
return __first;
else
__first = find(__i, __last, __val);
}
return __last;
}
}
template <class _ForwardIter, class _Integer, class _Tp, class
_BinaryPred>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val,
_BinaryPred __binary_pred) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool,
typename iterator_traits<_ForwardIter>::value_type, _Tp);
if (__count <= 0)
return __first;
else {
while (__first != __last) {
if (__binary_pred(*__first, __val))
break;
++__first;
}
while (__first != __last) {
_Integer __n = __count - 1;
_ForwardIter __i = __first;
++__i;
while (__i != __last && __n != 0 && __binary_pred(*__i, __val))
{
++__i;
--__n;
}
if (__n == 0)
return __first;
else {
while (__i != __last) {
if (__binary_pred(*__i, __val))
break;
++__i;
}
__first = __i;
}
}
return __last;
}
}
find_end():此函數用於找出在一個指定序列中另一個序列的最後一個匹配序列的位置，如果沒有則返回last(end()),仍然是有兩種形式，現只給出一種即可：
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2,
forward_iterator_tag, forward_iterator_tag)
{
if (__first2 == __last2)
return __last1;
else {
_ForwardIter1 __result = __last1;
while (1) {
_ForwardIter1 __new_result
= search(__first1, __last1, __first2, __last2);
if (__new_result == __last1)
return __result;
else {
__result = __new_result;
__first1 = __new_result;
++__first1;
}
}
}
2. 可變序列算法
stl的可變序列算法很多，有三十個左右，現在只看看較常用的幾個算法：copy, copy_backward, swap, iter_swap, swap_ranges, transform, replace_if,
fill, fill_n, generate, generate_n, remove,reverse, reverse_copy.
copy():區間復制函數，將原區間內的元素一次復制到目的區間，三個參數是first，last，result，其中的result是目的區間的首地址，源碼如下：
template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __copy(_InputIter __first, _InputIter __last,
_OutputIter
__result,
input_iterator_tag, _Distance*)
{
for ( ; __first != __last; ++__result, ++__first)
*__result =
*__first;
return __result;
}
copy_backward():與copy算法相似，也是將原區間內的元素一次復制到目的區間，但元素的復制順序是從後向前的，但要注意你所輸入的result是目的區間的結束位置，所以，copy_backward和copy的結果是一樣的，只不過是內部的實現細節不一樣罷了,源碼如下：
template <class _BidirectionalIter1, class _BidirectionalIter2,
class _Distance>
inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
_BidirectionalIter1 __last,
_BidirectionalIter2 __result,
bidirectional_iterator_tag,
_Distance*)
{
while (__first != __last)
*--__result
= *--__last;
return __result;
}
swap():交換元素（這兩個元素是以引用的形式傳進來的）:
template <class _Tp>
inline void swap(_Tp& __a, _Tp& __b) {
_Tp __tmp = __a;
__a = __b;
__b = __tmp;
}
iter_swap():函數是迭代器元素交換，參數是兩個迭代器指針，注意：數據必須是可交換的：
template <class _ForwardIter1, class _ForwardIter2, class _Tp>
inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*) {
_Tp __tmp = *__a;
*__a = *__b;
*__b = __tmp;
}
template <class _ForwardIter1, class _ForwardIter2>
inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) {
__iter_swap(__a, __b, __VALUE_TYPE(__a));
}
swap_ranges():顧名思意，他的作用是將原區間與目的區間的元素作交換，當然前提是元素必須是可交換的，有三個參數：first，last,result,其中result是目的區間的首地址，源碼如下：
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2
__first2) {
for ( ; __first1 != __last1; ++__first1, ++__first2)
iter_swap(__first1, __first2);
return __first2;
}
transform():這個函數非常有用，可以替代你做不少復雜的工作，目的是將原區間的元素依次通過操作的到目的元素，這些結果是要存 放到目的區間的，他有兩個實現（一）op為一元操作符，故只能接受一個參數，transform的四個參數依次是 first，last,result,op其中result是目的區間的首地址，（二）op為二元操作符，故原函數需要多一個參數，五個參數依次 是：first,last,first,result,op，第三個first是第二個區間的首地址，result是目的區間的首地址，op為二元操作符：
template <class _InputIter, class _OutputIter, class
_UnaryOperation>
_OutputIter transform(_InputIter __first, _InputIter __last,
_OutputIter
__result, _UnaryOperation __opr) {
for ( ; __first != __last; ++__first, ++__result)
*__result =
__opr(*__first);
return __result;
}
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _BinaryOperation>
_OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2
__first2, _OutputIter __result,
_BinaryOperation
__binary_op) {
for ( ; __first1 != __last1; ++__first1, ++__first2,
++__result)
*__result = __binary_op(*__first1,
*__first2);
return __result;
}
replace():替換函數，將原區間內為old的元素全部替換為new元素，old和new是需要函數參數提供的：
template <class _ForwardIter, class _Tp>
void replace(_ForwardIter __first, _ForwardIter __last,
const _Tp& __old_value, const
_Tp& __new_value) {
for ( ; __first != __last; ++__first)
if
(*__first == __old_value)
*__first = __new_value;
}
replace_if():很容易理解，這個函數將原區間內滿足一元謂詞判斷的元素全部替換為new元素：
template <class _ForwardIter, class _Predicate, class _Tp>
void replace_if(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred, const
_Tp& __new_value) {
for ( ; __first != __last; ++__first)
if
(__pred(*__first))
*__first = __new_value;
}
fill():填充函數，將原區間全部填滿你所指定的元素，源碼如下：
template <class _ForwardIter, class _Tp>
void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) {
for ( ; __first != __last; ++__first)
*__first =
__value;
}
fill_n()：也是填充，是填滿[first,first+n]區間內的元素，源碼如下：
template <class _OutputIter, class _Size, class _Tp>
_OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value) {
for ( ; __n > 0; --__n, ++__first)
*__first =
__value;
return __first;
}
generate()和generate_n():
兩個函數都是生成函數，用指定的生成器（函數）來填滿指定區間，為了便於說明，先看看兩個函數的源碼，之所以把這兩個函數放到一起，是因為他們長的太像了，一起討論方便：
template <class _ForwardIter, class _Generator>
void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
for ( ; __first != __last; ++__first)
*__first =
__gen();
}
template <class _OutputIter, class _Size, class _Generator>
_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
for ( ; __n > 0; --__n, ++__first)
*__first = __gen();
return __first;
}
其中的一句話：*__first = gen()，可以看出，gen()函數是沒有參數的，所以如果沒有一個關於gen()的全局變量，gen()函數生成的結果是一樣的，所以做好對gen()檢查好了再用，不然有可能整個區間的元素是一樣的。
remove_copy():將原區間中不等於指定value的元素復制到目的區間，源碼如下：
template <class _InputIter, class _OutputIter, class _Tp>
_OutputIter remove_copy(_InputIter __first, _InputIter __last,
_OutputIter
__result, const _Tp& __value) {
for ( ; __first != __last; ++__first)
if
(*__first != __value) {
*__result = *__first;
++__result;
}
return __result;
}
remove_copy_if():這個函數將remove_copy中的value替換為一個謂詞判斷，只有不滿足謂詞判斷的元素才會被復制到目的區間內,源碼如下：
template <class _InputIter, class _OutputIter, class _Predicate>
_OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
_OutputIter
__result, _Predicate __pred) {
for ( ; __first != __last; ++__first)
if
(!__pred(*__first)) {
*__result = *__first;
++__result;
}
return __result;
}
remove():這個算法是將容器中等於value的元素全部去掉，同樣是先看看源碼，在對他作分析：
_ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
const _Tp&
__value) {
__first = find(__first, __last, __value);
_ForwardIter __i = __first;
return __first == __last ? __first
:
remove_copy(++__i, __last, __first, __value);
}
其中先找出第一個滿足value的值的位置，再作判斷，然後調用remove_copy()函數將不等於value的元素復制到新的區間 上，可以看到，無論是空間或者是時間，這個算法的執行都不怎麼好，remove_copy()操作浪費了太多的時間和空間，不過考慮到他的通用性，這個函 數還是不錯的。
reverse():函數的功能是翻轉指定區間的全部元素，算法思想很簡單就能想到，不過源碼寫的很有技巧性，看後可以讓人眼前一亮的感覺，源碼分析：
template <class _BidirectionalIter>
void __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
bidirectional_iterator_tag) {
while (true)
if (__first
== __last || __first == --__last)
return;
else
iter_swap(__first++, __last);
}
reverse_copy():不對原區間的元素進行操作，而是將其翻轉輸出到指定的目的區間，源碼如下：
template <class _BidirectionalIter, class _OutputIter>
_OutputIter reverse_copy(_BidirectionalIter __first,
_BidirectionalIter __last,
_OutputIter
__result) {
while (__first != __last) {
--__last;
*__result =
*__last;
++__result;
}
return __result;
}
3.排序算法
由於內容太多，只列出典型部分啦：
Insertion Sort：算法的復雜度為O(N^2)，最好情況下時間復雜度為O(N)。在數據量很少時，尤其還是在序列“幾近排序但尚未完成”時，有著很不錯的效果。
// 默認以漸增方式排序
template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first,
RandomAccessIterator last)
{
if (first == last) return;
// --- insertion sort 外循環 ---
for (RandomAccessIterator i = first + 1; i != last; ++i)
__linear_insert(first, i, value_type(first));
// 以上，[first,i) 形成一個子區間
}
template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first,
RandomAccessIterator last, T*)
{
T value = *last; // 記錄尾元素
if (value < *first){ // 尾比頭還小 (注意，頭端必為最小元素)
copy_backward(first, last, last + 1); // 將整個區間向右移一個位置
*first = value; // 令頭元素等於原先的尾元素值
}
else // 尾不小於頭
__unguarded_linear_insert(last, value);
}
template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value)
{
RandomAccessIterator next = last;
--next;
// --- insertion sort 內循環 ---
// 注意，一旦不再出現逆轉對(inversion),循環就可以結束了
while (value < *next){ // 逆轉對(inversion)存在
*last = *next; // 調整
last = next; // 調整迭代器
--next; // 左移一個位置
}
*last = value; // value 的正確落腳處
}
Quick Sort：平均復雜度為O(NlogN)，可是最壞情況下將達O(N^2)。
Median-of-Three（三點中值）：因為任何元素都可以當做樞軸(pivot)，為了避免元素輸入時不夠隨機帶來的惡化效應，最理想最穩當的方式就是取整個序列的投、尾、中央三個元素的中值(median)作為樞軸。
// 返回 a，b，c之居中者
template <class T>
inline const T& __median(const T& a, const T& b, const T& c)
{
if (a < b)
if (b < c) // a < b < c
return b;
else if (a < c) // a < b, b >= c, a < c --> a < b <= c
return c;
else // a < b, b >= c, a >= c --> c <= a < b
return a;
else if (a < c) // c > a >= b
return a;
else if (b < c) // a >= b, a >= c, b < c --> b < c <= a
return c;
else // a >= b, a >= c, b >= c --> c<= b <= a
return b;
}
template <class RandomAccessIterator, class T>
RandomAccessIterator __unguarded_partition(
RandomAccessIterator first,
RandomAccessIterator last,
T pivot)
{
while(true){
while (*first < pivot) ++first; // first 找到 >= pivot的元素就停
--last;
while (pivot < *last) --last; // last 找到 <=pivot
if (!(first < last)) return first; // 交錯，結束循環
// else
iter_swap(first,last); // 大小值交換
++first; // 調整
}
}
Heap Sort：heap_sort的任務是找出middle-first個最小元素，因此，首先界定出區間[first,middle)，並利用make_heap()將它組織成一個max-heap，然後就可以講[middle,last)中的每一個元素拿來與max-heap的最大值比較(max-heap的最大值就在第一個元素)；如果小於該最大值，就互換位置並重新保持max-heap的狀態。如此一來，當我們走遍整個[middle,last)時，較大的元素都已經被抽離出[first,middle)，這時候再以sort_heap()將[first,middle)做一次排序。
// paitial_sort的任務是找出middle - first個最小元素。
template <class RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last)
{
__partial_sort(first, middle, last, value_type(first));
}
template <class RandomAccessIterator,class T>
inline void __partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, T*)
{
make_heap(first, middle); // 默認是max-heap，即root是最大的
for (RandomAccessIterator i = middle; i < last; ++i)
if (*i < *first)
__pop_heap(first, middle, i, T(*i), distance_type(first));
sort_heap(first,middle);
}
Intro Sort: 不當的樞軸選擇，導致不當的分割，導致Quick Sort惡化為O(N^2)。David R. Musser於1996年提出一種混合式排序算法，Introspective Sorting。其行為在大部分情況下幾乎與 median-of-3 Quick Sort完全相同。但是當分割行為(partitioning)有惡化為二次行為傾向時，能自我偵測，轉而改用Heap Sort，使效率維持在O(NlogN)，又比一開始就使用Heap Sort來得好。大部分STL的sort內部其實就是用的IntroSort。
template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first,
RandomAccessIterator last)
{
if (first != last){
__introsort_loop(first, last, value_type(first), __lg(last-first)*2);
__final_insertion_sort(first,last);
}
}
// __lg()用來控制分割惡化的情況
// 找出2^k <= n 的最大值,例：n=7得k=2; n=20得k=4
template<class Size>
inline Size __lg(Size n)
{
Size k;
for (k = 0; n > 1; n >>= 1)
++k;
return k;
}
// 當元素個數為40時,__introsort_loop的最後一個參數
// 即__lg(last-first)*2是5*2,意思是最多允許分割10層。
const int __stl_threshold = 16;
template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,
RandomAccessIterator last, T*,
Size depth_limit)
{
while (last - first > __stl_threshold){ // > 16
if (depth_limit == 0){ // 至此，分割惡化
partial_sort(first, last, last); // 改用 heapsort
return;
}
--depth_limit;
// 以下是 median-of-3 partition，選擇一個夠好的樞軸並決定分割點
// 分割點將落在迭代器cut身上
RandomAccessIterator cut = __unguarded_partition
(first, last, T(__median(*first,
*(first + (last - first)/2),
*(last - 1))));
// 對右半段遞歸進行sort
__introsort_loop(cut,last,value_type(first), depth_limit);
last = cut;
// 現在回到while循環中，准備對左半段遞歸進行sort
// 這種寫法可讀性較差，效率也並沒有比較好
}
}
函數一開始就判斷序列大小，通過個數檢驗之後，再檢測分割層次，若分割層次超過指定值，就改用partial_sort()，即Heap sort。都通過了這些校驗之後，便進入與Quick Sort完全相同的程序。當__introsort_loop()結束，[first,last)內有多個“元素個數少於或等於”16的子序列，每個序列有相當程序的排序，但尚未完全排序（因為元素個數一旦小於 __stl_threshold，就被中止了）。回到母函數，再進入__final_insertion_sort()：
template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last)
{
if (last - first > __stl_threshold){
// > 16
// 一、[first,first+16)進行插入排序
// 二、調用__unguarded_insertion_sort，實質是直接進入插入排序內循環，
// *參見Insertion sort 源碼
__insertion_sort(first,first + __stl_threshold);
__unguarded_insertion_sort(first + __stl_threshold, last);
}
else
__insertion_sort(first, last);
}
template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last)
{
__unguarded_insertion_sort_aux(first, last, value_type(first));
}
template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first,
RandomAccessIterator last,
T*)
{
for (RandomAccessIterator i = first; i != last; ++i)
__unguarded_linear_insert(i, T(*i));
}
4.數值算法
列舉一下，我也沒看多少：
accumulate:
template<class InputIterator, class Type>
Type accumulate(
InputIterator _First,
InputIterator _Last,
Type _Val
);
template<class InputIterator, class Type, class BinaryOperation>
Type accumulate(
InputIterator _First,
InputIterator _Last,
Type _Val,
BinaryOperation _Binary_op
);
inner_product：第二個序列的個數必須大於等於第一個序列的個數。因為，inner_product內部實現是以第一序列的元素個數為依據的，將兩個序列都走了一遍。可能實現為while( _First1!=_Last1){...}或者n=_Last1-_First1;while(n>0){...}
template<class InputIterator1, class InputIterator2, class Type>
Type inner_product(
InputIterator1 _First1,
InputIterator1 _Last1,
InputIterator2 _First2,
Type _Val
);
template<class InputIterator1, class InputIterator2, class Type,
class BinaryOperation1, class BinaryOperation2>
Type inner_product(
InputIterator1 _First1,
InputIterator1 _Last1,
InputIterator2 _First2,
Type _Val,
BinaryOperation1 _Binary_op1,
BinaryOperation2 _Binary_op2
);
adjacent_difference：
template<class InputIterator, class OutIterator>
OutputIterator adjacent_difference(
InputIterator _First,
InputIterator _Last,
OutputIterator _Result
);
template<class InputIterator, class OutIterator, class BinaryOperation>
OutputIterator adjacent_difference(
InputIterator _First,
InputIterator _Last,
OutputIterator _Result,
BinaryOperation _Binary_op
);
partial_sum：partial_sum與先前介紹的adjacent_difference互為逆運算。如果對區間值1,2,3,4,5執行partial_sum，獲 得結果為1,3,6,10,15,再對此結果執行adjacent_difference，便會獲得原始區間值1,2,3,4,5。反之亦然。
template<class InputIterator, class OutIt>
OutputIterator partial_sum(
InputIterator _First,
InputIterator _Last,
OutputIterator _Result
);
template<class InputIterator, class OutIt, class Fn2>
OutputIterator partial_sum(
InputIterator _First,
InputIterator _Last,
OutputIterator _Result,
BinaryOperation _Binary_op
);
