STL求交集,并集的算法
时间: 2023-07-10 14:13:56 浏览: 73
STL中提供了求集合交集、并集的算法,分别是`std::set_intersection`和`std::set_union`。
`std::set_intersection`的函数原型如下:
```cpp
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_union`的函数原型如下:
```cpp
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`表示输出结果的起始迭代器。
示例代码如下:
```cpp
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> intersection(v1.size() + v2.size()); // 交集
std::vector<int> uni(v1.size() + v2.size()); // 并集
// 求交集
auto it = std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), intersection.begin());
intersection.resize(it - intersection.begin());
// 求并集
it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), uni.begin());
uni.resize(it - uni.begin());
std::cout << "Intersection:";
for (auto i : intersection) {
std::cout << " " << i;
}
std::cout << std::endl;
std::cout << "Union:";
for (auto i : uni) {
std::cout << " " << i;
}
std::cout << std::endl;
return 0;
}
```
输出结果为:
```
Intersection: 3 4 5
Union: 1 2 3 4 5 6 7
```