当前位置：首页 > news >正文

【C++提高编程-11】----C++ STL常用集合算法

news 来源：原创 2024/9/29 13:21:03

🎩 欢迎来到技术探索的奇幻世界👨‍💻

📜 个人主页：@一伦明悦-CSDN博客

✍🏻 作者简介： C++软件开发、Python机器学习爱好者

🗣️ 互动与支持：💬评论 👍🏻点赞 📂收藏 👀关注+

如果文章有所帮助，欢迎留下您宝贵的评论，

点赞加收藏支持我，点击关注，一起进步！

前言

在C++ STL（标准模板库）中，有几个常用的集合算法可以用来操作集合（如std::set或std::unordered_set）：

正文

01-常用集合算法之set_intersection用法

std::set_intersection是一个C++标准库中用于计算两个已排序范围的交集的算法。它将交集的结果存储在第三个范围中，这个范围必须事先被分配足够的空间来存储结果。

以下是std::set_intersection的典型用法和详细解释：
#include <algorithm> // for std::set_intersection
#include <vector>    // for std::vector
#include <iostream>  // for outputint main() {// 定义两个已排序的输入集合std::vector<int> set1 = {1, 2, 3, 4, 5};std::vector<int> set2 = {3, 4, 5, 6, 7};// 定义一个输出集合，用于存储交集结果std::vector<int> intersection;// 使用 std::back_inserter 来避免手动管理容量// std::set_intersection 会根据需要自动增加 intersection 的容量std::set_intersection(set1.begin(), set1.end(),set2.begin(), set2.end(),std::back_inserter(intersection));// 输出交集结果for (int num : intersection) {std::cout << num << ' ';}std::cout << std::endl;return 0;
}
在上面的代码中，我们定义了两个已排序的std::vector集合set1和set2。然后我们使用std::set_intersection算法来计算它们的交集，并将结果存储在另一个std::vector``intersection中。

std::set_intersection的参数解释：

set1.begin()和set1.end()：这些是set1的开始和结束迭代器，它们定义了第一个输入范围的边界。

set2.begin()和set2.end()：这些是set2的开始和结束迭代器，它们定义了第二个输入范围的边界。

std::back_inserter(intersection)：这是一个输出

下面给出具体代码分析应用过程：

这段代码演示了如何使用 std::set_intersection 算法来计算两个向量 v1 和 v2 的交集，并将结果存储在目标向量 vTarget 中。

让我们逐步解释这段代码：

头文件包含和命名空间：
```
#include <vector>
#include <algorithm>
#include <iostream> // 没有在代码中显示，但通常需要用来输出
using namespace std;
```
这些头文件包含了向量 (vector) 和算法 (algorithm) 所需的标准库内容，并使用了 std 命名空间。
自定义函数对象 myPrint：
```
class myPrint
{
public:void operator()(int val){cout << val << " ";}
};
```
myPrint 是一个函数对象类，它定义了 operator()，用于打印整数值。这个类在后面的代码中被用来遍历并打印向量的元素。

测试函数 test01：

void test01()
{vector<int> v1;vector<int> v2;// 向 v1 和 v2 中添加元素for (int i = 0; i < 10; i++){v1.push_back(i);      // v1 包含 0 到 9v2.push_back(i + 5);  // v2 包含 5 到 14}vector<int> vTarget;// 取两个向量中较小的大小来设置 vTarget 的大小vTarget.resize(min(v1.size(), v2.size()));// 使用 std::set_intersection 计算交集，并将结果存储在 vTarget 中vector<int>::iterator itEnd =set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());// 使用自定义的 myPrint 函数对象打印 vTarget 中的元素for_each(vTarget.begin(), itEnd, myPrint());cout << endl;
}

test01 函数首先创建两个向量 v1 和 v2，分别包含了一系列整数。
v1 包含了 {0, 1, 2, ..., 9}，v2 包含了 {5, 6, 7, ..., 14}。
vTarget 向量被预先调整大小为 min(v1.size(), v2.size())，以确保足够存储计算得到的交集。
set_intersection 函数被调用来计算 v1 和 v2 的交集，结果存储在 vTarget 中。返回值 itEnd 是输出范围的尾后迭代器。
for_each 算法结合 myPrint 函数对象，迭代输出 vTarget 中的元素。

主函数 main：
```
int main() {test01();system("pause");return 0;
}
```
- main 函数调用 test01 来执行测试，并在程序结束时暂停控制台，以便查看输出结果。

总结：这段代码展示了如何使用 std::set_intersection 计算两个向量的交集，并使用自定义函数对象来打印结果。这种方法利用了 C++ 标准库中的算法和容器，展示了如何高效地处理集合操作。


#include <vector>
#include <algorithm>
class myPrint
{
public:void operator()(int val){cout << val << " ";}
};
void test01()
{vector<int> v1;vector<int> v2;for (int i = 0; i < 10; i++){v1.push_back(i);v2.push_back(i + 5);}vector<int> vTarget;//取两个里面较小的值给目标容器开辟空间vTarget.resize(min(v1.size(), v2.size()));//返回目标容器的最后一个元素的迭代器地址vector<int>::iterator itEnd =set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout << endl;
}
int main() {test01();system("pause");return 0;
}

02-常用集合算法之set_union用法

std::set_union 是另一个 C++ 标准库中的算法，用于计算两个已排序集合的并集。它会将两个输入集合的并集存储在第三个容器中，这个容器必须足够大以容纳所有结果。

以下是 std::set_union 的典型用法和详细解释：
#include <algorithm> // for std::set_union
#include <vector>    // for std::vector
#include <iostream>  // for outputint main() {// 定义两个已排序的输入集合std::vector<int> set1 = {1, 2, 3, 4, 5};std::vector<int> set2 = {3, 4, 5, 6, 7};// 定义一个输出集合，用于存储并集结果std::vector<int> unionResult(set1.size() + set2.size());// 使用 std::set_union 计算并集，并返回结束迭代器auto itEnd = std::set_union(set1.begin(), set1.end(),set2.begin(), set2.end(),unionResult.begin());// 调整输出集合大小，仅包含有效元素unionResult.resize(itEnd - unionResult.begin());// 输出并集结果for (int num : unionResult) {std::cout << num << ' ';}std::cout << std::endl;return 0;
}
在这段代码中，我们展示了如何使用 std::set_union 算法计算两个已排序向量 set1 和 set2 的并集，并将结果存储在另一个向量 unionResult 中。

std::set_union 的参数解释：

输入集合的迭代器范围：

set1.begin() 和 set1.end()：定义第一个输入集合 set1 的开始和结束迭代器。
set2.begin() 和 set2.end()：定义第二个输入集合 set2 的开始和结束迭代器。

输出集合的目标范围：

unionResult.begin()：指定用于存储结果的输出集合的起始位置迭代器。

返回值：

std::set_union 函数返回一个迭代器，指向输出范围的结束位置。这个迭代器可以帮助我们调整输出容器的大小，使其仅包含有效的并集元素。

代码解析：

定义输入集合：set1 和 set2 是已排序的向量，分别包含 {1, 2, 3, 4, 5} 和 {3, 4, 5, 6, 7}。

定义输出集合：unionResult 的大小被设定为 set1.size() + set2.size()，以确保足够大来容纳所有可能的并集元素。

计算并集：std::set_union 函数被调用来计算 set1 和 set2 的并集，并将结果存储在 unionResult 中。结束迭代器 itEnd 标志着输出范围的末尾。

调整输出集合大小：通过 unionResult.resize(itEnd - unionResult.begin())，我们调整 unionResult 的大小，使其仅包含实际计算得到的并集元素。

输出结果：最后使用简单的循环输出来展示计算得到的并集。

总结来说，std::set_union 是一个有用的算法，用于合并两个已排序集合，其操作简便高效，适用于各种需要处理集合并集的情况。

下面给出具体代码分析应用过程：

这段代码演示了如何使用 std::set_union 算法来计算两个向量 v1 和 v2 的并集，并将结果存储在目标向量 vTarget 中。

让我们逐步解释这段代码：

头文件包含和命名空间：
```
#include <vector>
#include <algorithm>
using namespace std;
```
这些头文件包含了向量 (vector) 和算法 (algorithm) 所需的标准库内容，并使用了 std 命名空间。
自定义函数对象 myPrint：
```
class myPrint
{
public:void operator()(int val){cout << val << " ";}
};
```
myPrint 是一个函数对象类，它定义了 operator()，用于打印整数值。这个类在后面的代码中被用来遍历并打印向量的元素。

测试函数 test01：

void test01()
{vector<int> v1;vector<int> v2;// 向 v1 和 v2 中添加元素for (int i = 0; i < 10; i++){v1.push_back(i);      // v1 包含 0 到 9v2.push_back(i + 5);  // v2 包含 5 到 14}vector<int> vTarget;// 取两个容器的和给目标容器开辟空间vTarget.resize(v1.size() + v2.size());// 使用 std::set_union 计算并集，并将结果存储在 vTarget 中vector<int>::iterator itEnd =set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());// 使用自定义的 myPrint 函数对象打印 vTarget 中的元素for_each(vTarget.begin(), itEnd, myPrint());

#include <vector>
#include <algorithm>class myPrint
{
public:void operator()(int val){cout << val << " ";}
};
void test01()
{vector<int> v1;vector<int> v2;for (int i = 0; i < 10; i++) {v1.push_back(i);v2.push_back(i + 5);}vector<int> vTarget;//取两个容器的和给目标容器开辟空间vTarget.resize(v1.size() + v2.size());//返回目标容器的最后一个元素的迭代器地址vector<int>::iterator itEnd =set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout << endl;
}
int main() {test01();system("pause");return 0;
}

03-常用集合算法之set_difference用法

std::set_difference 是另一个C++标准库中的算法，用于计算两个已排序集合的差集。它会从第一个输入集合中移除与第二个输入集合相同的元素，并将结果存储在第三个容器中。以下是 std::set_difference 的典型用法和详细解释：
#include <algorithm> // for std::set_difference
#include <vector>    // for std::vector
#include <iostream>  // for outputint main() {// 定义两个已排序的输入集合std::vector<int> set1 = {1, 2, 3, 4, 5};std::vector<int> set2 = {3, 4, 5, 6, 7};// 定义一个输出集合，用于存储差集结果std::vector<int> differenceResult(set1.size());// 使用 std::set_difference 计算差集，并返回结束迭代器auto itEnd = std::set_difference(set1.begin(), set1.end(),set2.begin(), set2.end(),differenceResult.begin());// 调整输出集合大小，仅包含有效元素differenceResult.resize(itEnd - differenceResult.begin());// 输出差集结果for (int num : differenceResult) {std::cout << num << ' ';}std::cout << std::endl;return 0;
}
std::set_difference 的参数解释：

输入集合的迭代器范围：

set1.begin() 和 set1.end()：定义第一个输入集合 set1 的开始和结束迭代器。
set2.begin() 和 set2.end()：定义第二个输入集合 set2 的开始和结束迭代器。

输出集合的目标范围：

differenceResult.begin()：指定用于存储结果的输出集合的起始位置迭代器。

返回值：

std::set_difference 函数返回一个迭代器，指向输出范围的结束位置。这个迭代器可以帮助我们调整输出容器的大小，使其仅包含有效的差集元素。

代码解析：

定义输入集合：set1 和 set2 是已排序的向量，分别包含 {1, 2, 3, 4, 5} 和 {3, 4, 5, 6, 7}。

定义输出集合：differenceResult 的大小被设定为 set1.size()，以确保足够大来容纳所有可能的差集元素。

计算差集：std::set_difference 函数被调用来计算 set1 和 set2 的差集，并将结果存储在 differenceResult 中。结束迭代器 itEnd 标志着输出范围的末尾。

调整输出集合大小：通过 differenceResult.resize(itEnd - differenceResult.begin())，我们调整 differenceResult 的大小，使其仅包含实际计算得到的差集元素。

输出结果：最后使用简单的循环输出来展示计算得到的差集。

总结来说，std::set_difference 是一个有用的算法，用于从一个已排序集合中移除另一个集合中存在的元素，其操作简便高效，适用于各种需要处理集合差集的情况。

下面给出具体代码分析应用过程：

这段代码展示了如何使用 std::set_difference 算法来计算两个已排序向量 v1 和 v2 的差集，并将结果存储在目标向量 vTarget 中。

让我们逐步解释这段代码：

头文件包含和命名空间：
```
#include <vector>
#include <algorithm>
#include <iostream>  // 这里应该包含头文件以便使用 cout
using namespace std;
```
这些头文件包含了向量 (vector) 和算法 (algorithm) 所需的标准库内容，以及输出 (cout) 所需的头文件。
自定义函数对象 myPrint：
```
class myPrint
{
public:void operator()(int val){cout << val << " ";}
};
```
myPrint 是一个函数对象类，用于打印整数值。它在后面的代码中被用来遍历并打印向量的元素。

测试函数 test01：

void test01()
{vector<int> v1;vector<int> v2;// 向 v1 和 v2 中添加元素for (int i = 0; i < 10; i++){v1.push_back(i);      // v1 包含 0 到 9v2.push_back(i + 5);  // v2 包含 5 到 14}vector<int> vTarget;// 取两个向量中较大的大小作为目标容器的大小vTarget.resize(max(v1.size(), v2.size()));// 使用 std::set_difference 计算 v1 和 v2 的差集，并将结果存储在 vTarget 中cout << "v1与v2的差集为： " << endl;vector<int>::iterator itEnd =set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());// 使用自定义的 myPrint 函数对象打印 vTarget 中的元素for_each(vTarget.begin(), itEnd, myPrint());cout << endl;// 再次使用 set_difference 计算 v2 和 v1 的差集，并存储在 vTarget 中cout << "v2与v1的差集为： " << endl;itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());// 使用自定义的 myPrint 函数对象打印 vTarget 中的元素for_each(vTarget.begin(), itEnd, myPrint());cout << endl;
}

向量初始化：v1 和 v2 分别初始化为 {0, 1, 2, ..., 9} 和 {5, 6, 7, ..., 14}。
目标向量初始化：vTarget 通过 resize 函数调整为能容纳 v1 和 v2 中最大元素数量的大小。
第一次差集计算：使用 set_difference 计算 v1 和 v2 的差集，并将结果存储在 vTarget 中，通过 for_each 和 myPrint 打印差集元素。
第二次差集计算：再次使用 set_difference 计算 v2 和 v1 的差集，并覆盖 vTarget，再次打印差集元素。

主函数 main：
```
int main() {test01();system("pause");return 0;
}
```
- 调用 test01 函数来执行测试。
- 使用 system("pause") 来在控制台中暂停，以便查看输出结果。

这段代码通过 std::set_difference 演示了如何计算两个向量的差集，并通过自定义的函数对象来打印结果。

#include <vector>
#include <algorithm>
class myPrint
{
public:void operator()(int val){cout << val << " ";}
};
void test01()
{vector<int> v1;vector<int> v2;for (int i = 0; i < 10; i++) {v1.push_back(i);v2.push_back(i + 5);}vector<int> vTarget;//取两个里面较大的值给目标容器开辟空间vTarget.resize(max(v1.size(), v2.size()));//返回目标容器的最后一个元素的迭代器地址cout << "v1与v2的差集为： " << endl;vector<int>::iterator itEnd =set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout << endl;cout << "v2与v1的差集为： " << endl;itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout << endl;
}
int main() {test01();system("pause");return 0;
}

总结

std::set_intersection（求交集）：
std::set_intersection算法用于计算两个已排序范围的交集，并将结果存储到另一个输出迭代器指定的范围中。
示例用法：
std::set<int> set1 = {1, 2, 3, 4, 5};
std::set<int> set2 = {3, 4, 5, 6, 7};
std::vector<int> intersection;std::set_intersection(set1.begin(), set1.end(),set2.begin(), set2.end(),std::back_inserter(intersection));// intersection 现在包含 {3, 4, 5}
std::set_union（求并集）：
std::set_union算法用于计算两个已排序范围的并集，并将结果存储到另一个输出迭代器指定的范围中。
示例用法：
std::set<int> set1 = {1, 2, 3, 4, 5};
std::set<int> set2 = {3, 4, 5, 6, 7};
std::vector<int> uni;std::set_union(set1.begin(), set1.end(),set2.begin(), set2.end(),std::back_inserter(uni));// uni 现在包含 {1, 2, 3, 4, 5, 6, 7}
std::set_difference（求差集）：
std::set_difference算法用于计算第一个已排序范围中存在但不在第二个已排序范围中的元素，并将结果存储到另一个输出迭代器指定的范围中。
示例用法：
std::set<int> set1 = {1, 2, 3, 4, 5};
std::set<int> set2 = {3, 4, 5, 6, 7};
std::vector<int> difference;std::set_difference(set1.begin(), set1.end(),set2.begin(), set2.end(),std::back_inserter(difference));// difference 现在包含 {1, 2}
这些算法要求其输入范围是已排序的。如果输入集合不是已排序的，你需要先对它们进行排序，然后再应用这些算法。