• 【C++】常用集合算法

    目录

    set_intersection

    set_union

    set_difference

    常用集合算法简介：

    • 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  —— 目标容器开始迭代器

    测试代码：

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6.  
    7. class Person {
    8. public:
    9.     Person(string name, int age) :m_Name(name), m_Age(age) {}
    10.     Person() {}
    11.     string m_Name;
    12.     int m_Age;
    13. };
    14.  
    15. ostream& operator<<(ostream& cout, const Person& p) {
    16.     cout << p.m_Name << " " << p.m_Age << endl;
    17.     return cout;
    18. }
    19.  
    20. template<typename T>
    21. void PrintVector(const T& x) {
    22.     cout << x << " ";
    23. }
    24.  
    25. // 内置数据类型交集
    26. void test01() {
    27.     vector<int>v1; // 有序
    28.     v1.push_back(3);
    29.     v1.push_back(4);
    30.     v1.push_back(5);
    31.     v1.push_back(6);
    32.     vector<int>v2; // 有序
    33.     v2.push_back(4);
    34.     v2.push_back(5);
    35.     v2.push_back(6);
    36.  
    37.     vector<int>v_target; // 目标容器
    38.  
    39.     // 计算大小目标容器需要的合适大小
    40.     size_t v_size = (v1.size() > v2.size()) ? v2.size() : v1.size();
    41.     
    42.     // 或者用 min 算法
    43.     v_size = min(v1.size(), v2.size());
    44.  
    45.     // 需要给目标容器开辟内存 v_size
    46.     v_target.resize(v_size);  // 这个空间可能大了，默认值为 0 
    47.  
    48.     // 求集合交集到目标容器，返回的是最后一个交集的迭代器
    49.     vector<int>::iterator EndIt = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target.begin());
    50.  
    51.     // 遍历的时候可以不用遍历到容器末尾，只需要遍历到交集的最后一个元素即可
    52.     for_each(v_target.begin(), EndIt, PrintVector<int>); // 遍历
    53.     cout << endl;
    54. }
    55.  
    56. class Person_sort {
    57. public:
    58.     bool operator()(const Person& p1, const Person& p2) {
    59.         return (p1.m_Age < p2.m_Age);
    60.     }
    61. };
    62.  
    63. // 自定义数据类型交集
    64. void test02() {
    65.     vectorv1; // 有序
    66.     vectorv2; // 有序
    67.     Person p1("A", 19);
    68.     Person p2("B", 18);
    69.     Person p3("C", 20);
    70.     Person p4("D", 21);  
    71.     
    72.     v1.push_back(p1);
    73.     v1.push_back(p2);
    74.     v1.push_back(p3);
    75.  
    76.     v2.push_back(p1);
    77.     v2.push_back(p2);
    78.     v2.push_back(p3);
    79.     v2.push_back(p4);
    80.  
    81.     sort(v1.begin(), v1.end(), Person_sort());
    82.     sort(v2.begin(), v2.end(), Person_sort());
    83.  
    84.     vectorv_target;
    85.  
    86.     // 计算大小目标容器需要的合适大小
    87.     size_t v_size = (v1.size() > v2.size()) ? v2.size() : v1.size();
    88.  
    89.     v_size = min(v1.size(), v2.size()); // min 算法
    90.  
    91.     // 需要给目标容器开辟内存 v_size
    92.     v_target.resize(v_size);
    93.  
    94.     // 放上排序规则仿函数，返回最后一个交集的迭代器
    95.     vector::iterator EndIt = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target.begin(), Person_sort());
    96.     for_each(v_target.begin(), EndIt, PrintVector); // 遍历
    97.     cout << endl;
    98. }
    99.  
    100. int main() {
    101.     test01();
    102.     test02();
    103.     system("pause");
    104.     return 0;
    105. }

    运行结果：

    • 两个容器必须是有序序列
    • 目标容器取两个容器中的最小值
    • set_intersection 返回值是交集最后一个元素的位置

    set_union

    功能：

    • 求两个集合（有序序列）的并集

    函数原型：

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

    beg1 ——  容器 1 开始迭代器

    end1 ——  容器 1  结束迭代器

    beg2 —— 容器 2 开始迭代器

    end2 —— 容器 2 结束迭代器

    dest  —— 目标容器开始迭代器

    测试代码：

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6.  
    7. class Person {
    8. public:
    9.     Person(string name, int age) :m_Name(name), m_Age(age) {}
    10.     Person() {}
    11.     string m_Name;
    12.     int m_Age;
    13. };
    14.  
    15. // 重载 << 
    16. ostream& operator<<(ostream& cout, const Person& p) {
    17.     cout << p.m_Name << " " << p.m_Age << endl;
    18.     return cout;
    19. }
    20.  
    21. // 输出模板函数
    22. template<typename T>
    23. void PrintVector(const T& x) {
    24.     cout << x << " ";
    25. }
    26.  
    27. // 内置数据类型并集
    28. void test01() {
    29.     vector<int>v1; // 有序
    30.     vector<int>v2; // 有序
    31.     v1.push_back(3);
    32.     v1.push_back(4);
    33.     v1.push_back(5);
    34.     v1.push_back(6);
    35.  
    36.     v2.push_back(5);
    37.     v2.push_back(6);
    38.     v2.push_back(7);
    39.  
    40.     vector<int>v_target;
    41.     v_target.resize(v1.size() + v2.size()); // 并集容量要取两个容器的和
    42.     
    43.     // 返回并集最后一个元素的迭代器
    44.     vector<int>::iterator EndIt = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target.begin());
    45.     for_each(v_target.begin(), EndIt, PrintVector<int>);
    46.     cout << endl;
    47. }
    48.  
    49. // 排序仿函数
    50. class Person_sort {
    51. public:
    52.     bool operator()(const Person& p1, const Person& p2) {
    53.         return (p1.m_Age < p2.m_Age);
    54.     }
    55. };
    56.  
    57. // 自定义数据类并集
    58. void test02() {
    59.     vectorv1; // 有序
    60.     vectorv2; // 有序
    61.     Person p1("A", 17);
    62.     Person p2("B", 19);
    63.     Person p3("C", 21);
    64.     Person p4("D", 23);
    65.     Person p5("E", 25);
    66.  
    67.     v1.push_back(p3);
    68.     v1.push_back(p2);
    69.     v1.push_back(p1);
    70.  
    71.     v2.push_back(p2);
    72.     v2.push_back(p3);
    73.     v2.push_back(p4);
    74.     v2.push_back(p5);
    75.  
    76.     // 先对容器进行排序
    77.     sort(v1.begin(), v1.end(), Person_sort());
    78.     sort(v2.begin(), v2.end(), Person_sort());
    79.  
    80.     vectorv_target; // 目标容器
    81.     v_target.resize(v1.size() + v2.size()); // 两个容器大小和
    82.  
    83.     vector::iterator EndIt = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target.begin(), Person_sort());
    84.     for_each(v_target.begin(), EndIt, PrintVector); // 遍历
    85.     cout << endl;
    86. }
    87.  
    88. int main() {
    89.     test01();
    90.     test02();
    91.     system("pause");
    92.     return 0;
    93. }

    运行结果：

    •  两个集合必须是有序序列
    • 目标容器开辟空间需要两个容器相加
    • set_union 返回值是并集最后一个元素的位置

    set_difference

    功能：

    • 求两个集合（有序序列）的差集

    差集：

    • v1 和 v2 的差集，找的是 v1 里有但 v2 里没有的元素（v1 特有的数）
    • v2 和 v1 的差集，找的是 v2 里有但 v1 里没有的元素（v2 特有的数）

    函数原型：

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

    beg1 —— 容器 1 开始迭代器

    end1 —— 容器 1 结束迭代器

    beg2 —— 容器 2 开始迭代器

    end2 —— 容器 2 结束迭代器

    dest  —— 目标容器开始迭代器

    测试代码：

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6.  
    7. class Person {
    8. public:
    9.     Person(string name, int age) :m_Name(name), m_Age(age) {}
    10.     Person() {}
    11.     string m_Name;
    12.     int m_Age;
    13. };
    14.  
    15. ostream& operator<<(ostream& cout, const Person& p) {
    16.     cout << p.m_Name << " " << p.m_Age << endl;
    17.     return cout;
    18. }
    19.  
    20. template<typename T>
    21. void PrintVector(const T& x) {
    22.     cout << x << " ";
    23. }
    24.  
    25. // 内置数据类型差集
    26. void test01() {
    27.     vector<int>v1; // 有序
    28.     vector<int>v2; // 有序
    29.  
    30.     v1.push_back(10);
    31.     v1.push_back(20);
    32.     v1.push_back(30);
    33.     v1.push_back(40);
    34.  
    35.     v2.push_back(30);
    36.     v2.push_back(40);
    37.     v2.push_back(50);
    38.     v2.push_back(60);
    39.  
    40.     cout << "v1 与 v2 的差集：";
    41.     vector<int>v_target1; // 目标容器
    42.     v_target1.resize(max(v1.size(), v2.size())); // 容器大小
    43.     vector<int>::iterator EndIt1 = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target1.begin());
    44.     for_each(v_target1.begin(), EndIt1, PrintVector<int>);
    45.     cout << endl;
    46.     
    47.     cout << "v1 与 v2 的差集：";
    48.     vector<int>v_target2; // 目标容器
    49.     v_target2.resize(max(v1.size(), v2.size())); // 容器大小
    50.     vector<int>::iterator EndIt2 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v_target2.begin());
    51.     for_each(v_target2.begin(), EndIt2, PrintVector<int>);
    52.     cout << endl;
    53. }
    54.  
    55. // 年龄排序仿函数
    56. class Person_sort {
    57. public:
    58.     bool operator()(const Person& p1, const Person& p2) {
    59.         return (p1.m_Age < p2.m_Age); // m_Age 降序
    60.     }
    61. };
    62.  
    63. // 自定义数据类型差集
    64. void test02() {
    65.     vectorv1; // 有序
    66.     vectorv2; // 有序
    67.  
    68.     Person p1("A", 22);
    69.     Person p2("B", 21);
    70.     Person p3("C", 20);
    71.     Person p4("D", 19);
    72.     Person p5("E", 18);
    73.  
    74.     v1.push_back(p1);
    75.     v1.push_back(p2);
    76.     v1.push_back(p3);
    77.  
    78.     v2.push_back(p3);
    79.     v2.push_back(p4);
    80.     v2.push_back(p5);
    81.  
    82.     sort(v1.begin(), v1.end(), Person_sort()); // 排序
    83.     sort(v2.begin(), v2.end(), Person_sort()); // 排序
    84.  
    85.     cout << "v1 和 v2 的差集：" << endl;
    86.     vectorv_target1;
    87.     v_target1.resize(max(v1.size(), v2.size()));
    88.     vector::iterator EndIt1 = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target1.begin(), Person_sort());
    89.     for_each(v_target1.begin(), EndIt1, PrintVector);
    90.     cout << endl;
    91.  
    92.     cout << "v2 与 v1 的差集：" << endl;;
    93.     vectorv_target2;
    94.     v_target2.resize(max(v1.size(), v2.size()));
    95.     vector::iterator EndIt2 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v_target2.begin(), Person_sort());
    96.     for_each(v_target2.begin(), EndIt2, PrintVector);
    97.     cout << endl;
    98. }
    99.  
    100. int main() {
    101.     test01();
    102.     test02();
    103.     system("pause");
    104.     return 0;
    105. }

    运行结果：

    •  两个容器需要是有序序列
    • 目标容器开辟空间大小取两个容器中大的
  • 相关阅读:
    第一篇：mybatis源码入门
    Flink状态Checkpoints检查点设置
    Git 用法指导
    06-jQuery中的防抖和节流
    基于MATLAB的指纹识别算法仿真实现
    双重队列问题
    C语言进阶 文件操作知识（上）
    Python之基础数据类型(二)
    【LeetCode刷题】--12.整数转罗马数字
    Redis 是什么？
  • 原文地址：https://blog.csdn.net/xuan3215/article/details/126230117