STL中的算法小結，STL算法小結
（1）要運用STL的算法，首先必須包含頭文件<algorithm>，某些STL算法用於數值處理，因此被定義於頭文件<numeric>
（2）所有STL算法都被設計用來處理一個或多個迭代器區間，第一個區間通常以起點和終點表示，至於其他區間，多數情況下你只需提供起點便足以，其終點可以自動以第一個區間的元素數量推斷出來，調用者必須保證這些區間的有效性。
STL算法采用覆蓋模式而非安插模式，所以調用者必須保證目標區間擁有足夠的元素空間，當然你也可以運用特殊的安插型迭代器將覆蓋模式改變為安插模式。
（3）尾詞_if：如果算法有兩種形式，參數個數都相同，但第一形式的參數要求傳遞一個值，第二形式的參數要求傳遞一個函數或仿函數，那麼尾詞_if就派上了用場，無尾詞的那個要求傳遞數值，有尾詞的那個要求傳遞函數或仿函數。不過並非所有“要求傳遞仿函數”的算法都有尾詞_if，如果算法以額外參數來接受這樣的函數或仿函數，那麼不同版本的算法就可以采用相同的命名。
尾詞_copy：這個尾詞用來表示在此算法中，元素不光被操作，還會被復制到目標區間。
（4）for_each()算法：
UnaryProc for_each (InputIterator beg, InputIterator end, UnaryProc op);
1對區間[beg, end)中的每一個元素調用op(elem)
2返回op（已在算法內部被變動過）的一個副本
3op的任何返回值都會被忽略
4op可以變動元素
5復雜度：線性
（5）元素計數算法：
difference_type count (InputIterator beg, InputIterator end, const T& value);
difference_type count_if (InputIterator beg, InputIterator end, UnaryPredicate op);
1第一形式會計算區間[beg, end)中的元素等於value的元素個數
2第二形式會計算區間[beg, end)中令以下一元判斷式結果為true的元素個數：op(elem)
3返回值型別為difference_type，是表現迭代器間距的型別
4注意op在函數調用過程中不應該改變自身狀態
5op不應該改動傳進來的參數
6關聯式容器（set/multiset，map/multimap）提供了一個等效的成員函數count()用來計算等於某個value或key的元素個數
7時間復雜度：線性
（6）最大最小值算法：
InputIterator min_element (InputIterator beg, InputIterator end);
InputIterator min_element (InputIterator beg, InputIterator end, CompFunc op);
InputIterator max_element (InputIterator beg, InputIterator end);
InputIterator max_element (InputIterator beg, InputIterator end, CompFunc op);
1所有這些算法都返回區間[beg, end)中的最大或最小值的位置
2上述無op參數版本以operator<進行元素比較
3op用來比較兩個元素：op(elem1, elem2)如果第一個元素小於第二個元素，應當返回true
4如果存在多個最大或最小值，上述算法返回找到的第一個最大或最小值
5op不應該改動傳進去的參數
6時間復雜度：線性
（7）搜尋元素算法：
InputIterator find (InputIterator beg, InputIterator end, const T& value);
InputIterator find_if (InputIterator beg, InputIterator end, UnaryPredicate op);
1第一形式返回區間[beg, end)中的第一個“元素值等於value”的元素位置
2第二形式返回區間[beg, end)中令一元判斷式op(elem)結果為true的第一個元素的位置
3如果沒有找到匹配元素，兩種形式都返回end
4注意op在函數調用過程中不應該改變自身狀態
5op不應該改動傳進來的參數
6如果是已序區間，應使用lower_bound()，upper_bound()，equal_range()或binary_search()算法以獲取更高的性能
7關聯式容器（set/multiset，map/multimap）提供了一個等效的成員函數find()，擁有對數時間復雜度
8時間復雜度：線性
InputIterator search_n (InputIterator beg, InputIterator end, Size count, const T& value);
InputIterator search_n (InputIterator beg, InputIterator end, Size count, const T& value, BinaryPredicate op);
1第一形式返回區間[beg, end)中的第一組“連續count個元素值全等於value”的元素位置
2第二形式返回區間[beg, end)中的第一組“連續count個元素使op(elem, value)結果為true”的元素位置
3如果沒有找到匹配元素，兩種形式都返回end
4注意op在函數調用過程中不應該改變自身狀態
5op不應該改動傳進來的參數
6時間復雜度：線性
ForwardIterator1 search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd);
ForwardIterator1 search (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op);
1兩種形式都返回區間[beg, end)內“和區間[searchBeg, searchEnd)完全吻合”的第一個子區間內的第一個元素位置
2第一形式中，子區間元素必須完全等於[searchBeg, searchEnd)的元素
3第二形式中，子區間元素和[searchBeg, searchEnd)的對應元素必須使op(elem, searchElem)結果為true
4如果沒有找到匹配子區間，兩種形式都返回end
5注意op在函數調用過程中不應該改變自身狀態
6op不應該改動傳進來的參數
7時間復雜度：線性
ForwardIterator find_end (ForwardIterator beg, ForwardIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd);
ForwardIterator find_end (ForwardIterator beg, ForwardIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd, BinaryPredicate op);
1兩種形式都返回區間[beg, end)內“和區間[searchBeg, searchEnd)完全吻合”的最後一個子區間內的第一個元素位置
2第一形式中，子區間元素必須完全等於[searchBeg, searchEnd)的元素
3第二形式中，子區間元素和[searchBeg, searchEnd)的對應元素必須使op(elem, searchElem)結果為true
4如果沒有找到匹配子區間，兩種形式都返回end
5注意op在函數調用過程中不應該改變自身狀態
6op不應該改動傳進來的參數
7時間復雜度：線性
ForwardIterator find_first_of (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd);
ForwardIterator find_first_of (ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op);
1第一形式返回第一個“既在區間[beg, end)中出現，也在區間[searchBeg, searchEnd)中出現”的元素位置
2第二形式返回區間[beg, end)中的第一個這樣的元素：他和區間[searchBeg, searchEnd)內的每一個元素進行op(elem, searchElem)結果都為ture
3如果沒有找到匹配元素，兩種形式都返回end
4注意op在函數調用過程中不應該改變自身狀態
5op不應該改動傳進來的參數
6你可以使用逆向迭代器來搜尋最後一個這樣的元素
7時間復雜度：線性
InputIterator adjacent_find (InputIterator beg, InputIterator end);
InputIterator adjacent_find (InputIterator beg, InputIterator end, BinaryPredicate op);
1第一形式返回區間[beg, end)中的第一對“連續兩個相等元素”之中的第一個元素位置
2第二形式返回區間[beg, end)中的第一對“連續兩個元素均使op(elem, nextElem)結果為true“的其中第一個元素位置
3如果沒有找到吻合元素，兩種形式都返回end
4注意op在函數調用過程中不應該改變自身狀態
5op不應該改動傳進來的參數
6時間復雜度：線性
bool equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg);
bool equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg, BinaryPredicate op);
1第一形式判斷區間[beg, end)內的元素是否都和以cmpBeg開頭的區間內的元素相等
2第二形式判斷區間[beg, end)內的元素和以cmpBeg開頭的區間內的對應元素是否都能使op(elem, cmpElem)結果為true
3調用者必須保證以cmpBeg開頭的區間具有足夠的元素
4當序列不相等時，如果想要了解其間的不同，應使用mismatch()算法
5注意op在函數調用過程中不應該改變自身狀態
6op不應該改動傳進來的參數
7時間復雜度：線性
pair<InputIterator1, InputIterator2> mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg);
pair<InputIterator1, InputIterator2> mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg, BinaryPredicate op);
1第一形式返回區間[beg, end)和以cmpBeg開頭的區間之中的第一組兩兩相異的對應元素
2第二形式返回區間[beg, end)和以cmpBeg開頭的區間之中的第一組”使op(elem, cmpElem)結果為false“的對應元素
3如果沒有找到相異點，就返回一個pair，以end和第二序列的對應元素組成。這並不意味著兩個序列相等，因為第二序列有可能包含更多的元素
4調用者必須保證以cmpBeg開頭的區間具有足夠的元素
5如果想要了解兩個序列是否相等，應使用equal()算法
6注意op在函數調用過程中不應該改變自身狀態
7op不應該改動傳進來的參數
8時間復雜度：線性
bool lexicographical_compare (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, InputIterator2 end2);
bool lexicographical_compare (InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, InputIterator2 end2, CompFunc op);
1兩種形式都用來判斷區間[beg1, end1)的元素是否小於區間[beg2, end2)的元素。所謂”小於“是指本著”字典次序“的意義
2第一形式使用operator<
3第二形式使用op(elem1, elem2)來判斷
4注意op在函數調用過程中不應該改變自身狀態
5op不應該改動傳進來的參數
6時間復雜度：線性
（8）復制元素算法：
OutputIterator copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg);
BidirectionalIterator1 copy_backward (BidirectionalIterator1 sourceBeg, BidirectionalIterator1 sourceEnd, BidirectionalIterator2 destEnd);
1這兩個算法都將源區間[sourceBeg, sourceEnd)中的所有元素復制到以destBeg為起點或以destEnd為終點的目標區間裡去
2返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
3destBeg或destEnd不可處於[sourceBeg, sourceEnd)區間內
4copy()正向遍歷序列，copy_backward()逆向遍歷序列
5STL沒有所謂的copy_if()算法，所以如果要復制符合某特定准則的元素，請使用remove_copy_if()算法
6如果希望在復制過程中逆轉元素次序，應該使用reverse_copy()
7調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
8如果想把容器內的所有元素賦值給另一容器，應當使用assignment操作符（當兩個容器的型別相同時）或者使用容器的assign()成員函數（當兩個容器的型別不同時）
9如果希望在復制過程中刪除某元素，請使用remove_copy()和remove_copy_if()算法
10如果希望在復制過程中改變元素，請使用transform()或replace_copy()算法
11時間復雜度：線性
（9）轉換元素算法：
OutputIterator transform (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryFunc op);
1針對源區間[sourceBeg, sourceEnd)中的每一個元素調用op(elem)並將結果寫到以destBeg為起點的目標區間
2返回目標區間內最後一個被轉換的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
3調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
4sourceBeg和destBeg可以相同，因此你可以使用這個算法來變動某一序列內的元素
5如果想以某值來替換符合某一標准的元素，應使用replace()算法
6時間復雜度：線性
OutputIterator transform (InputIterator1 source1Beg, InputIterator1 source1End, InputIterator2 source2Beg, OutputIterator destBeg, BinaryFunc op);
1針對第一個源區間[source1Beg, source1End)以及從source2Beg開始的第二個源區間的對應元素調用op(source1Elem, source2Elem)並將結果寫到以destBeg起始的目標區間
2返回目標區間內最後一個被轉換的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
3調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
4調用者必須保證第二源區間有足夠空間（至少擁有和第一源區間相同的空間大小）
5source1Beg，source2Beg，destBeg可以相同，因此你可以讓元素自己和自己結合然後將結果覆蓋至某個序列
6時間復雜度：線性
（10）互換元素內容算法：
ForwardIterator2 swap_ranges (ForwardIterator1 beg1, ForwardIterator1 end1, ForwardIterator2 beg2);
1將區間[beg1, end1)內的元素和從beg2開始的區間內的對應元素互換
2返回第二區間中的最後一個被交換元素的下一位置
3調用者必須保證目標區間有足夠空間
4兩區間不得重疊
5如果要將相同型別的兩個容器內的全部元素互換，應使用swap()成員函數這樣通常更快
6時間復雜度：線性
（11）賦值算法：
void fill (ForwardIterator beg, ForwardIterator end, const T& newValue);
void fill_n (OutputIterator beg, Size num, const T& newValue);
1fill()將區間[beg, end)內的每一個元素都賦予新值newValue
2fill_n()將從beg開始的前num個元素賦予新值newValue
3調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
4時間復雜度：線性
void generate (ForwardIterator beg, ForwardIterator end, Func op);
void generator_n (OutputIterator beg, Size num, Func op);
1generate()調用op產生新值並賦給區間[beg, end)內的每一個元素
2generate_n()調用op產生新值並賦給以beg開始的區間內的前num個元素
3調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
4時間復雜度：線性
（12）替換元素算法：
void replace (ForwardIterator beg, ForwardIterator end, const T& oldValue, const T& newValue);
void replace_if (ForwardIterator beg, ForwardIterator end, UnaryPredicate op, const T& newValuedValue);
1replace()將區間[beg, end)內每一個與oldValue相等的元素替換為newValue
2replace_if()將區間[beg ,end)內每一個令op(elem)為true的元素替換為newValue
3op不應該在函數調用過程中改變自身狀態
4時間復雜度：線性
OutputIterator replace_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, const T& oldValue, const T& newValue);
OutputIterator replace_copy_if (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryPredicate op, const T& newValue);
1replace_copy()是copy()和replace()的組合，它將源區間[sourceBeg, sourceEnd)內的元素復制到以destBeg開始的目標區間去，同時將與oldValue相等的所有元素替換成newValue
2replace_copy_if()是copy()和replace_if()的組合，它將源區間[sourceBeg, sourceEnd)內的元素復制到以destBeg開始的目標區間去，同時將令op(elem)結果為true的所有元素替換成newValue
3倆個算法都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
4op不應該在函數調用過程中改變自身狀態
5時間復雜度：線性
（13）移除性算法：
ForwardIterator remove (ForwardIterator beg, ForwardIterator end, const T& value);
ForwardIterator remove_if (ForwardIterator beg, ForwardIterator end, UnaryPredicate op);
1remove()會移除區間[beg, end)中的每一個與value相等的元素
2remove_if()會移除區間[beg, end)中的每一個令op(elem)結果為true的元素
3兩個算法都會返回變動後的序列的新邏輯終點（也就是最後一個未被移除元素的下一個位置）
4這些算法會把原來置於後面的未被移除元素向前移動，覆蓋被移除元素
5未被移除元素在相對次序上保持不變
6調用者在調用此算法後，應保證從此采用返回的新邏輯終點而不再使用原始終點end
7op不應該在函數調用過程中改變自身狀態
8由於會發生元素變動，所以這些算法不可用於關聯式容器，關聯式容器提供了功能相似的成員函數erase()
9list提供了一個等效成員函數remove()：不是重新賦值元素，而是重新安排指針
10時間復雜度：線性
OutputIterator remove_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, const T& value);
OutputIterator remove_copy_if (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, UnaryPredicate op);
1remove_copy()是copy()和remove()的組合，它將源區間[sourceBeg, sourceEnd)內的元素復制到以destBeg開始的目標區間去，同時移除與value相等的所有元素
2remove_copy_if()是copy()和remove_if()的組合，它將源區間[sourceBeg, sourceEnd)內的元素復制到以destBeg開始的目標區間去，同時移除令op(elem)結果為true的所有元素
3倆個算法都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
4op不應該在函數調用過程中改變自身狀態
5調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
6時間復雜度：線性
ForwardIterator unique (ForwardIterator beg, ForwardIterator end);
ForwardIterator unique (ForwardIterator beg, ForwardIterator end, BinaryPredicate op);
1兩個算法都會移除連續重復元素中的多余元素
2第一形式將區間[beg, end)內的所有與前一個元素相等的元素移除，所以源區間必須先經過排序，才能使用這個算法
3第二形式將每一個“位於元素e之後並且造成op(elem ,e)結果為true”的所有elem元素移除，換言之此op並非用來將元素和其原本的前一元素比較，而是將它和未被移除的前一元素比較
4兩種形式都返回被變動後的序列的新終點（最後一個未被移除的元素的下一個位置）
5兩個算法將原本位置在後的未被移除元素向前移動，覆蓋被移除元素
6未被移除元素在相對次序上保持不變
7調用者在調用此算法後，應保證從此采用返回的新邏輯終點而不再使用原始終點end
8op不應該在函數調用過程中改變自身狀態
9由於會發生元素變動，所以這些算法不可用於關聯式容器
10list提供了一個等效成員函數unique()：不是重新賦值元素，而是重新安排指針
11時間復雜度：線性
OutputIterator unique_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg);
OutputIterator unique_copy (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryPredicate op);
1兩種形式都是copy()和unique()的組合
2兩者都將源區間[sourceBeg, sourceEnd)內的元素復制到以destBeg開始的目標區間去，並移除重復元素
3倆個算法都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
4調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
5時間復雜度：線性
（14）變序性算法：
void reverse (BidirectionalIterator beg, BidirectionalIterator end);
OutputIterator reverse_copy (BidirectionalIterator sourceBeg, BidirectionalIterator sourceEnd, OutputIterator destBeg);
1reverse()將區間[beg, end)內的元素全部逆序
2reverse_copy()會將源區間[sourceBeg, sourceEnd)內的元素復制到以destBeg起始的目標區間，並在復制過程中顛倒安置次序
3reverse_copy()返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
4調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
5list提供了一個等效成員函數reverse()：不是重新賦值元素，而是重新安排指針
6時間復雜度：線性
void rotate (ForwardIterator beg, ForwardIterator newBeg, ForwardIterator end);
1將區間[beg, end)內的元素進行旋轉，執行後*newBeg成為新的第一元素
2調用者必須保證newBeg是區間[beg, end)內的一個有效位置，否則會引發未定義的行為
3時間復雜度：線性
void rotate_copy (ForwardIterator sourceBeg, ForwardIterator newBeg, ForwardIterator sourceEnd, OutputIterator destBeg);
1這是rotate()和copy()的組合
2將源區間[sourceBeg, sourceEnd)內的元素復制到以destBeg起始的目標區間中，同時旋轉元素使*newBeg成為新的第一元素
3返回目標區間內最後一個被復制的元素的下一個位置
4調用者必須保證newBeg是區間[sourceBeg, sourceEnd)內的一個有效位置，否則會引發未定義的行為
5調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
6源區間和目標區間不可重疊
7時間復雜度：線性
bool next_permutation (BidirectionalIterator beg, BidirectionalIterator end);
bool prev_permutation (BidirectionalIterator beg, BidirectionalIterator end);
1next_permutation()會改變區間[beg, end)內的元素次序，使它符合“下一個排列次序”
2prev_permutation()會改變區間[beg, end)內的元素次序，使它符合“上一個排列次序”
3如果元素得以排列成“正規”次序，則兩個算法都返回true。所謂正規次序，對next_permutation()而言為升序，對prev_permutation()而言為降序。因此如果要走遍所有排序，你必須先將所有元素（按升序或降序）排序，然後開始以循環方式調用prev_permutation()或next_permutation()直到算法返回false
4時間復雜度：線性
void random_shuffle (RandomAccessIterator beg, RandomAccessIterator end);
void random_shuffle (RandomAccessIterator beg, RandomAccessIterator end, RandomFunc& op);
1第一形式使用一個均勻分布隨機數產生器來打亂區間[beg, end)內的元素次序
2第二形式使用op來打亂區間[beg, end)內的元素次序。算法內部會使用一個整數值來調用op：op(max)，它應該返回一個大於零而小於max的隨機數但不包括max自身
3注意op是一個non-const reference，所有你不可以將暫時數值或一般函數傳進去
4時間復雜度：線性
BidirectionalIterator partition (BidirectionalIterator beg, BidirectionalIterator end, UnaryPredicate op);
BidirectionalIterator stable_partition (BidirectionalIterator beg, BidirectionalIterator end, UnaryPredicate op);
1兩種算法將區間[beg, end)中的“造成op(elem)結果為true”的元素向前端移動
2兩種算法都返回“令op(elem)結果為false”的第一個元素位置
3兩者差別為無論元素是否符合給定的准則，stable_partition()會保持它們之間的相對次序
4你可以運用此算法根據排序准則將所有元素分割為兩部分，nth_element()具有類似能力
5op不應該在函數調用中改變自身狀態
6時間復雜度：partition()為線性，stable_partition()當系統有足夠的內存時為線性、不足時為O(nlgn)
（15）排序算法：
void sort (RandomAccessIterator beg, RandomAccessIterator end);
void sort (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op);
void stable_sort (RandomAccessIterator beg, RandomAccessIterator end);
void stable_sort (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op);
1sort()和stable_sort()的上述第一形式使用operator<對區間[beg, end)內的所有元素進行排序
2sort()和stable_sort()的上述第二形式使用op(elem1, elem2)作為排序准則對區間[beg, end)內的所有元素進行排序
3op不應該在函數調用中改變自身狀態
4sort()和stable_sort()的區別是後者保證相等元素的原本相對次序在排序後保持不變
5不可以對list調用這些算法，因為list不支持隨機存取迭代器不過list提供了一個成員函數sort()
6時間復雜度：sort()：O(nlgn)，stable_sort()當系統有足夠的內存時為O(nlgn)、不足時為O(nlgn*lgn)
void partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end);
void partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd, RandomAccessIterator end, BinaryPredicate op);
1上述第一形式使用operator<對區間[beg, end)內的所有元素進行排序，使區間[beg, sortEnd)內的元素處於有序狀態
2上述第二形式使用op(elem1, elem2)作為排序准則對區間[beg, end)內的所有元素進行排序，使區間[beg, sortEnd)內的元素處於有序狀態
3op不應該在函數調用中改變自身狀態
4和sort()不同的是partial_sort()並不對全部元素進行排序：一旦第一個元素直至sortEnd之間的所有元素都排好次序就立刻停止，不會對剩余的元素進行排序
5如果end和sortEnd相等，那麼partial_sort()會對整個序列進行排序，平均而言其效率不及sort()，不過最差情況而言優於sort()
6時間復雜度：線性和O(nlgn)之間
RandomAccessIterator partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd, RandomAccessIterator destBeg, RandomAccessIterator destEnd);
RandomAccessIterator partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd, RandomAccessIterator destBeg, RandomAccessIterator destEnd, BinaryPredicate op);
1兩者都是copy()和partial_sort()的組合
2它們將元素從源區間[sourceBeg, sourceEnd)復制到目標區間[destBeg, destEnd)同時排序
3被排序元素的數量是源區間和目標區間兩者所含元素數量的最小值
4兩者都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
5時間復雜度：線性和O(nlgn)之間
void nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end);
void nth_element (RandomAccessIterator beg, RandomAccessIterator nth, RandomAccessIterator end, BinaryPredicate op);
1兩種形式都對區間[beg, end)內的元素進行排序，使第n個位置上的元素就位，也就是說所有在位置n之前的元素小於等於它，所有位置在n之後的元素都大於等於它。這樣你就得到了根據n位置上的元素分割開來的兩個子序列，第一子序列的元素統統小於第二子序列的元素。如果你只需要n個最大或最小的元素，但不要求它們必須已序，那麼這個算法就很有用。
2上述第一形式使用operator<作為排序准則
3上述第二形式使用op(elem1, elem2)作為排序准則
4op不應該在函數調用中改變自身狀態
5時間復雜度：線性
（16）Heap算法：
void make_heap (RandomAccessIterator beg, RandomAccessIterator end);
void make_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op);
1兩種形式都將[beg, end)內的元素轉化為heap
2第二形式將op(elem1, elem2)視為排序准則
3只有在多於一個元素的情況下才有必要使用這些函數來處理heap
4時間復雜度：線性
void push_heap (RandomAccessIterator beg, RandomAccessIterator end);
void push_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op);
1兩種形式都將end之前的最後一個元素加入原本就是個heap的[beg, end-1)區間內使整個區間[beg, end)成為一個heap
2第二形式將op(elem1, elem2)視為排序准則
3調用者必須保證進入函數時，區間[beg, end-1)內的元素原本已形成一個heap，而新元素緊跟其後
4時間復雜度：對數
void pop_heap (RandomAccessIterator beg, RandomAccessIterator end);
void pop_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op);
1以上兩種形式都將heap[beg, end)內的最高元素也就是第一個元素移動到最後的位置上，並將剩余區間[beg, end-1)內的元素組織起來成為一個新heap
2第二形式將op(elem1, elem2)視為排序准則
3調用者必須保證進入函數時，區間[beg, end)內的元素原本已形成一個heap，而新元素緊跟其後
4時間復雜度：對數
void sort_heap (RandomAccessIterator beg, RandomAccessIterator end);
void sort_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op);
1以上兩種形式都將heap[beg, end)轉換為一個已序序列
2第二形式將op(elem1, elem2)視為排序准則
3此算法一結束，該區間就不再是個heap了
4調用者必須保證進入函數時，區間[beg, end)內的元素原本已形成一個heap，而新元素緊跟其後
5時間復雜度：對數
（17）搜尋元素：
bool binary_search (ForwardIterator beg, ForwardIterator end, const T& value);
bool binary_search (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op);
1兩種形式都用來判斷已序區間[beg, end)中是否含有和value等值的元素
2第二形式將op(elem1, elem2)視為排序准則
3如果想獲得被搜尋元素的位置，應使用lower_bound()，upper_bound()或equal_range()算法
4調用者必須保證進入算法之際該區間已序
5時間復雜度：如果搭配隨機存取迭代器則為對數復雜度，否則為線性
bool includes (InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg, InputIterator2 searchEnd);
bool includes (InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg, InputIterator2 searchEnd, BinaryPredicate op);
1兩種形式都用來判斷已序區間[beg, end)是否包含另一個已序區間[searchBeg, searchEnd)中的每一個元素。也就是說對於[searchBeg, searchEnd)中的每一個元素，如果[beg, end)必有一個對應的相等元素那麼[searchBeg, searchEnd)肯定是[beg, end)的子集
2第二形式將op(elem1, elem2)視為排序准則
3調用者必須保證在進入算法之際兩區間都應該已經按照相同的排序准則排好序了
4時間復雜度：線性
ForwardIterator lower_bound (ForwardIterator beg, ForwardIterator end, const T& value);
ForwardIterator lower_bound (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op);
ForwardIterator upper_bound (ForwardIterator beg, ForwardIterator end, const T& value);
ForwardIterator upper_bound (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op);
1lower_bound()返回第一個“大於等於value”的元素位置，這是可插入“元素值為value”且“不破壞區間[beg, end)已序性”的第一個位置
2upper_bound()返回第一個“大於value”的元素位置，這是可插入“元素值為value”且“不破壞區間[beg, end)已序性”的最後一個位置
3如果不存在其值為value的元素，上述算法都返回end
4op(elem1, elem2)視為排序准則
5調用者必須保證在進入算法之際所有區間都應該已經按照排序准則排好序了
6如果要同時獲得lower_bound()和upper_bound()的結果，請使用equal_range()
7關聯式容器分別提供等效成員函數，性能更好
8時間復雜度：如果搭配隨機存取迭代器則為對數復雜度，否則為線性
pair<ForwardIterator, ForwardIterator> equal_range (ForwardIterator beg, ForwardIterator end, const T& value);
pair<ForwardIterator, ForwardIterator> equal_range (ForwardIterator beg, ForwardIterator end, const T& value, BinaryPredicate op);
1兩種形式都返回與value相等的元素所形成的區間，在此區間內插入其值為value的元素並不會破壞區間[beg, end)的已序性
2和下式等效：make_pair(lower_bound(……), upper_bound(……))
3第二形式將op(elem1, elem2)視為排序准則
4調用者必須保證在進入算法之際兩區間都應該已經按照相同的排序准則排好序了
5關聯式容器分別提供等效成員函數，性能更好
6時間復雜度：如果搭配隨機存取迭代器則為對數復雜度，否則為線性
（18）合並元素：
OutputIterator merge (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg);
OutputIterator merge (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op);
1兩者都將源區間[source1Beg, source1End)和[source2Beg, source2End)內的元素合並，使得以destBeg起始的目標區間內含兩個源區間的所有元素
2目標區間內的所有元素都將按順序排列
3兩者都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
4第二形式將op(elem1, elem2)視為排序准則
5源區間沒有任何變化
6調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
7list提供了一個等效成員函數merge()
8根據標准調用者應當確保兩個源區間一開始都是已序，然而在大部分實作版本中上述算法可以將兩個無序的源區間內的元素合並到一個無序的目標區間中，不過要考慮到這樣的移植性
9目標區間和源區間不得重疊
10如果你要確保兩個源區間中都存在的元素在目標區間中只出現一次，請使用set_union()
11如果你要獲得同時存在於兩個源區間的所有元素，請使用set_intersection()
12時間復雜度：線性
OutputIterator set_union (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg);
OutputIterator set_union (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op);
1兩者都將源區間[source1Beg, source1End)和[source2Beg, source2End)內的元素合並，得到以destBeg起始的目標區間——這個區間內含的元素要不來自第一源區間，要不就來自第二源區間，或是同時來自兩個區間
2同時出現於兩個源區間內的元素在並集區間中將只出現一次。不過如果原來的某個源區間內原本就存在重復元素，則目標區間也會有重復元素，重復的個數是兩個源區間內的重復個數的較大值
3兩者都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
4第二形式將op(elem1, elem2)視為排序准則
5源區間沒有任何變化
6調用者應當確保兩個源區間一開始都是已序
7調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
8目標區間和源區間不得重疊
9若想得到兩個源區間的全部元素，應使用merge()
10時間復雜度：線性
11目標區間內的所有元素都按順序排列
OutputIterator set_intersection (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg);
OutputIterator set_intersection (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op);
1兩者都將源區間[source1Beg, source1End)和[source2Beg, source2End)內的元素合並，得到以destBeg起始的目標區間——這個區間內含的元素不但存在於第一源區間，也存在於第二源區間
2如果原來的某個源區間內原本就存在重復元素，則目標區間也會有重復元素，重復的個數是兩個源區間內的重復個數的較小值
3兩者都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
4第二形式將op(elem1, elem2)視為排序准則
5源區間沒有任何變化
6調用者應當確保兩個源區間一開始都是已序
7調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
8目標區間和源區間不得重疊
9目標區間內的所有元素都按順序排列
10時間復雜度：線性
OutputIterator set_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg);
OutputIterator set_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op);
1兩者都將源區間[source1Beg, source1End)和[source2Beg, source2End)內的元素合並，得到以destBeg起始的目標區間——這個區間內含的元素只存在於第一源區間，不存在於第二源區間
2目標區間內的所有元素都按順序排列
3如果原來的某個源區間內原本就存在重復元素，則目標區間也會有重復元素，重復的個數是第一源區間內的重復個數減去第二源區間內的相應重復個數，如果第二源區間內的重復個數大於第一源區間內的相應重復個數，則目標區間內的對應重復個數將會是零
4兩者都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
5第二形式將op(elem1, elem2)視為排序准則
6源區間沒有任何變化
7調用者應當確保兩個源區間一開始都是已序
8調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
9目標區間和源區間不得重疊
10時間復雜度：線性
OutputIterator set_symmetric_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg);
OutputIterator set_symmetric_difference (InputIterator source1Beg, InputIterator source1End, InputIterator source2Beg, InputIterator source2End, OutputIterator destBeg, BinaryPredicate op);
1兩者都將源區間[source1Beg, source1End)和[source2Beg, source2End)內的元素合並，得到以destBeg起始的目標區間——這個區間內含的元素或存在於第一源區間，或存在於第二源區間，但不同時存在於兩個源區間
2目標區間內的所有元素都按順序排列
3如果原來的某個源區間內原本就存在重復元素，則目標區間也會有重復元素，重復的個數是兩個源區間內的對應重復元素的個數差值
4兩者都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
5第二形式將op(elem1, elem2)視為排序准則
6源區間沒有任何變化
7調用者應當確保兩個源區間一開始都是已序
8調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
9目標區間和源區間不得重疊
10時間復雜度：線性
void inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, BidirectionalIterator end2);
void inplace_merge (BidirectionalIterator beg1, BidirectionalIterator end1beg2, BidirectionalIterator end2, BinaryPredicate op);
1兩者都是將已源區間[beg1, end1beg2)和[end1beg2, end2)的元素合並，使區間[beg1, end2)成為兩者之總和（且形成已序）
2時間復雜度：內存足夠為線性否則為O(nlgn)
（19）數值算法：
運用數值算法需要包含頭文件：#include<numeric>
T accumulate (InputIterator beg, InputIterator end, T initValue);
T accumulate (InputIterator beg, InputIterator end, T initValue, BinaryFunc op);
1第一形式計算initValue和區間[beg, end)內的所有元素總和，具體地說它針對每一個元素調用initValue+=elem
2第二形式計算initValue和區間[beg, end)內每一個元素進行op運算的結果，具體地說它針對每一個元素調用initValue=op(initValue, elem)
3如果序列為空則兩者都返回initValue
4時間復雜度：線性
T inner_product (InputIterator1 beg1, InputIterator1 end1,InputIterator2 beg2, T initValue);
T inner_product (InputIterator1 beg1, InputIterator1 end1,InputIterator2 beg2, T initValue, BinaryFunc op1, BinaryFunc op2);
1第一形式計算並返回[beg1, end1)區間和以beg2為起始的區間的對應元素組（再加上initValue）的內積。具體地說針對兩區間內的每一組對應元素調用initValue=initValue+elem1*elem2
2第二形式將[beg1, end1)區間和以beg2為起始的區間的對應元素組進行op2運算再和initValue進行op1運算並將結果返回。具體地說針對兩區間內的每一組對應元素調用initValue=op1(initValue, op2(elem1, elem2))
3如果第一區間為空則兩者都返回initValue
4調用者必須保證以beg2為起始的區間內含足夠元素空間
5op1和op2都不得變動其參數內容
6時間復雜度：線性
OutputIterator partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg);
OutputIterator partial_sum (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryFunc op);
1第一形式計算源區間[sourceBeg, sourceEnd)中的每個元素的部分和，然後將結果寫入以destBeg為起始的區間
2第二形式計算源區間[sourceBeg, sourceEnd)中的每個元素和其先前所有元素進行op運算，然後將結果寫入以destBeg為起始的區間
3對於數列a1 a2 a3 ……它們分別計算a1, a1+a2, a1+a2+a3,……和a1, a1 op a2, a1 op a2 op a3,……
4 兩者都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
5第一形式相當於把一個相對值序列轉換為一個絕對值序列，就此而言partial_sum()正好和adjacent_difference()互補
6源區間和目標區間可以相同
7調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
8op不得變動其參數內容
9時間復雜度：線性
OutputIterator adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg);
OutputIterator adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd, OutputIterator destBeg, BinaryFunc op);
1第一形式計算源區間[sourceBeg, sourceEnd)中的每個元素和其緊鄰前驅元素的差值，然後將結果寫入以destBeg為起始的區間
2第二形式計算源區間[sourceBeg, sourceEnd)中的每個元素和其緊鄰前驅元素進行op運算，然後將結果寫入以destBeg為起始的區間
3第一個元素只是被很單純的加以復制
4對於數列a1 a2 a3 a4……它們分別計算a1, a2-a1, a3-a2,a4-a3, ……和a1, a2 op a1, a3 op a2, a4 op a3,……
5 兩者都返回目標區間內最後一個被復制的元素的下一個位置，也就是第一個未被覆蓋的元素的位置
6第一形式相當於把一個絕對值序列轉換為一個相對值序列，就此而言partial_sum()正好和adjacent_difference()互補
7源區間和目標區間可以相同
8調用者必須保證目標區間有足夠的空間，否則就得使用insert迭代器
9op不得變動其參數內容
10時間復雜度：線性
