STL源码剖析——STL算法之merge合并算法

末蓝、 2022-08-12 19:29 432阅读 0赞

前言

由于在前文的《STL算法剖析》中，源码剖析非常多，不方便学习，也不方便以后复习，这里把这些算法进行归类，对他们单独的源码剖析进行讲解。本文介绍的STL算法中的merge合并算法。源码中介绍了函数merge、inplace_merge。并对这些函数的源码进行详细的剖析，并适当给出使用例子，具体详见下面源码剖析。

merge合并算法源码剖析

  1. // merge, with and without an explicitly supplied comparison function.
  2. //将两个已排序的区间[first1,last1)和区间[first2,last2)合并
  3. /*
  4. 函数功能：Combines the elements in the sorted ranges [first1,last1) and [first2,last2), 
  5. into a new range beginning at result with all its elements sorted.
  7. 函数原型：
  8. default (1)    ：版本一
  9.     template <class InputIterator1, class InputIterator2, class OutputIterator>
  10.     OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
  11.                         InputIterator2 first2, InputIterator2 last2,
  12.                         OutputIterator result);
  13. custom (2)    ：版本二
  14.     template <class InputIterator1, class InputIterator2,
  15.           class OutputIterator, class Compare>
  16.     OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
  17.                         InputIterator2 first2, InputIterator2 last2,
  18.                         OutputIterator result, Compare comp);
  19. */
  20. //版本一：
  21. template <class _InputIter1, class _InputIter2, class _OutputIter>
  22. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  23.                   _InputIter2 __first2, _InputIter2 __last2,
  24.                   _OutputIter __result) {
  25.   __STL_REQUIRES(_InputIter1, _InputIterator);
  26.   __STL_REQUIRES(_InputIter2, _InputIterator);
  27.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  28.   __STL_REQUIRES_SAME_TYPE(
  29.           typename iterator_traits<_InputIter1>::value_type,
  30.           typename iterator_traits<_InputIter2>::value_type);
  31.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  32.                  _LessThanComparable);
  33.   //两个序列都尚未到达尾端，则执行while循环
  34.   /*
  35.   情况1：若序列二元素较小,则记录到目标区，且移动序列二的迭代器，但是序列一的迭代器不变.
  36.   情况2：若序列一元素较小或相等,则记录到目标区，且移动序列一的迭代器，但是序列二的迭代器不变.
  37.   最后：把剩余元素的序列复制到目标区
  38.   */
  39.   while (__first1 != __last1 && __first2 != __last2) {
  40.       //情况1
  41.     if (*__first2 < *__first1) {//若序列二元素较小
  42.       *__result = *__first2;//将元素记录到目标区
  43.       ++__first2;//移动迭代器
  44.     }
  45.     //情况2
  46.     else {//若序列一元素较小或相等
  47.       *__result = *__first1;//将元素记录到目标区
  48.       ++__first1;//移动迭代器
  49.     }
  50.     ++__result;//更新目标区位置，以便下次记录数据
  51.   }
  52.   //若有序列到达尾端，则把没到达尾端的序列剩余元素复制到目标区
  53.   //此时，区间[first1,last1)和区间[first2,last2)至少一个必定为空
  54.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  55. }
  56. //版本二
  57. template <class _InputIter1, class _InputIter2, class _OutputIter,
  58.           class _Compare>
  59. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  60.                   _InputIter2 __first2, _InputIter2 __last2,
  61.                   _OutputIter __result, _Compare __comp) {
  62.   __STL_REQUIRES(_InputIter1, _InputIterator);
  63.   __STL_REQUIRES(_InputIter2, _InputIterator);
  64.   __STL_REQUIRES_SAME_TYPE(
  65.           typename iterator_traits<_InputIter1>::value_type,
  66.           typename iterator_traits<_InputIter2>::value_type);
  67.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  68.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  69.           typename iterator_traits<_InputIter1>::value_type,
  70.           typename iterator_traits<_InputIter1>::value_type);
  71.   while (__first1 != __last1 && __first2 != __last2) {
  72.     if (__comp(*__first2, *__first1)) {
  73.       *__result = *__first2;
  74.       ++__first2;
  75.     }
  76.     else {
  77.       *__result = *__first1;
  78.       ++__first1;
  79.     }
  80.     ++__result;
  81.   }
  82.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  83. }
  84. //merge函数举例：
  85. /*
  86.     #include <iostream>     // std::cout
  87.     #include <algorithm>    // std::merge, std::sort
  88.     #include <vector>       // std::vector
  90.     int main () {
  91.       int first[] = {5,10,15,20,25};
  92.       int second[] = {50,40,30,20,10};
  93.       std::vector<int> v(10);
  95.       std::sort (first,first+5);
  96.       std::sort (second,second+5);
  97.       std::merge (first,first+5,second,second+5,v.begin());
  99.       std::cout << "The resulting vector contains:";
  100.       for (std::vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
  101.         std::cout << ' ' << *it;
  102.       std::cout << '\n';
  104.       return 0;
  105.     }
  106.     Output:
  107.     The resulting vector contains: 5 10 10 15 20 20 25 30 40 50
  108. */
  110. // inplace_merge and its auxiliary functions. 
  111. //版本一的辅助函数，无缓冲区的操作
  112. template <class _BidirectionalIter, class _Distance>
  113. void __merge_without_buffer(_BidirectionalIter __first,
  114.                             _BidirectionalIter __middle,
  115.                             _BidirectionalIter __last,
  116.                             _Distance __len1, _Distance __len2) {
  117.   if (__len1 == 0 || __len2 == 0)
  118.     return;
  119.   if (__len1 + __len2 == 2) {
  120.     if (*__middle < *__first)
  121.       iter_swap(__first, __middle);
  122.     return;
  123.   }
  124.   _BidirectionalIter __first_cut = __first;
  125.   _BidirectionalIter __second_cut = __middle;
  126.   _Distance __len11 = 0;
  127.   _Distance __len22 = 0;
  128.   if (__len1 > __len2) {
  129.     __len11 = __len1 / 2;
  130.     advance(__first_cut, __len11);
  131.     __second_cut = lower_bound(__middle, __last, *__first_cut);
  132.     distance(__middle, __second_cut, __len22);
  133.   }
  134.   else {
  135.     __len22 = __len2 / 2;
  136.     advance(__second_cut, __len22);
  137.     __first_cut = upper_bound(__first, __middle, *__second_cut);
  138.     distance(__first, __first_cut, __len11);
  139.   }
  140.   _BidirectionalIter __new_middle
  141.     = rotate(__first_cut, __middle, __second_cut);
  142.   __merge_without_buffer(__first, __first_cut, __new_middle,
  143.                          __len11, __len22);
  144.   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
  145.                          __len2 - __len22);
  146. }
  148. template <class _BidirectionalIter, class _Distance, class _Compare>
  149. void __merge_without_buffer(_BidirectionalIter __first,
  150.                             _BidirectionalIter __middle,
  151.                             _BidirectionalIter __last,
  152.                             _Distance __len1, _Distance __len2,
  153.                             _Compare __comp) {
  154.   if (__len1 == 0 || __len2 == 0)
  155.     return;
  156.   if (__len1 + __len2 == 2) {
  157.     if (__comp(*__middle, *__first))
  158.       iter_swap(__first, __middle);
  159.     return;
  160.   }
  161.   _BidirectionalIter __first_cut = __first;
  162.   _BidirectionalIter __second_cut = __middle;
  163.   _Distance __len11 = 0;
  164.   _Distance __len22 = 0;
  165.   if (__len1 > __len2) {
  166.     __len11 = __len1 / 2;
  167.     advance(__first_cut, __len11);
  168.     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  169.     distance(__middle, __second_cut, __len22);
  170.   }
  171.   else {
  172.     __len22 = __len2 / 2;
  173.     advance(__second_cut, __len22);
  174.     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  175.     distance(__first, __first_cut, __len11);
  176.   }
  177.   _BidirectionalIter __new_middle
  178.     = rotate(__first_cut, __middle, __second_cut);
  179.   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
  180.                          __comp);
  181.   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
  182.                          __len2 - __len22, __comp);
  183. }
  184. //版本一的辅助函数，有缓冲区的操作
  185. template <class _BidirectionalIter1, class _BidirectionalIter2,
  186.           class _Distance>
  187. _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
  188.                                       _BidirectionalIter1 __middle,
  189.                                       _BidirectionalIter1 __last,
  190.                                       _Distance __len1, _Distance __len2,
  191.                                       _BidirectionalIter2 __buffer,
  192.                                       _Distance __buffer_size) {
  193.   _BidirectionalIter2 __buffer_end;
  194.   if (__len1 > __len2 && __len2 <= __buffer_size) {//缓冲区足够放置序列二
  195.     __buffer_end = copy(__middle, __last, __buffer);
  196.     copy_backward(__first, __middle, __last);
  197.     return copy(__buffer, __buffer_end, __first);
  198.   }
  199.   else if (__len1 <= __buffer_size) {//缓冲区足够放置序列一
  200.     __buffer_end = copy(__first, __middle, __buffer);
  201.     copy(__middle, __last, __first);
  202.     return copy_backward(__buffer, __buffer_end, __last);
  203.   }
  204.   else//若缓冲区仍然不够，则调用STL算法rotate，不使用缓冲区
  205.     return rotate(__first, __middle, __last);
  206. }
  208. template <class _BidirectionalIter1, class _BidirectionalIter2,
  209.           class _BidirectionalIter3>
  210. _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  211.                                      _BidirectionalIter1 __last1,
  212.                                      _BidirectionalIter2 __first2,
  213.                                      _BidirectionalIter2 __last2,
  214.                                      _BidirectionalIter3 __result) {
  215.   if (__first1 == __last1)
  216.     return copy_backward(__first2, __last2, __result);
  217.   if (__first2 == __last2)
  218.     return copy_backward(__first1, __last1, __result);
  219.   --__last1;
  220.   --__last2;
  221.   while (true) {
  222.     if (*__last2 < *__last1) {
  223.       *--__result = *__last1;
  224.       if (__first1 == __last1)
  225.         return copy_backward(__first2, ++__last2, __result);
  226.       --__last1;
  227.     }
  228.     else {
  229.       *--__result = *__last2;
  230.       if (__first2 == __last2)
  231.         return copy_backward(__first1, ++__last1, __result);
  232.       --__last2;
  233.     }
  234.   }
  235. }
  237. template <class _BidirectionalIter1, class _BidirectionalIter2,
  238.           class _BidirectionalIter3, class _Compare>
  239. _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  240.                                      _BidirectionalIter1 __last1,
  241.                                      _BidirectionalIter2 __first2,
  242.                                      _BidirectionalIter2 __last2,
  243.                                      _BidirectionalIter3 __result,
  244.                                      _Compare __comp) {
  245.   if (__first1 == __last1)
  246.     return copy_backward(__first2, __last2, __result);
  247.   if (__first2 == __last2)
  248.     return copy_backward(__first1, __last1, __result);
  249.   --__last1;
  250.   --__last2;
  251.   while (true) {
  252.     if (__comp(*__last2, *__last1)) {
  253.       *--__result = *__last1;
  254.       if (__first1 == __last1)
  255.         return copy_backward(__first2, ++__last2, __result);
  256.       --__last1;
  257.     }
  258.     else {
  259.       *--__result = *__last2;
  260.       if (__first2 == __last2)
  261.         return copy_backward(__first1, ++__last1, __result);
  262.       --__last2;
  263.     }
  264.   }
  265. }
  266. //版本一的辅助函数，有缓冲区的操作
  267. template <class _BidirectionalIter, class _Distance, class _Pointer>
  268. void __merge_adaptive(_BidirectionalIter __first,
  269.                       _BidirectionalIter __middle, 
  270.                       _BidirectionalIter __last,
  271.                       _Distance __len1, _Distance __len2,
  272.                       _Pointer __buffer, _Distance __buffer_size) {
  273.   if (__len1 <= __len2 && __len1 <= __buffer_size) {
  274.       //case1：把序列一放在缓冲区
  275.     _Pointer __buffer_end = copy(__first, __middle, __buffer);
  276.     //直接调用归并函数merge
  277.     merge(__buffer, __buffer_end, __middle, __last, __first);
  278.   }
  279.   else if (__len2 <= __buffer_size) {
  280.       //case2：把序列二放在缓冲区
  281.     _Pointer __buffer_end = copy(__middle, __last, __buffer);
  282.     __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
  283.   }
  284.   else {//case3：缓冲区不足放置任何一个序列
  285.     _BidirectionalIter __first_cut = __first;
  286.     _BidirectionalIter __second_cut = __middle;
  287.     _Distance __len11 = 0;
  288.     _Distance __len22 = 0;
  289.     if (__len1 > __len2) {//若序列一比较长
  290.       __len11 = __len1 / 2;//计算序列一的一半
  291.       advance(__first_cut, __len11);//让first_cut指向序列一的中间位置
  292.       //找出*__first_cut在[middle,last)区间中的第一个不小于*__first_cut的元素位置
  293.       __second_cut = lower_bound(__middle, __last, *__first_cut);
  294.       //计算middle到__second_cut之间的距离，保存在__len22
  295.       distance(__middle, __second_cut, __len22); 
  296.     }
  297.     else {//若序列二比较长
  298.       __len22 = __len2 / 2;//计算序列二的一半
  299.       advance(__second_cut, __len22);//让__second_cut指向序列二的中间位置
  300.       //找出*__second_cut在[first,middle)区间中的第一个大于*__second_cut的元素位置
  301.       __first_cut = upper_bound(__first, __middle, *__second_cut);
  302.       //计算__first到__first_cut之间的距离，保存在__len11
  303.       distance(__first, __first_cut, __len11);
  304.     }
  305.     _BidirectionalIter __new_middle =
  306.       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
  307.                         __len22, __buffer, __buffer_size);
  308.     //对左半段递归调用
  309.     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  310.                      __len22, __buffer, __buffer_size);
  311.     //对右半段递归调用
  312.     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  313.                      __len2 - __len22, __buffer, __buffer_size);
  314.   }
  315. }
  317. template <class _BidirectionalIter, class _Distance, class _Pointer,
  318.           class _Compare>
  319. void __merge_adaptive(_BidirectionalIter __first, 
  320.                       _BidirectionalIter __middle, 
  321.                       _BidirectionalIter __last,
  322.                       _Distance __len1, _Distance __len2,
  323.                       _Pointer __buffer, _Distance __buffer_size,
  324.                       _Compare __comp) {
  325.   if (__len1 <= __len2 && __len1 <= __buffer_size) {
  326.     _Pointer __buffer_end = copy(__first, __middle, __buffer);
  327.     merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
  328.   }
  329.   else if (__len2 <= __buffer_size) {
  330.     _Pointer __buffer_end = copy(__middle, __last, __buffer);
  331.     __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
  332.                      __comp);
  333.   }
  334.   else {
  335.     _BidirectionalIter __first_cut = __first;
  336.     _BidirectionalIter __second_cut = __middle;
  337.     _Distance __len11 = 0;
  338.     _Distance __len22 = 0;
  339.     if (__len1 > __len2) {
  340.       __len11 = __len1 / 2;
  341.       advance(__first_cut, __len11);
  342.       __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  343.       distance(__middle, __second_cut, __len22);   
  344.     }
  345.     else {
  346.       __len22 = __len2 / 2;
  347.       advance(__second_cut, __len22);
  348.       __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  349.       distance(__first, __first_cut, __len11);
  350.     }
  351.     _BidirectionalIter __new_middle =
  352.       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
  353.                         __len22, __buffer, __buffer_size);
  354.     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  355.                      __len22, __buffer, __buffer_size, __comp);
  356.     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  357.                      __len2 - __len22, __buffer, __buffer_size, __comp);
  358.   }
  359. }
  360. //版本一的辅助函数
  361. template <class _BidirectionalIter, class _Tp, class _Distance>
  362. inline void __inplace_merge_aux(_BidirectionalIter __first,
  363.                                 _BidirectionalIter __middle,
  364.                                 _BidirectionalIter __last, _Tp*, _Distance*) {
  365.   _Distance __len1 = 0;
  366.   distance(__first, __middle, __len1);//计算序列一的长度
  367.   _Distance __len2 = 0;
  368.   distance(__middle, __last, __len2);//计算序列二的长度
  370.   //使用暂时缓冲区
  371.   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
  372.   if (__buf.begin() == 0)//若缓冲区配置失败
  373.       //则调用不使用缓冲区的合并操作
  374.     __merge_without_buffer(__first, __middle, __last, __len1, __len2);
  375.   else//若分配成功
  376.       //则调用具有缓冲区的合并操作
  377.     __merge_adaptive(__first, __middle, __last, __len1, __len2,
  378.                      __buf.begin(), _Distance(__buf.size()));
  379. }
  381. template <class _BidirectionalIter, class _Tp, 
  382.           class _Distance, class _Compare>
  383. inline void __inplace_merge_aux(_BidirectionalIter __first,
  384.                                 _BidirectionalIter __middle,
  385.                                 _BidirectionalIter __last, _Tp*, _Distance*,
  386.                                 _Compare __comp) {
  387.   _Distance __len1 = 0;
  388.   distance(__first, __middle, __len1);
  389.   _Distance __len2 = 0;
  390.   distance(__middle, __last, __len2);
  392.   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
  393.   if (__buf.begin() == 0)
  394.     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
  395.   else
  396.     __merge_adaptive(__first, __middle, __last, __len1, __len2,
  397.                      __buf.begin(), _Distance(__buf.size()),
  398.                      __comp);
  399. }
  400. //将两个已排序的序列[first,middle)和[middle,last)合并成单一有序序列.
  401. //若原来是增序，现在也是递增排序，若原来是递减排序，现在也是递减排序
  402. /*
  403. 函数功能：Merges two consecutive sorted ranges: [first,middle) and [middle,last), 
  404. putting the result into the combined sorted range [first,last).
  405. 函数原型：
  406. default (1)    ：版本一
  407.     template <class BidirectionalIterator>
  408.     void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
  409.                       BidirectionalIterator last);
  410. custom (2)    ：版本二
  411.     template <class BidirectionalIterator, class Compare>
  412.     void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
  413.                       BidirectionalIterator last, Compare comp);
  414. */
  415. //版本一
  416. template <class _BidirectionalIter>
  417. inline void inplace_merge(_BidirectionalIter __first,
  418.                           _BidirectionalIter __middle,
  419.                           _BidirectionalIter __last) {
  420.   __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
  421.   __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
  422.                  _LessThanComparable);
  423.   if (__first == __middle || __middle == __last)//若有空序列，则之间返回
  424.     return;
  425.   __inplace_merge_aux(__first, __middle, __last,
  426.                       __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
  427. }
  428. //版本二
  429. template <class _BidirectionalIter, class _Compare>
  430. inline void inplace_merge(_BidirectionalIter __first,
  431.                           _BidirectionalIter __middle,
  432.                           _BidirectionalIter __last, _Compare __comp) {
  433.   __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
  434.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  435.            typename iterator_traits<_BidirectionalIter>::value_type,
  436.            typename iterator_traits<_BidirectionalIter>::value_type);
  437.   if (__first == __middle || __middle == __last)
  438.     return;
  439.   __inplace_merge_aux(__first, __middle, __last,
  440.                       __VALUE_TYPE(__first), __DISTANCE_TYPE(__first),
  441.                       __comp);
  442. }
  443. //inplace_merge函数举例：
  444. /*
  445.     #include <iostream>     // std::cout
  446.     #include <algorithm>    // std::inplace_merge, std::sort, std::copy
  447.     #include <vector>       // std::vector
  449.     int main () {
  450.       int first[] = {5,10,15,20,25};
  451.       int second[] = {50,40,30,20,10};
  452.       std::vector<int> v(10);
  453.       std::vector<int>::iterator it;
  455.       std::sort (first,first+5);
  456.       std::sort (second,second+5);
  458.       it=std::copy (first, first+5, v.begin());
  459.          std::copy (second,second+5,it);
  461.       std::inplace_merge (v.begin(),v.begin()+5,v.end());
  463.       std::cout << "The resulting vector contains:";
  464.       for (it=v.begin(); it!=v.end(); ++it)
  465.         std::cout << ' ' << *it;
  466.       std::cout << '\n';
  468.       return 0;
  469.     }
  470.     Output：
  471.     The resulting vector contains: 5 10 10 15 20 20 25 30 40 50
  472. */

参考资料：

《STL源码剖析》侯捷

发表评论

表情：
评论列表 （有 0 条评论，432人围观）

还没有评论，来说两句吧...

相关阅读

    相关 【STL源码剖析】Sort算法

    前言：sort算法必须拿出来单独将，因为它是STL所有算法中最复杂最庞大的一个，就像我肯定会把copy算法单独列出来一样，这两个算法太重要了。 提示：STL算法特点是，前两个

    亦凉亦凉/ 0 赞/ 324 阅读