Проверьте, указано ли значение в наборе p1 и p2, но не в p3 - PullRequest
Новая
       28

Проверьте, указано ли значение в наборе p1 и p2, но не в p3

2 голосов
/ 14 июля 2020

Я наткнулся на упражнение и хотел бы знать, есть ли лучший способ его реализовать:

Учитывая три набора, 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

Ответы [ 4 ]

4 голосов
/ 14 июля 2020

Я бы использовал 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
2 голосов
/ 14 июля 2020

Вы ищете 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;
}
1 голос
/ 14 июля 2020

Вы можете реализовать intersection и - как операторы: 

template<typename T> set<T> operator &(const set<T>& s1, const set<T>& s2) { ... }
template<typename T> set<T> operator -(const set<T>& s1, const set<T>& s2) { ... }

int main() {
    set s1 = {1, 2, 3, 4, 5, 6, 7};
    set s2 = {1, 3, 4, 5, 7};
    set s3 = {3, 7};

    auto result = ( s1 & s2 ) - s3; // <- more 'elegant'

    std::copy( result.begin(),result.end(), ostream_iterator<int>(cout, " "));
}

https://godbolt.org/z/xPbeox

1 голос
/ 14 июля 2020

А как насчет: 

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;
    }   
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...