in-place C++ impostare intersezione

Question

Il metodo standard di intersecano due set in C++ è quello di effettuare le seguenti operazioni:

std::set<int> set_1; // With some elements 
std::set<int> set_2; // With some other elements 
std::set<int> the_intersection; // Destination of intersect 
std::set_intersection(set_1.begin(), set_1.end(), set_2.begin(), set_2.end(), std::inserter(the_intersection, the_intersection.end())); 

Come potrei fare per fare una serie di intersezione sul posto? Cioè, voglio che set_1 abbia i risultati della chiamata a set_intersection. Ovviamente, posso solo fare un set_1.swap(the_intersection), ma questo è molto meno efficiente di intersecare sul posto.

Answer 1

Credo di aver capito:

std::set<int>::iterator it1 = set_1.begin(); 
std::set<int>::iterator it2 = set_2.begin(); 
while ((it1 != set_1.end()) && (it2 != set_2.end())) { 
    if (*it1 < *it2) { 
     set_1.erase(it1++); 
    } else if (*it2 < *it1) { 
     ++it2; 
    } else { // *it1 == *it2 
      ++it1; 
      ++it2; 
    } 
} 
// Anything left in set_1 from here on did not appear in set_2, 
// so we remove it. 
set_1.erase(it1, set_1.end()); 

Chiunque veda problemi? Sembra essere O (n) sulla dimensione dei due set. Secondo cplusplus.com, std :: set cancella (posizione) è ammortizzato costante mentre cancella (primo, ultimo) è O (log n).

Answer 2

Si può facilmente passare attraverso set_1, controllare ogni elemento per vedere se esiste in set_2, e cancellarlo se non lo fa. Poiché i set sono ordinati, è possibile confrontarli in tempo lineare e la cancellazione di un elemento utilizzando un iteratore è amortized constant time. Non conterei sul fatto che sia più efficiente di quello che hai iniziato con, benchmarking sarebbe saggio se ti interessa.