STL源码剖析——STL算法之set集合算法

矫情吗；* 2022-08-12 16:27 291阅读 0赞

前言

本节介绍set集合的相关算法，分别是并集set_union，差集set_difference，交集set_intersection
和对称差集set_symmetric_difference，这是个函数都提供了两个版本的函数原型：第一个版本是采用默认的排序比较方式operator<；第二个版本是用户通过仿函数comp自行指定排序方式。注意：这四个算法接受的输入区间都是有序的，输出也是有序的。下面对set算法进行剖析，具体注释详见源码，同时给出例子说明该算法的功能。本文源码摘自SGI STL中的文件。

set算法源码剖析

  1. /*
  2. 下面是计算set集合的相关算法，分别是并集set_union，差集set_difference，交集set_intersection
  3. 和对称差集set_symmetric_difference，这是个函数都提供了两个版本的函数原型
  4. 第一个版本是采用默认的排序比较方式 operator<
  5. 第二个版本是用户通过comp自行指定排序方式
  6. 注意：这四个算法接受的输入区间都是有序的，输出也是有序的
  7. */
  9. // Set algorithms: includes, set_union, set_intersection, set_difference,
  10. // set_symmetric_difference.  All of these algorithms have the precondition
  11. // that their input ranges are sorted and the postcondition that their output
  12. // ranges are sorted.
  14. // 判断[first1, last1)是否包含[first2, last2),  
  15. // 注意: 两个区间要保证有序,默认排序方式是operator<，若要自行定义排序方式，则调用第二版本;
  16. template <class _InputIter1, class _InputIter2>
  17. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  18.               _InputIter2 __first2, _InputIter2 __last2) {
  19.   __STL_REQUIRES(_InputIter1, _InputIterator);
  20.   __STL_REQUIRES(_InputIter2, _InputIterator);
  21.   __STL_REQUIRES_SAME_TYPE(
  22.        typename iterator_traits<_InputIter1>::value_type,
  23.        typename iterator_traits<_InputIter2>::value_type);
  24.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  25.                  _LessThanComparable);
  26.   while (__first1 != __last1 && __first2 != __last2)//遍历两个区间
  27.     if (*__first2 < *__first1)//first2小于first1表示不包含
  28.       return false;//返回FALSE
  29.     else if(*__first1 < *__first2)//若first1小于first2 
  30.       ++__first1;//寻找第一个区间下一个位置
  31.     else
  32.       ++__first1, ++__first2;//若first2等于first1,遍历两区间的下一位置
  34.   return __first2 == __last2;//若第二个区间先到达尾端，则返回TRUE
  35. }
  37. //版本二：用户通过comp自行指定排序方式
  38. template <class _InputIter1, class _InputIter2, class _Compare>
  39. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  40.               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  41.   __STL_REQUIRES(_InputIter1, _InputIterator);
  42.   __STL_REQUIRES(_InputIter2, _InputIterator);
  43.   __STL_REQUIRES_SAME_TYPE(
  44.        typename iterator_traits<_InputIter1>::value_type,
  45.        typename iterator_traits<_InputIter2>::value_type);
  46.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  47.        typename iterator_traits<_InputIter1>::value_type,
  48.        typename iterator_traits<_InputIter2>::value_type);
  49.   while (__first1 != __last1 && __first2 != __last2)
  50.     if (__comp(*__first2, *__first1))
  51.       return false;
  52.     else if(__comp(*__first1, *__first2)) 
  53.       ++__first1;
  54.     else
  55.       ++__first1, ++__first2;
  57.   return __first2 == __last2;
  58. }
  60. //两个集合区间的并集，同样也有两个版本
  61. //求存在于[first1, last1)或存在于[first2, last2)内的所有元素
  62. //注意：输入区间必须是已排序
  63. /*
  64. default (1)    :默认是operator<操作的排序方式
  65.     template <class InputIterator1, class InputIterator2, class OutputIterator>
  66.     OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
  67.                             InputIterator2 first2, InputIterator2 last2,
  68.                             OutputIterator result);
  69. custom (2)    :用户指定的排序方式
  70.     template <class InputIterator1, class InputIterator2,
  71.           class OutputIterator, class Compare>
  72.     OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
  73.                             InputIterator2 first2, InputIterator2 last2,
  74.                             OutputIterator result, Compare comp);
  75. */
  76. //版本一：默认是operator<操作的排序方式
  77. template <class _InputIter1, class _InputIter2, class _OutputIter>
  78. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  79.                       _InputIter2 __first2, _InputIter2 __last2,
  80.                       _OutputIter __result) {
  81.   __STL_REQUIRES(_InputIter1, _InputIterator);
  82.   __STL_REQUIRES(_InputIter2, _InputIterator);
  83.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  84.   __STL_REQUIRES_SAME_TYPE(
  85.        typename iterator_traits<_InputIter1>::value_type,
  86.        typename iterator_traits<_InputIter2>::value_type);
  87.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  88.                  _LessThanComparable);
  89.   //两个区间都尚未到达区间尾端，执行以下操作
  90.   while (__first1 != __last1 && __first2 != __last2) {
  91.       /*
  92.       在两区间内分别移动迭代器，首先将元素较小者(假设为A区)记录在目标区result
  93.       移动A区迭代器使其前进；同时另一个区的迭代器不变。然后进行一次新的比较，
  94.       记录较小值，移动迭代器...直到两区间中有一个到达尾端。若两区间存在元素相等，
  95.       默认记录第一区间的元素到目标区result.
  96.       */
  97.     if (*__first1 < *__first2) {//first1小于first2
  98.       *__result = *__first1;//则result初始值为first1
  99.       ++__first1;//继续第一个区间的下一个元素位置
  100.     }
  101.     else if (*__first2 < *__first1) {//first2小于first1
  102.       *__result = *__first2;//第二区间元素值记录到目标区
  103.       ++__first2;//移动第二区间的迭代器
  104.     }
  105.     else {//若两区间存在相等的元素，把第一区间元素记录到目标区
  106.         //同时移动两个区间的迭代器
  107.       *__result = *__first1;
  108.       ++__first1;
  109.       ++__first2;
  110.     }
  111.     ++__result;//更新目标区位置，以备进入下一次记录操作操作
  112.   }
  113.   /*
  114.   只要两区间之中有一个区间到达尾端，就结束上面的while循环
  115.   以下将尚未到达尾端的区间剩余的元素拷贝到目标区
  116.   此刻，[first1, last1)和[first2, last2)至少有一个是空区间
  117.   */
  118.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  119. }
  120. //版本二：用户根据仿函数comp指定排序规则
  121. template <class _InputIter1, class _InputIter2, class _OutputIter,
  122.           class _Compare>
  123. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  124.                       _InputIter2 __first2, _InputIter2 __last2,
  125.                       _OutputIter __result, _Compare __comp) {
  126.   __STL_REQUIRES(_InputIter1, _InputIterator);
  127.   __STL_REQUIRES(_InputIter2, _InputIterator);
  128.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  129.   __STL_REQUIRES_SAME_TYPE(
  130.        typename iterator_traits<_InputIter1>::value_type,
  131.        typename iterator_traits<_InputIter2>::value_type);
  132.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  133.        typename iterator_traits<_InputIter1>::value_type,
  134.        typename iterator_traits<_InputIter2>::value_type);
  135.   while (__first1 != __last1 && __first2 != __last2) {
  136.     if (__comp(*__first1, *__first2)) {
  137.       *__result = *__first1;
  138.       ++__first1;
  139.     }
  140.     else if (__comp(*__first2, *__first1)) {
  141.       *__result = *__first2;
  142.       ++__first2;
  143.     }
  144.     else {
  145.       *__result = *__first1;
  146.       ++__first1;
  147.       ++__first2;
  148.     }
  149.     ++__result;
  150.   }
  151.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  152. }
  153. /*例子:
  154.     #include <iostream>     // std::cout
  155.     #include <algorithm>    // std::set_union, std::sort
  156.     #include <vector>       // std::vector
  158.     int main () {
  159.       int first[] = {5,10,15,20,25};
  160.       int second[] = {50,40,30,20,10};
  161.       std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
  162.       std::vector<int>::iterator it;
  164.       std::sort (first,first+5);     //  5 10 15 20 25
  165.       std::sort (second,second+5);   // 10 20 30 40 50
  167.       it=std::set_union (first, first+5, second, second+5, v.begin());
  168.                                                    // 5 10 15 20 25 30 40 50  0  0
  169.       v.resize(it-v.begin());                      // 5 10 15 20 25 30 40 50
  171.       std::cout << "The union has " << (v.size()) << " elements:\n";
  172.       for (it=v.begin(); it!=v.end(); ++it)
  173.         std::cout << ' ' << *it;
  174.       std::cout << '\n';
  176.       return 0;
  177.     }
  178.     Output:
  179.     The union has 8 elements:
  180.     5 10 15 20 25 30 40 50
  181. */
  183.  //两个集合区间的交集，同样也有两个版本
  184. //求存在于[first1, last1)且存在于[first2, last2)内的所有元素
  185. //注意：输入区间必须是已排序，输出区间的每个元素的相对排序和第一个区间相对排序相同
  186. /*
  187. default (1)    :默认是operator<操作的排序方式
  188.         template <class InputIterator1, class InputIterator2, class OutputIterator>
  189.         OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
  190.                                    InputIterator2 first2, InputIterator2 last2,
  191.                                    OutputIterator result);
  194. custom (2)    :用户指定的排序方式
  195.         template <class InputIterator1, class InputIterator2,
  196.           class OutputIterator, class Compare>
  197.         OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
  198.                                    InputIterator2 first2, InputIterator2 last2,
  199.                                    OutputIterator result, Compare comp);
  200. */
  201. //版本一：默认是operator<操作的排序方式
  202. template <class _InputIter1, class _InputIter2, class _OutputIter>
  203. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  204.                              _InputIter2 __first2, _InputIter2 __last2,
  205.                              _OutputIter __result) {
  206.   __STL_REQUIRES(_InputIter1, _InputIterator);
  207.   __STL_REQUIRES(_InputIter2, _InputIterator);
  208.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  209.   __STL_REQUIRES_SAME_TYPE(
  210.        typename iterator_traits<_InputIter1>::value_type,
  211.        typename iterator_traits<_InputIter2>::value_type);
  212.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  213.                  _LessThanComparable);
  214.   //若两个区间都尚未到达尾端，则执行以下操作
  215.   while (__first1 != __last1 && __first2 != __last2) 
  216.     //在两个区间分别移动迭代器，直到遇到相等元素，记录到目标区
  217.     //继续移动迭代器...直到两区间之中有到达尾端
  218.     if (*__first1 < *__first2) //第一个区间元素小于第二区间元素
  219.       ++__first1;//移动第一区间的迭代器，此时第二区间的迭代器不变
  220.     else if (*__first2 < *__first1) //第二区间的元素小于第一区间元素
  221.       ++__first2;//移动第二区间元素，此时第一区间的迭代器不变
  222.     else {//若第一区间元素等于第二区间元素
  223.       *__result = *__first1;//按第一区间的相对排序记录到目标区
  224.       //分别移动两区间的迭代器
  225.       ++__first1;
  226.       ++__first2;
  227.       //更新目标区迭代器，以便继续记录元素
  228.       ++__result;
  229.     }
  230.     //若有区间到达尾部，则停止while循环
  231.     //此时，返回目标区
  232.   return __result;
  233. }
  234. //版本二：用户根据仿函数comp指定排序规则
  235. template <class _InputIter1, class _InputIter2, class _OutputIter,
  236.           class _Compare>
  237. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  238.                              _InputIter2 __first2, _InputIter2 __last2,
  239.                              _OutputIter __result, _Compare __comp) {
  240.   __STL_REQUIRES(_InputIter1, _InputIterator);
  241.   __STL_REQUIRES(_InputIter2, _InputIterator);
  242.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  243.   __STL_REQUIRES_SAME_TYPE(
  244.        typename iterator_traits<_InputIter1>::value_type,
  245.        typename iterator_traits<_InputIter2>::value_type);
  246.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  247.        typename iterator_traits<_InputIter1>::value_type,
  248.        typename iterator_traits<_InputIter2>::value_type);
  250.   while (__first1 != __last1 && __first2 != __last2)
  251.     if (__comp(*__first1, *__first2))
  252.       ++__first1;
  253.     else if (__comp(*__first2, *__first1))
  254.       ++__first2;
  255.     else {
  256.       *__result = *__first1;
  257.       ++__first1;
  258.       ++__first2;
  259.       ++__result;
  260.     }
  261.   return __result;
  262. }
  263. /*例子：
  264.     #include <iostream>     // std::cout
  265.     #include <algorithm>    // std::set_intersection, std::sort
  266.     #include <vector>       // std::vector
  268.     int main () {
  269.       int first[] = {5,10,15,20,25};
  270.       int second[] = {50,40,30,20,10};
  271.       std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
  272.       std::vector<int>::iterator it;
  274.       std::sort (first,first+5);     //  5 10 15 20 25
  275.       std::sort (second,second+5);   // 10 20 30 40 50
  277.       it=std::set_intersection (first, first+5, second, second+5, v.begin());
  278.                                                    // 10 20 0  0  0  0  0  0  0  0
  279.       v.resize(it-v.begin());                      // 10 20
  281.       std::cout << "The intersection has " << (v.size()) << " elements:\n";
  282.       for (it=v.begin(); it!=v.end(); ++it)
  283.         std::cout << ' ' << *it;
  284.       std::cout << '\n';
  286.       return 0;
  287.     }
  288.     Output:
  289.     The intersection has 2 elements:
  290.     10 20
  291. */
  293.  //两个集合区间的差集，同样也有两个版本
  294. //求存在于[first1, last1)但不存在于[first2, last2)内的所有元素
  295. //注意：输入区间必须是已排序，输出区间的每个元素的相对排序和第一个区间相对排序相同
  296. /*
  297. default (1)    :默认是operator<操作的排序方式
  298.         template <class InputIterator1, class InputIterator2, class OutputIterator>
  299.         OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
  300.                                  InputIterator2 first2, InputIterator2 last2,
  301.                                  OutputIterator result);
  305. custom (2)    :用户指定的排序方式
  306.         template <class InputIterator1, class InputIterator2,
  307.           class OutputIterator, class Compare>
  308.         OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
  309.                                  InputIterator2 first2, InputIterator2 last2,
  310.                                  OutputIterator result, Compare comp);
  311. */
  312. //版本一：默认是operator<操作的排序方式
  313. template <class _InputIter1, class _InputIter2, class _OutputIter>
  314. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  315.                            _InputIter2 __first2, _InputIter2 __last2,
  316.                            _OutputIter __result) {
  317.   __STL_REQUIRES(_InputIter1, _InputIterator);
  318.   __STL_REQUIRES(_InputIter2, _InputIterator);
  319.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  320.   __STL_REQUIRES_SAME_TYPE(
  321.        typename iterator_traits<_InputIter1>::value_type,
  322.        typename iterator_traits<_InputIter2>::value_type);
  323.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  324.                  _LessThanComparable);
  325.   //若两个区间都尚未到达尾端，则执行以下操作
  326.   while (__first1 != __last1 && __first2 != __last2)
  327.      /*
  328.      在两个区间分别移动迭代器，当第一区间元素等于第二区间元素时，表示两区间共同存在该元素
  329.      则同时移动迭代器；
  330.      当第一区间元素大于第二区间元素时，就让第二区间迭代器前进；
  331.      第一区间元素小于第二区间元素时，把第一区间元素记录到目标区
  332.     继续移动迭代器...直到两区间之中有到达尾端
  333.     */
  334.     if (*__first1 < *__first2) {//第一区间元素小于第二区间元素
  335.       *__result = *__first1;//把第一区间元素记录到目标区
  336.       ++__first1;//移动第一区间迭代器
  337.       ++__result;//跟新目标区，以便继续记录数据
  338.     }
  339.     else if (*__first2 < *__first1)//当第一区间的元素大于第二区间的元素
  340.       ++__first2;//移动第二区间迭代器,注意：这里不记录任何元素
  341.     else {//若两区间的元素相等时,同时移动两区间的迭代器
  342.       ++__first1;
  343.       ++__first2;
  344.     }
  345.     //若第二区间先到达尾端，则把第一区间剩余的元素复制到目标区
  346.   return copy(__first1, __last1, __result);
  347. }
  348. //版本二：用户根据仿函数comp指定排序规则
  349. template <class _InputIter1, class _InputIter2, class _OutputIter, 
  350.           class _Compare>
  351. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  352.                            _InputIter2 __first2, _InputIter2 __last2, 
  353.                            _OutputIter __result, _Compare __comp) {
  354.   __STL_REQUIRES(_InputIter1, _InputIterator);
  355.   __STL_REQUIRES(_InputIter2, _InputIterator);
  356.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  357.   __STL_REQUIRES_SAME_TYPE(
  358.        typename iterator_traits<_InputIter1>::value_type,
  359.        typename iterator_traits<_InputIter2>::value_type);
  360.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  361.        typename iterator_traits<_InputIter1>::value_type,
  362.        typename iterator_traits<_InputIter2>::value_type);
  364.   while (__first1 != __last1 && __first2 != __last2)
  365.     if (__comp(*__first1, *__first2)) {
  366.       *__result = *__first1;
  367.       ++__first1;
  368.       ++__result;
  369.     }
  370.     else if (__comp(*__first2, *__first1))
  371.       ++__first2;
  372.     else {
  373.       ++__first1;
  374.       ++__first2;
  375.     }
  376.   return copy(__first1, __last1, __result);
  377. }
  378. /*例子：
  379.     #include <iostream>     // std::cout
  380.     #include <algorithm>    // std::set_difference, std::sort
  381.     #include <vector>       // std::vector
  383.     int main () {
  384.       int first[] = {5,10,15,20,25};
  385.       int second[] = {50,40,30,20,10};
  386.       std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
  387.       std::vector<int>::iterator it;
  389.       std::sort (first,first+5);     //  5 10 15 20 25
  390.       std::sort (second,second+5);   // 10 20 30 40 50
  392.       it=std::set_difference (first, first+5, second, second+5, v.begin());
  393.                                                    //  5 15 25  0  0  0  0  0  0  0
  394.       v.resize(it-v.begin());                      //  5 15 25
  396.       std::cout << "The difference has " << (v.size()) << " elements:\n";
  397.       for (it=v.begin(); it!=v.end(); ++it)
  398.         std::cout << ' ' << *it;
  399.       std::cout << '\n';
  401.       return 0;
  402.     }
  403.     Output：
  404.     The difference has 3 elements:
  405.     5 15 25
  406. */
  408.  //两个集合区间的对称差集，同样也有两个版本
  409. //求存在于[first1, last1)但不存在于[first2, last2)内的所有元素以及出现在[first2, last2)但不出现在[first1, last1)
  410. //注意：输入区间必须是已排序
  411. /*
  412. default (1)    :默认是operator<操作的排序方式
  413.         template <class InputIterator1, class InputIterator2, class OutputIterator>
  414.         OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1,
  415.                                            InputIterator2 first2, InputIterator2 last2,
  416.                                            OutputIterator result);
  419. custom (2)    :用户指定的排序方式
  420.         template <class InputIterator1, class InputIterator2,
  421.           class OutputIterator, class Compare>
  422.         OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1,
  423.                                            InputIterator2 first2, InputIterator2 last2,
  424.                                            OutputIterator result, Compare comp);
  425. */
  426. //版本一：默认是operator<操作的排序方式
  427. template <class _InputIter1, class _InputIter2, class _OutputIter>
  428. _OutputIter 
  429. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  430.                          _InputIter2 __first2, _InputIter2 __last2,
  431.                          _OutputIter __result) {
  432.   __STL_REQUIRES(_InputIter1, _InputIterator);
  433.   __STL_REQUIRES(_InputIter2, _InputIterator);
  434.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  435.   __STL_REQUIRES_SAME_TYPE(
  436.        typename iterator_traits<_InputIter1>::value_type,
  437.        typename iterator_traits<_InputIter2>::value_type);
  438.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  439.                  _LessThanComparable);
  440.   //若两个区间都尚未到达尾端，则执行下面的操作
  441.   while (__first1 != __last1 && __first2 != __last2)
  442.       /*
  443.       情况1：若两区间元素相等，则同时移动两区间的迭代器.
  444.       情况2：若第一区间的元素小于第二区间元素，则把第一区间元素记录到目标区，且移动第一区间迭代器.
  445.       情况3：若第一区间的元素大于第二区间元素，则把第二区间元素记录到目标区，且移动第二区间迭代器.
  446.       */
  447.     if (*__first1 < *__first2) {//属于情况2
  448.       *__result = *__first1;//把第一区间元素记录到目标区
  449.       ++__first1;//移动第一区间迭代器.此时第二区间迭代器不变
  450.       ++__result;
  451.     }
  452.     else if (*__first2 < *__first1) {//属于情况3
  453.       *__result = *__first2;//把第二区间元素记录到目标区
  454.       ++__first2;//移动第二区间迭代器.此时第一区间迭代器不变
  455.       ++__result;
  456.     }
  457.     else {//属于情况1
  458.         //同时移动两区间的迭代器
  459.       ++__first1;
  460.       ++__first2;
  461.     }
  462.      /*
  463.   只要两区间之中有一个区间到达尾端，就结束上面的while循环
  464.   以下将尚未到达尾端的区间剩余的元素拷贝到目标区
  465.   此刻，[first1, last1)和[first2, last2)至少有一个是空区间
  466.   */
  467.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  468. }
  470. //版本二：用户根据仿函数comp指定排序规则
  471. template <class _InputIter1, class _InputIter2, class _OutputIter,
  472.           class _Compare>
  473. _OutputIter 
  474. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  475.                          _InputIter2 __first2, _InputIter2 __last2,
  476.                          _OutputIter __result,
  477.                          _Compare __comp) {
  478.   __STL_REQUIRES(_InputIter1, _InputIterator);
  479.   __STL_REQUIRES(_InputIter2, _InputIterator);
  480.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  481.   __STL_REQUIRES_SAME_TYPE(
  482.        typename iterator_traits<_InputIter1>::value_type,
  483.        typename iterator_traits<_InputIter2>::value_type);
  484.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  485.        typename iterator_traits<_InputIter1>::value_type,
  486.        typename iterator_traits<_InputIter2>::value_type);
  487.   while (__first1 != __last1 && __first2 != __last2)
  488.     if (__comp(*__first1, *__first2)) {
  489.       *__result = *__first1;
  490.       ++__first1;
  491.       ++__result;
  492.     }
  493.     else if (__comp(*__first2, *__first1)) {
  494.       *__result = *__first2;
  495.       ++__first2;
  496.       ++__result;
  497.     }
  498.     else {
  499.       ++__first1;
  500.       ++__first2;
  501.     }
  502.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  503. }
  504. /*例子：
  505.     #include <iostream>     // std::cout
  506.     #include <algorithm>    // std::set_symmetric_difference, std::sort
  507.     #include <vector>       // std::vector
  509.     int main () {
  510.       int first[] = {5,10,15,20,25};
  511.       int second[] = {50,40,30,20,10};
  512.       std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
  513.       std::vector<int>::iterator it;
  515.       std::sort (first,first+5);     //  5 10 15 20 25
  516.       std::sort (second,second+5);   // 10 20 30 40 50
  518.       it=std::set_symmetric_difference (first, first+5, second, second+5, v.begin());
  519.                                                    //  5 15 25 30 40 50  0  0  0  0
  520.       v.resize(it-v.begin());                      //  5 15 25 30 40 50
  522.       std::cout << "The symmetric difference has " << (v.size()) << " elements:\n";
  523.       for (it=v.begin(); it!=v.end(); ++it)
  524.         std::cout << ' ' << *it;
  525.       std::cout << '\n';
  527.       return 0;
  528.     }
  529.     Output：
  530.     The symmetric difference has 6 elements:
  531.     5 15 25 30 40 50
  532. */

参考资料：

《STL源码剖析》侯捷

发表评论

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

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

相关阅读

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

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

    亦凉亦凉/ 0 赞/ 324 阅读