2016-05-07

STL中常用的集合操作函数

在实际的编程工作中，经常需要对两个集合进行各种操作，例如取交集、取并集等。在C++中，完全不需要自己来实现这些操作，因为STL已经为我们准备好了这些常用的集合操作函数。

排序

STL的集合操作都基于排序区间，所以在调用这些函数之前要对集合排序。最常用的排序函数是std::sort，它的用法很简单，只要传入一对迭代器即可，如下所示：

std::vector<int> vector{ 8, 3, 5, 9, 2 };
std::sort(vector.begin(), vector.end());
//vector的元素序列是 { 2, 3, 5, 8, 9 }

std:sort默认使用<操作符来比较元素，当然也可以使用自定义的比较函数来改变排序规则。例如，下面的例子使用>操作符比较元素：

std::vector<int> vector{ 8, 3, 5, 9, 2 };
std::sort(vector.begin(), vector.end(), [](int v1, int v2) {
    return v1 > v2;
});
//vector的元素序列是 { 9, 8, 5, 3, 2 }

与std::sort一样，下文介绍的所有集合操作函数默认都使用<操作符来比较元素，而且都可以在最后一个参数指定自定义的比较函数，这一点不再提及。但要注意的是，排序和集合操作使用的比较函数必须要一致，否则会有问题。另外，由于集合操作函数的输入都基于排序区间，所以这些函数的输出结果也是有序的，这点也不再提及。

STL保证std::sort的时间复杂度是O(N·log(N))，其中N为区间长度。

交集

对两个集合取交集可以使用std::set_intersection，该函数需要两对迭代器，以及一个输出迭代器，如下所示：

std::vector<int> vector1{ 1, 3, 4, 6, 9 };
std::vector<int> vector2{ 2, 4, 6, 8, 9 };
std::vector<int> result;
std::set_intersection(
    vector1.begin(), vector1.end(),  //第一个区间
    vector2.begin(), vector2.end(),  //第二个区间
    std::back_inserter(result)
);
//result的元素序列是 { 4, 6, 9 }

两个输入区间内的元素不会被修改，操作结果通过输出迭代器复制到另一个集合中。STL集合操作函数的用法都高度一致，下文其它函数的用法也是这样，仅仅是语义上不同。

STL保证std::set_intersection至多进行2·(N1+N2-1)次比较，其中N1是第一个区间的长度，N2是第二个区间的长度（N1和N2的定义下同）。

并集

对两个集合取并集可以使用std::set_union，如下所示：

std::vector<int> vector1{ 1, 3, 4, 6, 9 };
std::vector<int> vector2{ 2, 4, 6, 8, 9 };
std::vector<int> result;
std::set_union(
    vector1.begin(), vector1.end(),  //第一个区间
    vector2.begin(), vector2.end(),  //第二个区间
    std::back_inserter(result)
);
//result的元素序列是 { 1, 2, 3, 4, 6, 8, 9 }

STL保证std::set_union至多进行2·(N1+N2-1)次比较。

差集

对两个集合取差集可以使用std::set_difference，如下所示：

std::vector<int> vector1{ 1, 3, 4, 6, 9 };
std::vector<int> vector2{ 2, 4, 6, 8, 9 };
std::vector<int> result;
std::set_difference(
    vector1.begin(), vector1.end(),  //第一个区间
    vector2.begin(), vector2.end(),  //第二个区间
    std::back_inserter(result)
);
//result的元素序列是 { 1, 3 }

std::set_difference从第一个区间去除第二个区间的元素。

STL保证std::set_difference至多进行2·(N1+N2-1)次比较。

合并

合并两个集合可以使用std::merge，如下所示：

std::vector<int> vector1{ 1, 3, 4, 6, 9 };
std::vector<int> vector2{ 2, 4, 6, 8, 9 };
std::vector<int> result;
std::merge(
    vector1.begin(), vector1.end(),  //第一个区间
    vector2.begin(), vector2.end(),  //第二个区间
    std::back_inserter(result)
);
//result的元素序列是 { 1, 2, 3, 4, 4, 6, 6, 8, 9, 9 }

与std::set_union不同，std::merge不会去除重复的元素。

STL保证std::merge至多进行N1+N2-1次比较。

C++