come calcolare le dimensioni di un incrocio di due insiemi STL in C++

Question

mi viene data due set (std :: set da <set>) di cui mi piacerebbe conoscere la dimensione dell'intersezione . Potrei usare std :: set_intersection da <algorithm>, ma devo fornire un iteratore di output per copiare l'intersezione in qualche altro contenitore.

Un modo semplice sarebbe

set<int> s1{1,2,3,4,5}; 
    set<int> s2{4,5,6,7,8,9,0,1}; 

    vector<int> v; 

    set_intersection(
     s1.begin(), s1.end(), s2.begin(), s2.end(), 
     inserter(v, v.begin())); 

dopodiché V.SIZE() fornisce la dimensione dell'intersezione. Tuttavia, l'intersezione dovrà essere memorizzata, anche se non facciamo nulla con esso.

Per evitare questo, ho cercato di implementare una classe di uscita iteratore manichino, che conta solo, ma non assegna:

template<typename T> 
class CountingOutputIterator { 
private: 
    int* counter_; 
    T dummy_; 
public: 
    explicit CountingOutputIterator(int* counter) :counter_(counter) {} 
    T& operator*() {return dummy_;} 
    CountingOutputIterator& operator++() { // ++t 
    (*counter_)++; 
    return *this; 
    } 
    CountingOutputIterator operator++(int) { // t++ 
    CountingOutputIterator ret(*this); 
    (*counter_)++; 
    return ret; 
    } 
    bool operator==(const CountingOutputIterator& c) { 
    return counter_ == c.counter_; // same pointer 
    } 
    bool operator!=(const CountingOutputIterator& c) { 
    return !operator==(c); 
    } 
}; 

usando che potremmo fare

set<int> s1{1,2,3,4,5}; 
    set<int> s2{4,5,6,7,8,9,0,1}; 

    int counter = 0; 
    CountingOutputIterator<int> counter_it(&counter); 
    set_intersection(
     s1.begin(), s1.end(), s2.begin(), s2.end(), counter_it); 

dopo di che contatore tiene la dimensione dell'intersezione.

Questo è molto più codice tuttavia. Le mie domande sono:

1) Esiste un metodo standard (libreria) o un trucco standard per ottenere la dimensione dell'intersezione senza memorizzare l'intera intersezione? 2) Indipendentemente dal fatto che ci sia o meno, l'approccio con il fittizio iteratore personalizzato è buono?

Answer 1

Non è difficile scrivere un ciclo che si muove attraverso le due serie alla ricerca di elementi corrispondenti, oppure si potrebbe fare questo, che è molto più semplice di un iteratore personalizzato:

struct Counter 
{ 
    struct value_type { template<typename T> value_type(const T&) { } }; 
    void push_back(const value_type&) { ++count; } 
    size_t count = 0; 
}; 

template<typename T1, typename T2> 
size_t intersection_size(const T1& s1, const T2& s2) 
{ 
    Counter c; 
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(c)); 
    return c.count; 
} 

Answer 2

Si potrebbe fare questo:

auto common = count_if(begin(s1), end(s1), [&](const auto& x){ return s2.find(x) != end(s2); }); 

Non è ottimamente efficiente, ma dovrebbe essere abbastanza veloce per la maggior parte scopi.

Answer 3

Non è molto difficile scrivere una funzione che lo faccia. This mostra come set_intersection è fatto [anche se l'attuazione effettiva può naturalmente essere leggermente diversa]

Così abbiamo potuto solo prendere quel codice, e modificarlo un po ':

template <class InputIterator1, class InputIterator2> 
    size_t set_intersection_size (InputIterator1 first1, InputIterator1 last1, 
           InputIterator2 first2, InputIterator2 last2) 
{ 
    size_t result = 0; 
    while (first1!=last1 && first2!=last2) 
    { 
    if (*first1<*first2) ++first1; 
    else if (*first2<*first1) ++first2; 
    else { 
     result++; 
     ++first1; ++first2; 
    } 
    } 
    return result; 
} 

Anche se nella mia esperienza, quando vuoi sapere quanti sono nell'intersezione, in genere prima o poi vuoi sapere anche quali elementi.

Answer 4

È possibile semplificare l'utilizzo di il tuo approccio un bel po ':

struct counting_iterator 
{ 
    size_t count; 
    counting_iterator& operator++() { ++count; return *this; } 
    // other iterator stuff 
}; 

size_t count = set_intersection(
    s1.begin(), s1.end(), s2.begin(), s2.end(), counting_iterator()).count;