C++ STL常用算法之常用集合算法

常用集合算法

学习目标:

• 掌握常用的集合算法

算法简介:

• set_intersection // 求两个容器的交集

• set_union // 求两个容器的并集

• set_difference // 求两个容器的差集

set_intersection

功能描述:

• 求两个容器的交集

函数原型:

• set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  • beg1：容器1开始迭代器

  • end1：容器1结束迭代器

  • beg2：容器2开始迭代器

  • end2：容器2结束迭代器

  • dest：目标容器开始迭代器

  • 注意：两个集合必须是有序序列，求交集的两个集合必须的有序序列

  • set_intersection返回值既是交集中最后一个元素的位置

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>using namespace std;int main() {// 创建两个有序的 vector 容器vector<int> v1 = {1, 2, 3, 4, 5};vector<int> v2 = {4, 5, 6, 7, 8};// 输出原始容器的内容cout << "v1: ";copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));cout << endl;cout << "v2: ";copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));cout << endl;// 创建一个目标容器来存储交集vector<int> v_intersection;// 使用 set_intersection 函数计算交集set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v_intersection));// 输出交集的内容cout << "交集: ";copy(v_intersection.begin(), v_intersection.end(), ostream_iterator<int>(cout, " "));cout << endl;return 0;
}

 

set_union

功能描述:

• 求两个集合的并集

函数原型:

• set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  • beg1：容器1开始迭代器

  • end1：容器1结束迭代器

  • beg2：容器2开始迭代器

  • end2：容器2结束迭代器

  • dest：目标容器开始迭代器

  • 注意：两个集合必须是有序序列，求并集的两个集合必须的有序序列

  • 目标容器开辟空间需要两个容器相加

  • set_union返回值既是并集中最后一个元素的位置

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>using namespace std;int main() {// 创建两个有序的 vector 容器vector<int> v1 = {1, 2, 3, 4, 5};vector<int> v2 = {4, 5, 6, 7, 8};// 输出原始容器的内容cout << "v1: ";copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));cout << endl;cout << "v2: ";copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));cout << endl;// 创建一个目标容器来存储并集vector<int> v_union;// 使用 set_union 函数计算并集set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v_union));// 输出并集的内容cout << "并集: ";copy(v_union.begin(), v_union.end(), ostream_iterator<int>(cout, " "));cout << endl;return 0;
}

 

set_difference

功能描述:

• 求两个集合的差集

函数原型:

• set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  • beg1：容器1开始迭代器

  • end1：容器1结束迭代器

  • beg2：容器2开始迭代器

  • end2：容器2结束迭代器

  • dest：目标容器开始迭代器

  • 注意：两个集合必须是有序序列，求差集的两个集合必须的有序序列

  • 目标容器开辟空间需要从两个容器取较大值

  • set_difference返回值既是差集中最后一个元素的位置

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>using namespace std;int main() {// 创建两个有序的 vector 容器vector<int> v1 = {1, 2, 3, 4, 5};vector<int> v2 = {4, 5, 6, 7, 8};// 输出原始容器的内容cout << "v1: ";copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));cout << endl;cout << "v2: ";copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));cout << endl;// 创建一个目标容器来存储差集vector<int> v_difference;// 使用 set_difference 函数计算差集 (v1 - v2)set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v_difference));// 输出差集的内容cout << "差集 (v1 - v2): ";copy(v_difference.begin(), v_difference.end(), ostream_iterator<int>(cout, " "));cout << endl;return 0;
}