In-Place-C++ Schnittmenge

Question

Der Standardweg zwei Sätze in C++ von sich schneid ist folgendes zu tun:

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

Wie würde ich über das Tun eine in-Place-Set Kreuzung gehen? Das heißt, ich möchte set_1 die Ergebnisse des Aufrufs von set_intersection haben. Offensichtlich kann ich einfach eine set_1.swap(the_intersection) machen, aber das ist viel weniger effizient als das Schneiden an Ort und Stelle.

Answer 1

Ich glaube, ich habe es:

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

Wer irgendwelche Probleme sehen? Scheint O (n) auf der Größe der zwei Sätze zu sein. Gemäß cplusplus.com ist std :: set Erase (Position) amortisiert, während Erase (first, last) ist O (log n).

Answer 2

Sie können ganz einfach durch set_1 gehen, überprüfen Sie jedes Element, um zu sehen, ob es in set_2 vorhanden ist, und es zu löschen, wenn es nicht der Fall ist. Da die Sätze sortiert sind, können Sie sie in linearer Zeit vergleichen, und das Löschen eines Elements mit einem Iterator ist amortized constant time. Ich würde nicht darauf zählen, dass es effizienter ist als das, womit Sie begonnen haben, Benchmarking wäre jedoch sinnvoll, wenn es für Sie von Bedeutung ist.