set算法 (交集，并集，差集，对称差集)

set是以种以红黑树作为底部结构的关联式容器，它查找的平均时间复杂度可以达到 O(logN)。

• 模拟实现 set 的代码

概述

set 是一种关联式的容器，它的特点是：所有元素依照键值大小被排序。

由于 set 内元素有序的特点，所以以红黑树作为它的底部容器最合适不过了。set 中的值不允许被改变，原因是改变它的值会影响底部容器——红黑树的结构，而红黑树的调整则需要付出很大的代价。正因为如此，它具有很高的查找效率，查找的平均时间复杂度可以达到 O(logN) 。

与 list 类似，当用户对 set 进行插入删除后，原先的迭代器依然有效，但被删除的那个元素是个特例，既然都已经被删除了，它之前的迭代器当然失效了。

set的使用

set 如同之前的序列式容器，有众多接口，这些接口实现的功能和之前的序列式容器类似。我们可以在它的有关文档中看得到。如下是部分接口的操作的演示：

• 插入
  
  随机插入非有序序列，set内部自动排好了序。

• 查找
  查找接口若找到返回找到的那个数据的迭代器，没找到则返回一个指向随机数的迭代器。
  
  查找一个不存在的值，返回的指向随机数的迭代器，故该接口要求用户所要查找的值必须在。

下图找一个存在的值。

• 修改
  

可以看到，set 内的值不允许修改，因为修改会影响底层红黑树的结构，而红黑树的调整则需要高昂的代价。

set算法

STL 中有关 set 给出了四种算法，分别是交集，并集， 差集，对称差集。但是此处的 set 不同于数学中的集合。数学中的集合允许元素以任意次数、任意次序出现，但此处的不允许元素重复出现，而且所有元素按序出现。这四种算法处理的结构也是有序的。

有关 set 的四个算法提供两个版本。版本一接收五个迭代器，前四个分别两两确定一个集合区间，还有一个迭代器用于处理运算的结果。版本二和版本一的不同之处在于，版本二可以自定义元素的比较方式（模板参数定制比较器）。它们的返回值相同，都返回运算结果的尾端迭代器。

这四个算法虽然以 set 命名，但实际上也不局限于 set, 只要是元素有序出现，且提供迭代器的容器都可以用此算法，这一点才稍后的演示中可以看到。

交集 `SetIntersection（）

交集算法用于求出同时存在于集合1 和 集合2 中的元素。下面是它的演示（自定义实现的，暂且不给参数五，在函数内部将处理结果打印）：

代码细节：

//求交集   s1 交 s2
template<class InputIterator1, class InputIterator2>
void SetIntersection(InputIterator1 first1, InputIterator1 last1,
            InputIterator2 first2, InputIterator2 last2)
{
    while (first1 != last1 && first2 != last2){
        if (*first1 < *first2)
            ++first1;
        else if (*first1 > *first2)
            ++first2;
        else{//交集只有相等才处理
            cout << *first1 << " ";
            ++first1;
            ++first2;
        }
    }
}

并集 SetUnion()

并集将 s1 集合和 s2 集合中所有元素合并到一起，相同的元素只在并集中出现一次。下面是操作演示：

代码细节：

//求并集   s1 并 s2
template<class InputIterator1, class InputIterator2>
void SetUnion(InputIterator1 first1, InputIterator1 last1, 
        InputIterator2 first2, InputIterator2 last2)
{
    while (first1 != last1 && first2 != last2){
        if (*first1 < *first2){
            cout << *first1 << " ";
            ++first1;
        }
        else if (*first1 > *first2){
            cout << *first2 << " ";
            ++first2;
        }
        else{//两集合相等则只打印一次
            cout << *first1 << " ";
            ++first1;
            ++first2;
        }
    }
    //处理没有走到结尾的集合
    while (first1 != last1){
        cout << *first1 << " ";
        ++first1;
    }

    while (first2 != last2){
        cout << *first2 << " ";
        ++first2;
    }
}

差集 SetDifference()

差集的结果是：在 s1 中出现但没有在 s2 中出现的数据。下面是操作演示：

代码细节：

//求差集 s1 - s2
template<class InputIterator1, class InputIterator2>
void SetDifference(InputIterator1 first1, InputIterator1 last1,
    InputIterator2 first2, InputIterator2 last2)
{
    while (first1 != last1 && first2 != last2){
        if (*first1 == *first2){
            ++first1;
            ++first2;
        }
        else if (*first1 > *first2)//
            ++first2;
        else{//说明*first只在s1中出现，没有在s2中出现
            cout << *first1 << " ";
            ++first1;
        }
    }
}

对称差集 SetSymmetricDifference()

对称差集的结果是：只出现在 s1 但没出现在 s2 加 只出现在 s2 但没出现在 s1 中的数据。下面是操作演示：

代码细节：

//求对称差集，出现在s1但不出现在s2中 + 出现在s2但不出现在s1 (s1-s2) 并 (s2 -s1)
template<class InputIterator1, class InputIterator2>
void SetSymmetricDifference(InputIterator1 first1, InputIterator1 last1,//set_symmetric_difference
    InputIterator2 first2, InputIterator2 last2)
{
    while (first1 != last1 && first2 != last2){
        if (*first1 < *first2){//说明只在s1中出现，没在s2中出现
            cout << *first1 << " ";
            ++first1;
        }
        else if (*first1 > *first2){//说明只在s2中出现，没在s1中出现
            cout << *first2 << " ";
            ++first2;
        }
        else{//说明*first在s1和s2中都出现则不处理
            ++first2;
            ++first1;
        }
    }

    while (first1 != last1){
        cout << *first1 << " ";
        ++first1;
    }

    while (first2 != last2){
        cout << *first2 << " ";
        ++first2;
    }
}

处理其它有序容器

如上图所示，我们随机分别给两个 Vector 插入两组有序数据，再调用集合的四个算法处理，发现和 set 的一样，由此我们得出结论，set 的算法也可以应用于其它有序容器。

---

【作者：果冻 http://blog.csdn.net/jelly_9】
—— 完！