STL算法之merge合并算法 · STL源碼剖析

### 前言 ? 由于在前文的《[STL算法剖析](http://blog.csdn.net/chenhanzhun/article/details/39698523)》中，源碼剖析非常多，不方便學習，也不方便以后復習，這里把這些算法進行歸類，對他們單獨的源碼剖析進行講解。本文介紹的STL算法中的merge合并算法。源碼中介紹了函數merge、inplace_merge。并對這些函數的源碼進行詳細的剖析，并適當給出使用例子，具體詳見下面源碼剖析。 ### merge合并算法源碼剖析 ~~~ // merge, with and without an explicitly supplied comparison function. //將兩個已排序的區間[first1,last1)和區間[first2,last2)合并 /* 函數功能：Combines the elements in the sorted ranges [first1,last1) and [first2,last2), into a new range beginning at result with all its elements sorted. 函數原型： default (1) ：版本一 template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); custom (2) ：版本二 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); */ //版本一： template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, _LessThanComparable); //兩個序列都尚未到達尾端，則執行while循環 /* 情況1：若序列二元素較小,則記錄到目標區，且移動序列二的迭代器，但是序列一的迭代器不變. 情況2：若序列一元素較小或相等,則記錄到目標區，且移動序列一的迭代器，但是序列二的迭代器不變. 最后：把剩余元素的序列復制到目標區 */ while (__first1 != __last1 && __first2 != __last2) { //情況1 if (*__first2 < *__first1) {//若序列二元素較小 *__result = *__first2;//將元素記錄到目標區 ++__first2;//移動迭代器 } //情況2 else {//若序列一元素較小或相等 *__result = *__first1;//將元素記錄到目標區 ++__first1;//移動迭代器 } ++__result;//更新目標區位置，以便下次記錄數據 } //若有序列到達尾端，則把沒到達尾端的序列剩余元素復制到目標區 //此時，區間[first1,last1)和區間[first2,last2)至少一個必定為空 return copy(__first2, __last2, copy(__first1, __last1, __result)); } //版本二 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { __STL_REQUIRES(_InputIter1, _InputIterator); __STL_REQUIRES(_InputIter2, _InputIterator); __STL_REQUIRES_SAME_TYPE( typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter2>::value_type); __STL_REQUIRES(_OutputIter, _OutputIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_InputIter1>::value_type, typename iterator_traits<_InputIter1>::value_type); while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first2, *__first1)) { *__result = *__first2; ++__first2; } else { *__result = *__first1; ++__first1; } ++__result; } return copy(__first2, __last2, copy(__first1, __last1, __result)); } //merge函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::merge, std::sort #include <vector> // std::vector int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; std::vector<int> v(10); std::sort (first,first+5); std::sort (second,second+5); std::merge (first,first+5,second,second+5,v.begin()); std::cout << "The resulting vector contains:"; for (std::vector<int>::iterator it=v.begin(); it!=v.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output: The resulting vector contains: 5 10 10 15 20 20 25 30 40 50 */ // inplace_merge and its auxiliary functions. //版本一的輔助函數，無緩沖區的操作 template <class _BidirectionalIter, class _Distance> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2) { if (__len1 == 0 || __len2 == 0) return; if (__len1 + __len2 == 2) { if (*__middle < *__first) iter_swap(__first, __middle); return; } _BidirectionalIter __first_cut = __first; _BidirectionalIter __second_cut = __middle; _Distance __len11 = 0; _Distance __len22 = 0; if (__len1 > __len2) { __len11 = __len1 / 2; advance(__first_cut, __len11); __second_cut = lower_bound(__middle, __last, *__first_cut); distance(__middle, __second_cut, __len22); } else { __len22 = __len2 / 2; advance(__second_cut, __len22); __first_cut = upper_bound(__first, __middle, *__second_cut); distance(__first, __first_cut, __len11); } _BidirectionalIter __new_middle = rotate(__first_cut, __middle, __second_cut); __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22); __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, __len2 - __len22); } template <class _BidirectionalIter, class _Distance, class _Compare> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Compare __comp) { if (__len1 == 0 || __len2 == 0) return; if (__len1 + __len2 == 2) { if (__comp(*__middle, *__first)) iter_swap(__first, __middle); return; } _BidirectionalIter __first_cut = __first; _BidirectionalIter __second_cut = __middle; _Distance __len11 = 0; _Distance __len22 = 0; if (__len1 > __len2) { __len11 = __len1 / 2; advance(__first_cut, __len11); __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); distance(__middle, __second_cut, __len22); } else { __len22 = __len2 / 2; advance(__second_cut, __len22); __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); distance(__first, __first_cut, __len11); } _BidirectionalIter __new_middle = rotate(__first_cut, __middle, __second_cut); __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22, __comp); __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, __len2 - __len22, __comp); } //版本一的輔助函數，有緩沖區的操作 template <class _BidirectionalIter1, class _BidirectionalIter2, class _Distance> _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first, _BidirectionalIter1 __middle, _BidirectionalIter1 __last, _Distance __len1, _Distance __len2, _BidirectionalIter2 __buffer, _Distance __buffer_size) { _BidirectionalIter2 __buffer_end; if (__len1 > __len2 && __len2 <= __buffer_size) {//緩沖區足夠放置序列二 __buffer_end = copy(__middle, __last, __buffer); copy_backward(__first, __middle, __last); return copy(__buffer, __buffer_end, __first); } else if (__len1 <= __buffer_size) {//緩沖區足夠放置序列一 __buffer_end = copy(__first, __middle, __buffer); copy(__middle, __last, __first); return copy_backward(__buffer, __buffer_end, __last); } else//若緩沖區仍然不夠，則調用STL算法rotate，不使用緩沖區 return rotate(__first, __middle, __last); } template <class _BidirectionalIter1, class _BidirectionalIter2, class _BidirectionalIter3> _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, _BidirectionalIter3 __result) { if (__first1 == __last1) return copy_backward(__first2, __last2, __result); if (__first2 == __last2) return copy_backward(__first1, __last1, __result); --__last1; --__last2; while (true) { if (*__last2 < *__last1) { *--__result = *__last1; if (__first1 == __last1) return copy_backward(__first2, ++__last2, __result); --__last1; } else { *--__result = *__last2; if (__first2 == __last2) return copy_backward(__first1, ++__last1, __result); --__last2; } } } template <class _BidirectionalIter1, class _BidirectionalIter2, class _BidirectionalIter3, class _Compare> _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, _BidirectionalIter3 __result, _Compare __comp) { if (__first1 == __last1) return copy_backward(__first2, __last2, __result); if (__first2 == __last2) return copy_backward(__first1, __last1, __result); --__last1; --__last2; while (true) { if (__comp(*__last2, *__last1)) { *--__result = *__last1; if (__first1 == __last1) return copy_backward(__first2, ++__last2, __result); --__last1; } else { *--__result = *__last2; if (__first2 == __last2) return copy_backward(__first1, ++__last1, __result); --__last2; } } } //版本一的輔助函數，有緩沖區的操作 template <class _BidirectionalIter, class _Distance, class _Pointer> void __merge_adaptive(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size) { if (__len1 <= __len2 && __len1 <= __buffer_size) { //case1：把序列一放在緩沖區 _Pointer __buffer_end = copy(__first, __middle, __buffer); //直接調用歸并函數merge merge(__buffer, __buffer_end, __middle, __last, __first); } else if (__len2 <= __buffer_size) { //case2：把序列二放在緩沖區 _Pointer __buffer_end = copy(__middle, __last, __buffer); __merge_backward(__first, __middle, __buffer, __buffer_end, __last); } else {//case3：緩沖區不足放置任何一個序列 _BidirectionalIter __first_cut = __first; _BidirectionalIter __second_cut = __middle; _Distance __len11 = 0; _Distance __len22 = 0; if (__len1 > __len2) {//若序列一比較長 __len11 = __len1 / 2;//計算序列一的一半 advance(__first_cut, __len11);//讓first_cut指向序列一的中間位置 //找出*__first_cut在[middle,last)區間中的第一個不小于*__first_cut的元素位置 __second_cut = lower_bound(__middle, __last, *__first_cut); //計算middle到__second_cut之間的距離，保存在__len22 distance(__middle, __second_cut, __len22); } else {//若序列二比較長 __len22 = __len2 / 2;//計算序列二的一半 advance(__second_cut, __len22);//讓__second_cut指向序列二的中間位置 //找出*__second_cut在[first,middle)區間中的第一個大于*__second_cut的元素位置 __first_cut = upper_bound(__first, __middle, *__second_cut); //計算__first到__first_cut之間的距離，保存在__len11 distance(__first, __first_cut, __len11); } _BidirectionalIter __new_middle = __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, __len22, __buffer, __buffer_size); //對左半段遞歸調用 __merge_adaptive(__first, __first_cut, __new_middle, __len11, __len22, __buffer, __buffer_size); //對右半段遞歸調用 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, __len2 - __len22, __buffer, __buffer_size); } } template <class _BidirectionalIter, class _Distance, class _Pointer, class _Compare> void __merge_adaptive(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp) { if (__len1 <= __len2 && __len1 <= __buffer_size) { _Pointer __buffer_end = copy(__first, __middle, __buffer); merge(__buffer, __buffer_end, __middle, __last, __first, __comp); } else if (__len2 <= __buffer_size) { _Pointer __buffer_end = copy(__middle, __last, __buffer); __merge_backward(__first, __middle, __buffer, __buffer_end, __last, __comp); } else { _BidirectionalIter __first_cut = __first; _BidirectionalIter __second_cut = __middle; _Distance __len11 = 0; _Distance __len22 = 0; if (__len1 > __len2) { __len11 = __len1 / 2; advance(__first_cut, __len11); __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); distance(__middle, __second_cut, __len22); } else { __len22 = __len2 / 2; advance(__second_cut, __len22); __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); distance(__first, __first_cut, __len11); } _BidirectionalIter __new_middle = __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, __len22, __buffer, __buffer_size); __merge_adaptive(__first, __first_cut, __new_middle, __len11, __len22, __buffer, __buffer_size, __comp); __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, __len2 - __len22, __buffer, __buffer_size, __comp); } } //版本一的輔助函數 template <class _BidirectionalIter, class _Tp, class _Distance> inline void __inplace_merge_aux(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Tp*, _Distance*) { _Distance __len1 = 0; distance(__first, __middle, __len1);//計算序列一的長度 _Distance __len2 = 0; distance(__middle, __last, __len2);//計算序列二的長度 //使用暫時緩沖區 _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); if (__buf.begin() == 0)//若緩沖區配置失敗 //則調用不使用緩沖區的合并操作 __merge_without_buffer(__first, __middle, __last, __len1, __len2); else//若分配成功 //則調用具有緩沖區的合并操作 __merge_adaptive(__first, __middle, __last, __len1, __len2, __buf.begin(), _Distance(__buf.size())); } template <class _BidirectionalIter, class _Tp, class _Distance, class _Compare> inline void __inplace_merge_aux(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Tp*, _Distance*, _Compare __comp) { _Distance __len1 = 0; distance(__first, __middle, __len1); _Distance __len2 = 0; distance(__middle, __last, __len2); _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); if (__buf.begin() == 0) __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); else __merge_adaptive(__first, __middle, __last, __len1, __len2, __buf.begin(), _Distance(__buf.size()), __comp); } //將兩個已排序的序列[first,middle)和[middle,last)合并成單一有序序列. //若原來是增序，現在也是遞增排序，若原來是遞減排序，現在也是遞減排序 /* 函數功能：Merges two consecutive sorted ranges: [first,middle) and [middle,last), putting the result into the combined sorted range [first,last). 函數原型： default (1) ：版本一 template <class BidirectionalIterator> void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); custom (2) ：版本二 template <class BidirectionalIterator, class Compare> void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); */ //版本一 template <class _BidirectionalIter> inline void inplace_merge(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last) { __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, _LessThanComparable); if (__first == __middle || __middle == __last)//若有空序列，則之間返回 return; __inplace_merge_aux(__first, __middle, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } //版本二 template <class _BidirectionalIter, class _Compare> inline void inplace_merge(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Compare __comp) { __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool, typename iterator_traits<_BidirectionalIter>::value_type, typename iterator_traits<_BidirectionalIter>::value_type); if (__first == __middle || __middle == __last) return; __inplace_merge_aux(__first, __middle, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first), __comp); } //inplace_merge函數舉例： /* #include <iostream> // std::cout #include <algorithm> // std::inplace_merge, std::sort, std::copy #include <vector> // std::vector int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; std::vector<int> v(10); std::vector<int>::iterator it; std::sort (first,first+5); std::sort (second,second+5); it=std::copy (first, first+5, v.begin()); std::copy (second,second+5,it); std::inplace_merge (v.begin(),v.begin()+5,v.end()); std::cout << "The resulting vector contains:"; for (it=v.begin(); it!=v.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } Output： The resulting vector contains: 5 10 10 15 20 20 25 30 40 50 */ ~~~ 參考資料：《STL源碼剖析》侯捷