-C++ establecer intersección

Question

La forma estándar de intersección de dos conjuntos en C++ es hacer lo siguiente:

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())); 

¿Cómo voy a ir haciendo un conjunto de intersección en el lugar? Es decir, quiero que set_1 tenga los resultados de la llamada a set_intersection. Obviamente, puedo hacer un set_1.swap(the_intersection), pero esto es mucho menos eficiente que intersectar en el lugar.

Answer 1

creo que ya lo tengo:

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()); 

Alguien ve algún problema? Parece ser O (n) en el tamaño de los dos conjuntos. De acuerdo con cplusplus.com, std :: set erase (position) se amortiza constantemente, mientras que erase (first, last) es O (log n).

Answer 2

Puede ir fácilmente a través de set_1, verifique cada elemento para ver si existe en set_2, y bórrelo si no lo hace. Como los conjuntos están ordenados, puede compararlos en tiempo lineal, y borrar un elemento usando un iterador es amortized constant time. Sin embargo, no confiaría en que sea más eficiente que con lo que comenzaste, la evaluación comparativa sería sabia si es importante para ti.