检查值是否在set p1和p2中，而不是在p3中

Question

我遇到了一个练习，我想知道是否有更好的方法来实现这一点：

给定三个集合，p1、p2和p3，您希望列出p1和p2中的值，而不是p3中的值。

我的尝试很简单：

include <iostream>
#include <set>

std::set<int>   p1({1, 2, 3, 4, 5, 6, 7});
std::set<int>   p2({1, 3, 4, 5, 7});
std::set<int>   p3({1, 7});


int main() {

    std::cout << "p1: ";
    for(int v : p1) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;

    std::cout << "p2: ";
    for(int v : p2) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;

    std::set<int> p;

    for(int v: p1) {
        if(p2.find(v) != p2.end()) {
            p.insert(v);
        }
    }

    for(int v: p2) {
        if(p1.find(v) != p1.end()) {
            p.insert(v);
        }
    }

    for(int v: p3) {
        p.erase(v);
    }

    std::cout << "p: ";
    for(int v : p) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

p1: 1, 2, 3, 4, 5, 6, 7,
p2: 1, 3, 4, 5, 7,
p3: 1, 7,
p: 3, 4, 5,

编辑：

谢谢大家的答复。

我已经将你所有的答案汇编成一个小测试程序，并对它们进行了基准测试：

#include <iostream>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <chrono>

std::set<int> p1;
std::set<int> p2;
std::set<int> p3;


template<typename T> std::set<T> operator &(const std::set<T>& s1, const std::set<T>& s2)
{
    std::set<T> result;
    std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
                          std::inserter(result, result.begin()));

    return result;

}

template<typename T> std::set<T> operator ^(const std::set<T> & s1, const std::set<T> & s2)
{
    std::set<T> result;
    std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
                        std::inserter(result, result.begin()));
    return result;
}


void version_0(std::set<int> & p1, std::set<int> & p2, std::set<int> & p3, std::set<int> & p)
{
    for(int v: p1) {
        if(p2.find(v) != p2.end()) {
            p.insert(v);
        }
    }

    for(int v: p2) {
        if(p1.find(v) != p1.end()) {
            p.insert(v);
        }
    }

    for(int v: p3) {
        p.erase(v);
    }
}


void version_1(std::set<int> & p1, std::set<int> & p2, std::set<int> & p3, std::set<int> & p)
{
    for(int v: p1) {
        if(p2.find(v) != p2.end()) {
            p.insert(v);
        }
    }

    for(int v: p3) {
        p.erase(v);
    }

}


void version_2(std::set<int> & p1, std::set<int> & p2, std::set<int> & p3, std::set<int> & p)
{
    for (int i: p1)
    {
        if ( p2.find(i)!=p2.end() && p3.find(i) == p3.end()) {
            p.insert(i);
        }
    }
}


void version_3(std::set<int> & p1, std::set<int> & p2, std::set<int> & p3, std::set<int> & p)
{
    std::set<int> p1_and_p2;

    std::set_intersection(p1.begin(), p1.end(), p2.begin(), p2.end(),
                          std::inserter(p1_and_p2, p1_and_p2.begin()));

    std::set_difference(p1_and_p2.begin(), p1_and_p2.end(), p3.begin(), p3.end(),
                        std::inserter(p, p.begin()));
}


void version_4(std::set<int> & p1, std::set<int> & p2, std::set<int> & p3, std::set<int> & p)
{
    std::set_intersection(p1.begin(), p1.end(), p2.begin(), p2.end(), 
                                               std::inserter(p, p.begin()));

    for (int v : p3)
        p.erase(v);
}


void version_5(std::set<int> & p1, std::set<int> & p2, std::set<int> & p3, std::set<int> & p)
{
    p = (p1 & p2) ^ p3;
}


void (*versions[])(std::set<int> &, std::set<int> &, std::set<int> &, std::set<int> &) = {
    version_0,
    version_1,
    version_2,
    version_3,
    version_4,
    version_5
};


int main() {

    srand(0);

    for(int i = 0; i < 1000000; ++i) {
        p1.insert(rand());
    }

    for(int i = 0; i < 1000000; ++i) {
        p2.insert(rand());
    }

    for(int i = 0; i < 1000000; ++i) {
        p3.insert(rand());
    }

    std::cout << "P1 size: " << p1.size() << std::endl;
    std::cout << "P2 size: " << p2.size() << std::endl;
    std::cout << "P3 size: " << p3.size() << std::endl;

    std::set<int> p;
    std::set<int> p1_and_p2;

    int i = 0;

    for(auto func: versions) {
        auto t1 = std::chrono::high_resolution_clock::now();

        std::set<int> p;
        func(p1, p2, p3, p);

        auto t2 = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();

        std::cout << "Version " << i++ << " took " << duration << "us and found " << p.size() << " values" << std::endl;
    }

    return 0;
}

输出：

$ g++ -std=c++2a -O3 -o test test.cpp
$ ./test
P1 size: 999769
P2 size: 999752
P3 size: 999798
Version 0 took 560467us and found 453 values
Version 1 took 338087us and found 453 values
Version 2 took 226445us and found 453 values
Version 3 took 254171us and found 453 values
Version 4 took 259274us and found 453 values
Version 5 took 254655us and found 453 values

Answer 1

我会用std::set_intersection和std::set_difference。

示例：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>

int main() {
    std::set<int>   p1({1, 2, 3, 4, 5, 6, 7});
    std::set<int>   p2({1, 3, 4, 5, 7});
    std::set<int>   p3({1, 7});

    std::set<int> p1_and_p2;
    std::set_intersection(p1.begin(), p1.end(), p2.begin(), p2.end(),
                          std::inserter(p1_and_p2, p1_and_p2.begin()));

    std::set<int> not_in_p3;
    std::set_difference(p1_and_p2.begin(), p1_and_p2.end(), p3.begin(), p3.end(),
                        std::inserter(not_in_p3, not_in_p3.begin()));
    
    for(auto v : not_in_p3) std::cout << v << '\n';
}

输出：

3
4
5

Answer 2

您正在寻找std::set_intersection的第一个p1和p2，然后删除p3从它。参见下面的示例代码

#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>

int main()
{
    std::set<int>   p1({ 1, 2, 3, 4, 5, 6, 7 });
    std::set<int>   p2({ 1, 3, 4, 5, 7 });
    std::set<int>   p3({ 1, 7 });

    std::set<int> p;

    std::set_intersection(p1.begin(), p1.end(), p2.begin(), p2.end(), 
                                               std::inserter(p, p.begin()));

    for (int v : p3)
        p.erase(v);


    return 0;
}

Answer 3

那麽：

std::set<int>   p1({1, 2, 3, 4, 5, 6, 7});
std::set<int>   p2({1, 3, 4, 5, 7});
std::set<int>   p3({1, 7});

int main()
{   
    for ( auto i: p1 )
    {   
        if (
            ( p2.find(i)!=p2.end()) &&  
            ( p3.find(i) == p3.end())
           )   
            std::cout << i << std::endl;
    }   
}