不造轮子之STL中集合的交并补

程序员的园

发布于 2024-09-29 13:57:38

480

发布于 2024-09-29 13:57:38

文章被收录于专栏：程序员的园——原创文章

在日常的开发中，常涉及到容器的常见操作，如查找、删除、排序等，C++ STL提供了丰富的算法库，可以方便的完成这些操作。为了避免重复造轮子，同时为了提高效率，了解常见的STL算法是非常有必要的。

两个容器涉及到求其交并补级，C++ STL提供了相应的算法，本文将介绍这些算法的使用方法。

0. 排序——std::sort

在求交并补之前，需要保证两个容器是有序的，因此需要先对容器进行排序。std::sort算法可以对一个范围内的元素进行排序，其函数原型如下：

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

其中，first和last表示要排序的范围的起始和结束迭代器。std::sort算法将范围内的元素按照升序进行排序。

#include <vector>
#include <algorithm>
int main() {
 std::vector v = {5, 3, 1, 4, 2}; // 未排序
 std::sort(v.begin(), v.end()); // 排序
 for (int i : v) {
 std::cout << i << " ";
 } // 输出：1 2 3 4 5
 return 0;
}

1. 合并——std::merge

std::merge算法将两个有序的输入范围合并到一个有序的输出范围中（如果存在的话会含有重复元素）。其函数原型如下：

template< class InputIt1, class InputIt2, class OutputIt, class Compare >
OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );

其中，first1和last1表示第一个输入范围的起始和结束迭代器，first2和last2表示第二个输入范围的起始和结束迭代器，d_first表示输出范围的起始迭代器，comp表示比较函数。std::merge算法将两个输入范围合并到输出范围中，返回输出范围的结束迭代器。

#include <vector>
#include <algorithm>

int main() 
{
 std::vector v1 = {1, 3, 5, 7, 9};
 std::vector v2 = {2, 4, 5, 6, 8, 10};
 std::vector v3(v1.size() + v2.size());
 std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
 for (int i : v3) 
 {
 std::cout << i << " ";
 }
 return 0;
} // 输出：1 2 3 4 5 5 6 7 8 9 10

2. 交集——std::set_intersection

std::set_intersection算法计算两个有序输入范围的交集，并将结果存储到输出范围中。其函数原型如下：

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_intersection( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );

其中，first1和last1表示第一个输入范围的起始和结束迭代器，first2和last2表示第二个输入范围的起始和结束迭代器，d_first表示输出范围的起始迭代器。std::set_intersection算法将两个输入范围中相同的元素存储到输出范围中，返回输出范围的结束迭代器。

#include <vector>
#include <algorithm>
int main() {
 std::vector v1 = {1, 3, 5, 7, 9};
 std::vector v2 = {2, 3, 5, 6, 8, 9};
 std::vector v3(std::min(v1.size(), v2.size()));
 std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
 for (int i : v3) {
 std::cout << i << " ";
 } // 输出：3 5 9
}

3. 并集——std::set_union

std::set_union算法计算两个有序输入范围的并集(不含重复元素)，并将结果存储到输出范围中。其函数原型如下：

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_union( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );

其中，first1和last1表示第一个输入范围的起始和结束迭代器，first2和last2表示第二个输入范围的起始和结束迭代器，d_first表示输出范围的起始迭代器。std::set_union算法将两个输入范围中的所有元素存储到输出范围中，返回输出范围的结束迭代器。

#include <vector>
#include <algorithm>
int main() 
{
 std::vector v1 = {1, 3, 5, 7, 9};
 std::vector v2 = {2, 3, 5, 6, 8, 10};
 std::vector v3(v1.size() + v2.size());
 std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
 for (int i : v3) 
 {
 std::cout << i << " ";
 } // 输出：1 2 3 5 6 7 8 9 10
 return 0;
}

4. 补集——std::set_difference

std::set_difference算法计算两个有序输入范围的差集，并将结果存储到输出范围中。其函数原型如下：

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );

其中，first1和last1表示第一个输入范围的起始和结束迭代器，first2和last2表示第二个输入范围的起始和结束迭代器，d_first表示输出范围的起始迭代器。std::set_difference算法将第一个输入范围中不在第二个输入范围中的元素存储到输出范围中，返回输出范围的结束迭代器。

#include <vector>
#include <algorithm>
int main() 
{
 std::vector v1 = {1, 3, 5, 7, 9};
 std::vector v2 = {2, 3, 5, 6, 8, 9};
 std::vector v3(std::min(v1.size(), v2.size()));
 std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
 for (int i : v3) 
 {
 std::cout << i << " ";
 } // 输出：1 7
}

总结

std::merge、std::set_intersection、std::set_union和std::set_difference是C++标准库中提供的四个算法，用于计算两个有序输入范围的合并、交集、并集和差集。这些算法可以方便地处理有序数据，并返回结果。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-09-29，如有侵权请联系 cloudcommunity@tencent.com 删除

存储