STLソース解析——STLアルゴリズムのmerge統合アルゴリズム
18979 ワード
前言
前の文の「STLアルゴリズム解析」では、ソースの解析が非常に多く、勉強にも不便で、後で復習するにも不便です.ここではこれらのアルゴリズムを分類し、独自のソースコードの解析を解説します.本論文で紹介したSTLアルゴリズムにおけるmerge結合アルゴリズム.ソースコードには関数merge、inplace_が紹介されています.mergeこれらの関数のソースコードを詳細に分析し、適切に使用例を示し、詳細は次のソースコードの分析を参照してください.
マージアルゴリズムのソースコード解析
《STLソース解析》侯捷
前の文の「STLアルゴリズム解析」では、ソースの解析が非常に多く、勉強にも不便で、後で復習するにも不便です.ここではこれらのアルゴリズムを分類し、独自のソースコードの解析を解説します.本論文で紹介したSTLアルゴリズムにおけるmerge結合アルゴリズム.ソースコードには関数merge、inplace_が紹介されています.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
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
custom (2) ：
template
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
*/
// ：
template
_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
_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 // std::cout
#include // std::merge, std::sort
#include // std::vector
int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector 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::iterator it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '
';
return 0;
}
Output:
The resulting vector contains: 5 10 10 15 20 20 25 30 40 50
*/
// inplace_merge and its auxiliary functions.
// ，
template
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
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
_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
_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
_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
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
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
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
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
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last);
custom (2) ：
template
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
*/
//
template
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
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 // std::cout
#include // std::inplace_merge, std::sort, std::copy
#include // std::vector
int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector v(10);
std::vector::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 << '
';
return 0;
}
Output：
The resulting vector contains: 5 10 10 15 20 20 25 30 40 50
*/ 《STLソース解析》侯捷