STL一共提供了四种与集合相关的算法，分别是并集（union）， 交集（intersection），差集（difference），对称差集（symmetric difference）。

　　这四种集合算法要求处理的两个序列都是非递减有序的，而且处理后的结果集合没有重复的元素。

　　下面是这四种集合算法的具体实现，为了方便起见，我去掉了模板，集合中的数据类型用int。

1，并集union

1 void my_union(int *s1, int len1, 2            int *s2, int len2, 3            int *result) 4 { 5     int first1=0, first2=0; 6  7     while(first1 != len1 && first2 != len2) 8     { 9         if(s1[first1] < s2[first2]){10             *result = s1[first1];11             first1++;12         }13         else if(s1[first1] > s2[first2]){14             *result = s2[first2];15             first2++;16         }17         else{18             *result = s1[first1];19             first1++;20             first2++;21         }22         result++;23     }24 25     while(first1 != len1)26         *result++ = s1[first1++];27     while(first2 != len2)28         *result++ = s2[first2++];29 }

2，交集intersection

　　intersection的实现比较简单，只有s1和s2中两个元素相同的时候才将元素拷贝进result中。

　　

1 void my_intersection(int *s1, int len1, 2                      int *s2, int len2, 3                      int *result) 4 { 5     int first1=0,first2=0; 6  7     while(first1 != len1 && first2 != len2) 8     { 9         if(s1[first1] < s2[first2])10             first1++;11         else if(s1[first1] > s2[first2])12             first2++;13         else{14             *result++ = s1[first1];15             first1++;16             first2++;17         }18     }19 }

3，差集difference

　　差集difference构造出集合s1-s2。

1 void my_difference(int *s1, int len1, 2                    int *s2, int len2, 3                    int *result) 4 { 5     int first1=0, first2=0; 6  7     while(first1 != len1 && first2 != len2) 8     { 9         if(s1[first1] < s2[first2]){10             *result++ = s1[first1];11             first1++;12         }13         else if(s1[first1] > s2[first2])14             first2++;15         else{16             first1++;17             first2++;18         }19     }20 21     while(first1 != len1)22         *result++ = s1[first1++];23 }

4，对称差集symmetric_difference

　　对称差集返回“属于s1但不属于s2”且“属于s2但不属于s1”的每一个元素。

　　

1 void my_symm_difference(int *s1, int len1, 2                         int *s2, int len2, 3                         int *result) 4 { 5     int first1=0,first2=0; 6  7     while(first1 != len1 && first2 != len2) 8     { 9         if(s1[first1] < s2[first2]){10             *result++ = s1[first1];11             first1++;12         }13         else if(s1[first1] > s2[first2]){14             *result++ = s2[first2];15             first2++;16         }17         else{18             first1++;19             first2++;20         }21     }22 23     while(first1 != len1)24         *result++ = s1[first1++];25     while(first2 != len2)26         *result++ = s2[first2++];27 }

 

　　以上这些算法都不算很难，但是STL以一种统一的编程方式将上面的四种算法高效地实现。值得学习和回味。