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

测试代码：

#include
#include
#include
#include
using namespace std;

class Person {
public:
    Person(string name, int age) :m_Name(name), m_Age(age) {}
    Person() {}
    string m_Name;
    int m_Age;
};

ostream& operator<<(ostream& cout, const Person& p) {
    cout << p.m_Name << " " << p.m_Age << endl;
    return cout;
}

template
void PrintVector(const T& x) {
    cout << x << " ";
}

// 内置数据类型交集
void test01() {
    vectorv1; // 有序
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);
    vectorv2; // 有序
    v2.push_back(4);
    v2.push_back(5);
    v2.push_back(6);

    vectorv_target; // 目标容器

    // 计算大小目标容器需要的合适大小
    size_t v_size = (v1.size() > v2.size()) ? v2.size() : v1.size();
    
    // 或者用 min 算法
    v_size = min(v1.size(), v2.size());

    // 需要给目标容器开辟内存 v_size
    v_target.resize(v_size);  // 这个空间可能大了，默认值为 0 

    // 求集合交集到目标容器，返回的是最后一个交集的迭代器
    vector::iterator EndIt = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target.begin());

    // 遍历的时候可以不用遍历到容器末尾，只需要遍历到交集的最后一个元素即可
    for_each(v_target.begin(), EndIt, PrintVector); // 遍历
    cout << endl;
}

class Person_sort {
public:
    bool operator()(const Person& p1, const Person& p2) {
        return (p1.m_Age < p2.m_Age);
    }
};

// 自定义数据类型交集
void test02() {
    vectorv1; // 有序
    vectorv2; // 有序
    Person p1("A", 19);
    Person p2("B", 18);
    Person p3("C", 20);
    Person p4("D", 21);  
    
    v1.push_back(p1);
    v1.push_back(p2);
    v1.push_back(p3);

    v2.push_back(p1);
    v2.push_back(p2);
    v2.push_back(p3);
    v2.push_back(p4);

    sort(v1.begin(), v1.end(), Person_sort());
    sort(v2.begin(), v2.end(), Person_sort());

    vectorv_target;

    // 计算大小目标容器需要的合适大小
    size_t v_size = (v1.size() > v2.size()) ? v2.size() : v1.size();

    v_size = min(v1.size(), v2.size()); // min 算法

    // 需要给目标容器开辟内存 v_size
    v_target.resize(v_size);

    // 放上排序规则仿函数，返回最后一个交集的迭代器
    vector::iterator EndIt = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target.begin(), Person_sort());
    for_each(v_target.begin(), EndIt, PrintVector); // 遍历
    cout << endl;
}

int main() {
    test01();
    test02();
    system("pause");
    return 0;
}

运行结果：

• 两个容器必须是有序序列
• 目标容器取两个容器中的最小值
• 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  —— 目标容器开始迭代器

测试代码：

#include
#include
#include
#include
using namespace std;

class Person {
public:
    Person(string name, int age) :m_Name(name), m_Age(age) {}
    Person() {}
    string m_Name;
    int m_Age;
};

// 重载 << 
ostream& operator<<(ostream& cout, const Person& p) {
    cout << p.m_Name << " " << p.m_Age << endl;
    return cout;
}

// 输出模板函数
template
void PrintVector(const T& x) {
    cout << x << " ";
}

// 内置数据类型并集
void test01() {
    vectorv1; // 有序
    vectorv2; // 有序
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);

    v2.push_back(5);
    v2.push_back(6);
    v2.push_back(7);

    vectorv_target;
    v_target.resize(v1.size() + v2.size()); // 并集容量要取两个容器的和
    
    // 返回并集最后一个元素的迭代器
    vector::iterator EndIt = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target.begin());
    for_each(v_target.begin(), EndIt, PrintVector);
    cout << endl;
}

// 排序仿函数
class Person_sort {
public:
    bool operator()(const Person& p1, const Person& p2) {
        return (p1.m_Age < p2.m_Age);
    }
};

// 自定义数据类并集
void test02() {
    vectorv1; // 有序
    vectorv2; // 有序
    Person p1("A", 17);
    Person p2("B", 19);
    Person p3("C", 21);
    Person p4("D", 23);
    Person p5("E", 25);

    v1.push_back(p3);
    v1.push_back(p2);
    v1.push_back(p1);

    v2.push_back(p2);
    v2.push_back(p3);
    v2.push_back(p4);
    v2.push_back(p5);

    // 先对容器进行排序
    sort(v1.begin(), v1.end(), Person_sort());
    sort(v2.begin(), v2.end(), Person_sort());

    vectorv_target; // 目标容器
    v_target.resize(v1.size() + v2.size()); // 两个容器大小和

    vector::iterator EndIt = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target.begin(), Person_sort());
    for_each(v_target.begin(), EndIt, PrintVector); // 遍历
    cout << endl;
}

int main() {
    test01();
    test02();
    system("pause");
    return 0;
}

运行结果：

•  两个集合必须是有序序列
• 目标容器开辟空间需要两个容器相加
• 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  —— 目标容器开始迭代器

测试代码：

#include
#include
#include
#include
using namespace std;

class Person {
public:
    Person(string name, int age) :m_Name(name), m_Age(age) {}
    Person() {}
    string m_Name;
    int m_Age;
};

ostream& operator<<(ostream& cout, const Person& p) {
    cout << p.m_Name << " " << p.m_Age << endl;
    return cout;
}

template
void PrintVector(const T& x) {
    cout << x << " ";
}

// 内置数据类型差集
void test01() {
    vectorv1; // 有序
    vectorv2; // 有序

    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);

    v2.push_back(30);
    v2.push_back(40);
    v2.push_back(50);
    v2.push_back(60);

    cout << "v1 与 v2 的差集：";
    vectorv_target1; // 目标容器
    v_target1.resize(max(v1.size(), v2.size())); // 容器大小
    vector::iterator EndIt1 = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target1.begin());
    for_each(v_target1.begin(), EndIt1, PrintVector);
    cout << endl;
    
    cout << "v1 与 v2 的差集：";
    vectorv_target2; // 目标容器
    v_target2.resize(max(v1.size(), v2.size())); // 容器大小
    vector::iterator EndIt2 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v_target2.begin());
    for_each(v_target2.begin(), EndIt2, PrintVector);
    cout << endl;
}

// 年龄排序仿函数
class Person_sort {
public:
    bool operator()(const Person& p1, const Person& p2) {
        return (p1.m_Age < p2.m_Age); // m_Age 降序
    }
};

// 自定义数据类型差集
void test02() {
    vectorv1; // 有序
    vectorv2; // 有序

    Person p1("A", 22);
    Person p2("B", 21);
    Person p3("C", 20);
    Person p4("D", 19);
    Person p5("E", 18);

    v1.push_back(p1);
    v1.push_back(p2);
    v1.push_back(p3);

    v2.push_back(p3);
    v2.push_back(p4);
    v2.push_back(p5);

    sort(v1.begin(), v1.end(), Person_sort()); // 排序
    sort(v2.begin(), v2.end(), Person_sort()); // 排序

    cout << "v1 和 v2 的差集：" << endl;
    vectorv_target1;
    v_target1.resize(max(v1.size(), v2.size()));
    vector::iterator EndIt1 = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v_target1.begin(), Person_sort());
    for_each(v_target1.begin(), EndIt1, PrintVector);
    cout << endl;

    cout << "v2 与 v1 的差集：" << endl;;
    vectorv_target2;
    v_target2.resize(max(v1.size(), v2.size()));
    vector::iterator EndIt2 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v_target2.begin(), Person_sort());
    for_each(v_target2.begin(), EndIt2, PrintVector);
    cout << endl;
}

int main() {
    test01();
    test02();
    system("pause");
    return 0;
}

运行结果：

•  两个容器需要是有序序列
• 目标容器开辟空间大小取两个容器中大的