STL学习之set相关算法

    STL一共提供了四种与set（集合）相关的算法，分别是并集（union）、交集（intersection）、差集（difference）、对称差集（symmetric difference）。
    四个算法所接受的set，必须是有序区间，元素值得重复出现。换句话说，它们可以接受STL的set/multiset容器作为输入空间。
    本节四个算法都至少有4个参数，分布表示两个set的区间。以下所有说明都是以S1代表第一个区间[first1, last1)，以S2代表第二个区间[first2, last2)。每一个set算法都提供两个版本，第二个版本允许用户指定“a < b”的意义，因为这些算法判断两个元素是否相等的依据，完全靠“小于”运算。

1、运用实例

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>

using namespace std;

template <class T>
struct display
{
    void operator() (const T&a)
    {
        cout << a << " ";
    }
};

int main()
{
    int ia1[6] = {1, 3, 5, 6, 9, 11};
    int ia2[7] = {1, 1, 2, 3, 5, 8, 13};

    multiset<int> s1(ia1, ia1 + 6);
    multiset<int> s2(ia2, ia2 + 7);

    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:" << endl;
    set_union(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));
    cout << endl;

    first1 = s1.begin();
    last1 = s1.end();
    cout << "intersection of s1 and s2:" << endl;
    set_intersection(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));
    cout << endl;

    first1 = s1.begin();
    last1 = s1.end();
    cout << "difference of s1 and s2:" << endl;
    set_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));
    cout << endl;


    first1 = s1.begin();
    last1 = s1.end();
    cout << "symmetric difference of s1 and s2:" << endl;
    set_symmetric_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));
    cout << endl;


    first1 = s1.begin();
    last1 = s1.end();
    first2 = s2.begin();
    last2 = s2.end();
    cout << "difference of s1 and s2:" << endl;
    set_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}

    运行结果如下所示。
    

2、算法讲解
    （1）set_union
    算法set_union可构造s1、s2之并集。也就是说，它能构造出集合，此集合含有s1或s2内的每一个元素。s1、s2及其并集都是以排序区间表示。返回值为一个迭代器，指出输出区间的尾端。
    由于s1和s2内的每个元素都不需要唯一，因此，如果某个值在s1出现n次，在s2中出现m次，那么该值在输出区间中会出现max（n，m）次，其中n个来自s1，其余来自s2。
    set_union是一种稳定操作，意思是输入区间内的每个元素的相对顺序都不会改变。
    set_union有两个版本，差别在于如何定义某个元素小于另一个元素。第一个版本使用operator<进行比较，第二版本采用仿函数comp进行比较。

template <class InputInterator1, class InputInterator2, class OutputInterator>
OutputInterator set_union(InputInterator1 first1, InputInterator1 last1, InputInterator2 first2, InputInterator2 last2, OutputInterator result)
{
    //当两个区间都未到达尾端时，执行以下操作
    while(first1 != last1 && first2 != last2)
    {
        if(*first1 < *first2)
        {
            *result =*first1;
            first1++;
        }
        else if(*first2 < *first1)
        {
            *result = *first2;
            first2++;
        }
        else
        {
            *result = *first1;
            first1++;
            first2++;
        }
        result++;
    }

    //只要两个区间之一有一区到达尾端，就结束上述到达while循环
    //以下是尚未到达尾端的区间的所有剩余元素拷贝到目的端
    //此刻的[first1, last1)和[first2, last2)之中至少有一个是空白区间
    copy(first2, last2, copy(first1, last1, result));
}

    （2）set_intersection
    算法set_intersection可构造s1、s2的交集。也就是说，它能构造集合，该集合中含有同时出现于s1和s2内对每个元素。s1、s2及其交集都是以排序区间表示。返回值是一个迭代器，指向输出区间的末尾。
    同set_union。

template <class InputInterator1, class InputInterator2, class OutputInterator>
OutputInterator set_intersection(InputInterator1 first1, InputInterator1 last1, InputInterator2 first2, InputInterator2 last2, OutputInterator result)
{
    //当两个区间都未到达尾端时，执行以下操作
    while(first1 != last1 && first2 != last2)
    {
        if(*first1 < *first2)
        {
            first1++;
        }
        else if(*first2 < *first1)
        {
            first2++;
        }
        else
        {
            *result = *first1;
            first1++;
            first2++;
        }
        result++;
    }

    return result;
}

    （3）set_difference
    算法set_difference可构造s1、s2之差集。也就是说，它可以构造一个集合，此集合内含“出现于s1但不出现于s2”的每一个元素。s1、s2及其差集都是以排序区间表示。返回值为一个迭代器，指向输出区间的尾端。

//差集：求存在于[first1, last1)且不存在于[first2, last2)的所有元素
//注意：set是一种sorted range，这是以下算法的前提
template <class InputInterator1, class InputInterator2, class OutputInterator>
OutputInterator set_difference(InputInterator1 first1, InputInterator1 last1, InputInterator2 first2, InputInterator2 last2, OutputInterator result)
{
    //当两个区间都未到达尾端时，执行以下操作
    while(first1 != last1 && first2 != last2)
    {
        //在两个区间内分别移动迭代器。当第一个区间的元素等于第二个区间的元素（表示此值同时存在于两区间）
        //就让两区间同时前进；当第一个区间的元素大于第二个区间的元素，就让第二个区间前进；有了这两种处理，
        //就保证当第一个区间的元素小于第二个区间的元素时，第一个区间的元素只存在于第一个区间中，不存在于
        //第二个区间中，于是将它记录于目标区间中
        if(*first1 < *first2)
        {
            *result = *first1;
            result++;
            first1++;
        }
        else if(*first2 < *first1)
        {
            first2++;
        }
        else
        {
            first1++;
            first2++;
        }
    }

    return copy(first1, last1, result);
}

    （4）set_symmetric_difference
    算法set_symmetric_difference可构造s1、s2之对称差集。也就是说，它能构造出集合，此集合内包含“出现于s1但不出现于s2”以及“出现于s2但不出现于s1”的每一个元素。

template <class InputInterator1, class InputInterator2, class OutputInterator>
OutputInterator set_symmetric_difference(InputInterator1 first1, InputInterator1 last1, InputInterator2 first2, InputInterator2 last2, OutputInterator result)
{
    //当两个区间都未到达尾端时，执行以下操作
    while(first1 != last1 && first2 != last2)
    {
        //在两个区间内分别移动迭代器。
        //当两区间内的元素相等，就让两区间同时前进；
        //当两区间内的元素不等，就记录较小值于目标中，并令较小值所在区间前进
        if(*first1 < *first2)
        {
            *result = *first1;
            result++;
            first1++;
        }
        else if(*first2 < *first1)
        {
            *result = *first2;
            result++;
            first2++;
        }
        else
        {
            first1++;
            first2++;
        }
    }

    return copy(first2, last2, copy(first1, last1, result));
}