C++ STL（第十七篇：算法）

1、算法的概述

算法，就是一個問題的解法。以有限的步驟，解決邏輯或數學上的問題。STL 收錄了極具複用價值的 70 個算法，包括和赫赫有名的排序、查找、排列、組合等。

有的算法需要搭配特定的資料結構。例如 binary search tree（二叉查找樹）和 RB-tree 便是為了解決查找問題而發展出來的特殊資料結構，hashtable 擁有快速查找的能力。map-heap可以協助完成所謂的堆排序。

通常評價一個算法的好壞，是通過兩個次元，時間複雜度 和 空間複雜度，這兩個在整理 算法及其複雜度分析 中進行了詳細的說明，這裡就不贅述了。

算法也可以分為兩大類，質變算法 和 非質變算法。

質變算法，是指運算過程中會更改區間内的元素内容。如拷貝（copy）、互換（swap）、替換（replace）、删除（remove）等。

非質變算法，是指運算過程中不會更改區間内的元素内容。如查找（find）、比對（search）、計數（count）、巡訪（for_each）、尋找極緻（max，min）等。

2、算法的一般形式

所有的泛型算法的前面兩個參數都是一對疊代器，通常稱為 first 和 last，用以标示算法的操作區間。STL 習慣采用前閉後開區間表示法，寫成 [first, last)，表示區間涵蓋 first 與 last 之間的所有元素。 當 first == last 時，表示是一個空區間。

這個[first, last) 區間的必要條件是，必須能夠通過累加操作，從 first 到達 last。編譯器本身無法強求這一點，如果這個條件不成立，會導緻未可預期的結果。

前面整理疊代器時，我們知道疊代器可分為 5 類。每一個 STL 算法的聲明，都表現出它所要求的最低疊代器類型。例如，find() 需要一個 inputIterator，這是它的最低要求，但它也可以接受更高類型的疊代器。

許多 STL 算法不止支援一個版本。這一類算法的某個版本采用預設運算行為，另一個版本提供額外參數，接受外界傳入一個仿函數，以便采用其他政策。例如，unique() 預設情況下使用equality操作符來比較兩個相鄰元素，但如果這些元素的型别并未提供 equality 操作符，或使用者自定義 equality 操作符，便可以傳一個仿函數給另一個版本 unique()。

質變算法通常提供兩個版本：一個是 in-place（就地進行）版，就地改變其操作對象；另一個是 copy（另地進行）版，将操作對象的内容複制一份副本，然後在副本上進行修改并傳回該副本。

下面就整理幾個簡單的算法，之後會對複雜的算法進行整理。

3、最簡單算法（數值算法）

accumulate 計算區間内的總和，其參數 init 是用來明确定義的值，如果計算區間 first 與 last 之間的總和，可把 init 設為0。代碼如下：

//版本1
template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
	for(;first != last; ++first)
		init = init + *first;				//将每個元素值累加到初值 init 身上
	return init;
}

//版本2
template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op)
{
	for(;first != last; ++first)
		init = binary_op(init, *first); 	//對每個元素執行二進制操作
	return init;
}
           

adjacent_difference 用來計算 [first, last) 中相鄰元素的差額。其核心代碼如下：

template<class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result)
{
	if( first == last )
		return result;
	
	*result = *first;	//首先記錄第一個元素
	return __adjacent_difference(first, last, result, value_type(first));
}

template<class InputIterator, class OutputIterator, class T>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result)
{
	T value = *first;
	while( ++first != last )
	{
		T tmp = *first;
		*++result = tmp - value;
		value = tmp
	}
	return ++result;
}
           

當然它也有第二個版本的函數，傳入一個仿函數，這裡就不做具體整理了。adjacent_difference 算法就是将 *first 指派給 *result，并針對 [first+1, last) 内的每個疊代器 i，将 *i - *(i-1) 的值指派給 *(result+(i - first))。

inner_product 計算 [first1, last1) 和 [first2, first2+(last1-first1)) 的一般内積。代碼如下：

template<class InputIterator1， class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init)
{
	//以第一序列元素個數為據，将兩個序列都走一遍
	for(;first1 != last1; ++first1, ++first2)
		init = init + (*first1 * *first2);
	
	return init;
}
           

其中參數 init 和 accumulate 中的參數 init 一樣，用來明确定義的結果。

partial_sum 用來計算局部總和。它會将 *first 指派給 *result，将 *first 和 *(first+1) 的和指派給 *(result+1)，依次類推。代碼如下：

template<class InputIterator, class OutputIterator>
OutputIterator partial_sum( InputIterator first, InputIterator last, OutputIterator result)
{
	if( first == last )
		return result;
	
	return __parial_sum(first, last, result, value_type(first));
}

template<class InputIterator, class OutputIterator, class T>
OutputIterator __partial_sum( InputIterator first, InputIterator last, OutputIterator result, T*)
{
	T value = *first;
	while( ++first != last)
	{
		value = value + *first;
		*++result = value;
	}
	
	return ++result;
}
           

partial_sum 和 adjacent_difference 互為逆運算。如果對區間值 1,2,3,4,5 執行 partial_sum，結果為 1,3,6,10,15，在對此結果執行 adjacent_difference，獲得原始區間值 1,2,3,4,5。

感謝大家，我是假裝很努力的YoungYangD（小羊）。

參考資料：

《STL源碼剖析》