STL中定义的set要求元素不得重复且已经排序。而set算法要求的都是有序区间（输出也是有序的），但元素可以重复出现。

STL提供了4个set相关的算法，分别是并集（union）、交集（intersection）、差集（difference）和对称差集（symmetric difference），这4个算法接受的set必须是有序区间，都至少接受4个参数，分别表示两个set区间。一般而言，set算法前4个参数分别表示两个区间，第五个参数表示存放结果的区间的起始位置。

1、set_union

求两个集合的并集，能够造出S1 U S2，此集合内含S1或S2内的每一个元素。如果某个值在S1出现n次，在S2出现m次，那么该值在输出区间中会出现max(m, n)次。

返回值为一个迭代器，指向输出区间的尾端。

是一种稳定操作，输入区间内的每个元素相对顺序都不会改变。

//并集，求存在于[first1, last1)或存在于[first2, last2)内的所有元素  
//注意：输入区间必须是已排序  
//版本一,默认是operator<操作的排序方式  
template <class InputIterator1, class InputIterator2, class OutputIterator>  
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,  InputIterator2 first2, InputIterator2 last2,  OutputIterator result) {  //两个区间都尚未到达区间尾端，执行以下操作  while (first1 != last1 && first2 != last2) {  /*在两区间内分别移动迭代器，首先将元素较小者(假设为A区)记录在目标区result，移动A区迭代器使其前进；同时另一个区的迭代器不变。然后进行一次新的比较， 记录较小值，移动迭代器...直到两区间中有一个到达尾端。若元素相等， 默认取第一区间元素到目标区result，同时移动两个迭代器.*/  if (*first1 < *first2) {  *result = *first1;  ++first1;  }  else if (*first2 < *first1) {  *result = *first2;  ++first2;  }  else {  *result = *first1;  ++first1;  ++first2;  }  ++result;  }  /*只要两区间之中有一个区间到达尾端，就结束上面的while循环以下将尚未到达尾端的区间剩余的元素拷贝到目标区 此刻，[first1, last1)和[first2, last2)至少有一个是空区间*/  return copy(first2, last2, copy(first1, last1, result));  
}  
//版本二,用户根据仿函数comp指定排序规则  
template <class InputIterator1, class InputIterator2, class OutputIterator,class Compare>  
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,  InputIterator2 first2, InputIterator2 last2,  OutputIterator result, Compare comp) {  while (first1 != last1 && first2 != last2) {  if (comp(*first1, *first2)) {  *result = *first1;  ++first1;  }  else if (comp(*first2, *first1)) {  *result = *first2;  ++first2;  }  else {  *result = *first1;  ++first1;  ++first2;  }  ++result;  }  return copy(first2, last2, copy(first1, last1, result));  
}  

图解如下：

2、set_intersection

求两个集合的交集，此集合内含同时出现于S1和S2内的每一个元素。如果某个值在S1出现n次，在S2出现m次，那么该值在输出区间中会出现min(m, n)次，并且全部来自S1。

返回值为一个迭代器，指向输出区间的尾端。

是一种稳定操作，输入区间内的每个元素相对顺序都不会改变。

//交集，求存在于[first1, last1)且存在于[first2, last2)内的所有元素  
//注意：输入区间必须是已排序  
//版本一,默认是operator<操作的排序方式  
template <class InputIterator1, class InputIterator2, class OutputIterator>  
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,  InputIterator2 first2, InputIterator2 last2,  OutputIterator result) {  //若两个区间都尚未到达尾端，则执行以下操作  while (first1 != last1 && first2 != last2)  //在两个区间分别移动迭代器，直到遇到相等元素，记录到目标区  //继续移动迭代器...直到两区间之中有一区到达尾端  if (*first1 < *first2)  ++first1;  else if (*first2 < *first1)  ++first2;  else {  *result = *first1;  ++first1;  ++first2;  ++result;  }  return result;  
}  
//版本二,用户根据仿函数comp指定排序规则  
//略。

图解如下：

3、set_difference

求两个集合的差集，此集合内含出现于S1但不出现于S2内的元素。如果某个值在S1出现n次，在S2出现m次，那么该值在输出区间中会出现max(n-m, 0)次，并且全部来自S1。

返回值为一个迭代器，指向输出区间的尾端。

是一种稳定操作，输入区间内的每个元素相对顺序都不会改变。

//差集，求存在于[first1, last1)且不存在于[first2, last2)内的所有元素  
//注意：输入区间必须是已排序  
//版本一，默认是operator<操作的排序方式  
template <class InputIterator1, class InputIterator2, class OutputIterator>  
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,  InputIterator2 first2, InputIterator2 last2,  OutputIterator result) {  //若两个区间都尚未到达尾端，则执行以下操作  while (first1 != last1 && first2 != last2)  /*在两个区间分别移动迭代器，当第一区间元素等于第二区间元素时，表示两区间共同存在该元素，则同时移动迭代器； 当第一区间元素大于第二区间元素时，就让第二区间迭代器前进； 第一区间元素小于第二区间元素时，把第一区间元素记录到目标区 继续移动迭代器...直到两区间之中有到达尾端*/  if (*first1 < *first2) {  *result = *first1;  ++first1;  ++result;  }  else if (*first2 < *first1)  ++first2;  else {  ++first1;  ++first2;  }  //把第一区间剩余的元素(若有剩余)复制到目标区return copy(first1, last1, result);  
}  
//版本二，用户根据仿函数comp指定排序规则  
//略.

图解如下：

4、set_symmetric_difference

求两个集合的对称差集(s1-s2)∪(s2-s1)，此集合内含出现于S1但不出现于S2内的元素，以及出现于S2但不出现于S1内的每一个元素。如果某个值在S1出现n次，在S2出现m次，那么该值在输出区间中会出现|n-m|次。

返回值为一个迭代器，指向输出区间的尾端。

是一种稳定操作，输入区间内的每个元素相对顺序都不会改变。

//对称差集，求存在于[first1, last1)但不存在于[first2, 
//last2)内的所有元素以及出现在[first2, last2)但不出现在
//[first1, last1)的所有元素  
//注意：输入区间必须是已排序  
//版本一，默认是operator<操作的排序方式  
template <class InputIterator1, class InputIterator2, class OutputIterator>  
OutputIterator set_symmetric_difference(InputIterator1 first1,  InputIterator1 last1,  InputIterator2 first2,  InputIterator2 last2,  OutputIterator result) {   //若两个区间都尚未到达尾端，则执行下面的操作  while (first1 != last1 && first2 != last2)  /*在两区间内分别移动迭代器。当两区间内的元素相等，就让两区同时前进； 当两区间内的元素不等，就记录较小值于目标区，并令较小值所在区间前进*/  if (*first1 < *first2) {  *result = *first1;  ++first1;  ++result;  }  else if (*first2 < *first1) {  *result = *first2;  ++first2;  ++result;  }  else {  ++first1;  ++first2;  }  return copy(first2, last2, copy(first1, last1, result));  
}     
//版本二，用户根据仿函数comp指定排序规则
//略。

图解如下：

5、应用实例：

#include<algorithm>  
#include<set>  
#include<iterator>  
#include<iostream>  
using namespace std;  template<typename T>  
struct display{  void operator()(const T& x) const{  cout << x << " ";  }  
};  int main(){  int ia[] = { 1, 3, 5, 7, 9, 11 };  int ib[] = { 1, 1, 2, 3, 5, 8, 13 };  multiset<int> s1(begin(ia), end(ia));  multiset<int> s2(begin(ib), end(ib));  for_each(s1.begin(), s1.end(), display<int>());  cout << endl;  for_each(s2.begin(), s2.end(), display<int>());  cout << endl;  multiset<int>::iterator first1 = s1.begin();  multiset<int>::iterator last1 = s1.end();  multiset<int>::iterator first2 = s2.begin();  multiset<int>::iterator last2 = s2.end();  cout << "union of s1 and s2:";  set_union(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));  cout << endl;  cout << "intersection of s1 and s2:";  set_intersection(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));  cout << endl;  cout << "difference of s1 and s2:";  set_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));  cout << endl;  cout << "symmetric differenceof s1 and s2:";  set_symmetric_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));  cout << endl;  return 0;  
}