算法set_intersection、set_union、set_difference

目录

• 关于容器交集、并集、差集的算法
  • 1 示例代码
  • 2 运行结果
  • 3 总结
    • 3.1 相同点
    • 3.2 不同点
      • 3.2.1 set_intersection
      • 3.2.2 set_union
      • 3.2.3 set_difference
      • 3.2.4 差异对比

关于容器交集、并集、差集的算法

不喜欢无实物表演，秉承一贯风格，用代码说事。

1 示例代码

#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

int main()
{
    std::set<std::string> basket1{ "apple", "orange", "banana", "apricot", "peanut", "cherry" };
    std::set<std::string> basket2{ "cherry", "pear", "mango", "grape", "lemon", "peanut" };

    auto printSet = [](std::set<std::string>& strSet, const std::string& message) {
        std::cout << "打印" << message << "结果如下：" << std::endl;
        for (auto& item : strSet)
            std::cout << item << std::endl;
        std::cout << std::endl;
    };

    // 打印原始数据
    printSet(basket1, "篮子1");
    printSet(basket2, "篮子2");

    // 交集
    std::set<std::string> inter_result;
    std::set_intersection(std::begin(basket1), std::end(basket1), std::begin(basket2), std::end(basket2), 
        std::inserter(inter_result, std::begin(inter_result)));
    printSet(inter_result, std::string("set_intersection"));

    // 并集
    std::set<std::string> union_result;
    std::set_union(std::begin(basket1), std::end(basket1), std::begin(basket2), std::end(basket2),
        std::inserter(union_result, std::begin(union_result)));
    printSet(union_result, "set_union");

    // 差集
    std::set<std::string> difference_result;
    std::set_difference(std::begin(basket1), std::end(basket1), std::begin(basket2), std::end(basket2),
        std::inserter(difference_result, std::begin(difference_result)));
    printSet(difference_result, "set_difference");

    // 非set容器应用示例
    {
        std::vector<int> vecInt1 = { 10, 20, 30, 40, 50, 60 };
        std::vector<int> vecInt2 = { 20, 25, 30, 34, 56, 80 };
        std::vector<int> inter_vec_result;
        std::set_intersection(std::begin(vecInt1), std::end(vecInt1), std::begin(vecInt2), std::end(vecInt2),
            std::back_inserter(inter_vec_result));
        std::cout << "std::vector应用结果示例：" << std::endl;
        for (auto& item : inter_vec_result)
        {
            std::cout << item << std::endl;
        }
    }

    system("pause");
}

2 运行结果

打印篮子1结果如下：
apple
apricot
banana
cherry
orange
peanut

打印篮子2结果如下：
cherry
grape
lemon
mango
peanut
pear

打印set_intersection结果如下：
cherry
peanut

打印set_union结果如下：
apple
apricot
banana
cherry
grape
lemon
mango
orange
peanut
pear

打印set_difference结果如下：
apple
apricot
banana
orange

std::vector应用结果示例：
20
30
请按任意键继续. . .

3 总结

3.1 相同点

• 引用头文件 #include

• 因为std::set容器默认是有序的，因此set容器使用可随意使用这三个算法。

  详见示例中篮子1和篮子2的打印结果，尽管初始化往篮子中塞时候是无序的，但塞入之后容器会默认排好序。

• 不仅仅只是std::set容器才可以应用这三个算法；其他容器也可以使用，但必须先保证容器中数据是有序的。

  详见示例中std::vector容器的应用示例。当然，实际工作中可先调用sort算法对容器中数据进行排序后再应用此算法。

  如果容器的数据无序，程序会“崩溃”。不妨可以把示例代码中第43行的std::vector中元素位置调换后再运行试试。

3.2 不同点

3.2.1 set_intersection

求两个容器中元素的交集。如下图所示：

3.2.2 set_union

求两个容器中元素的并集。如下图所示：

3.2.3 set_difference

求两个容器1与容器2中元素的差集。如下图所示：

3.2.4 差异对比

如下图所示：