set_difference und set_intersection simultan

Question

Ich frage mich, ob es eine Einrichtung in der Standard-Bibliothek gibt, um gleichzeitig den gesetzten Schnittpunkt zu berechnen und die Differenz zwischen zwei sortierten Bereichen festzulegen. Etwas mit einer Signatur entlang der Linien von:

template <class Input1, class Input2, 
      class Output1, class Output2, class Output3> 
Output3 decompose_sets (Input1 first1, Input1 last1, 
         Input2 first2, Input2 last2, 
         Output1 result1, Output2 result2, 
         Output3 result3); 

, so daß nach einem Aufruf an decompose sets, result1 enthält alle Elemente in [first1,last1) die nicht in [first2,last2), result2 alle Elemente in [first2,last2) enthält, die nicht in [first1,last1), und result3 enthält alle Elemente, die in [first1,last1) und [first2,last2) gemeinsam sind.

Die Beispielimplementierungen set_difference und set_intersection von cplusplus.com scheinen, als könnten sie mir helfen, eine effiziente Implementierung zu erstellen, die nur einen Scan statt drei durchführt. Wenn es in der Standardbibliothek ist, würde ich es hassen, das Rad neu zu erfinden.

Beispiel durch Anfrage:

Gegeben seien zwei Sätze a = {0, 1, 2, 3, 4} und B = {2, 4, 5, 6}, dann würde Ich mag die folgenden drei bauen Sets:

• only_a = {0,1,3}
• only_b = {5,6}
• gemeinsamen = {2,4}

Answer 1

Es gibt keinen Standard-Bibliotheksalgorithmus, der es in einem einzigen Scan macht, aber es ist einfach zu schreiben. Das Folgende sieht korrekt aus und die Ausgabe ist sinnvoll here on ideone.com.

template <class Input1, class Input2, 
      class Output1, class Output2, class Output3> 
Output3 decompose_sets(Input1 first1, Input1 last1, 
        Input2 first2, Input2 last2, 
        Output1 result1, Output2 result2, 
        Output3 result3) 
{ 
    while (first1 != last1 && first2 != last2) { 
     if (*first1 < *first2) { 
      *result1++ = *first1++; 
     } else if (*first2 < *first1) { 
      *result2++ = *first2++; 
     } else { 
      *result3++ = *first1++; 
      ++first2; // skip common value in set2 
     } 
    } 
    std::copy(first1, last1, result1); 
    std::copy(first2, last2, result2); 
    return result3; 
} 

Answer 2

Es gibt keine solche Funktion in STL , aber es gibt set_symmetric_difference(), die eine sortierte Sequenz der Elemente konstruiert, die in der ersten Sequenz vorhanden sind, aber nicht in der zweiten Sequenz vorhanden sind, und jene Elemente, die in der zweiten Sequenz vorhanden sind, sind nicht in der ersten Sequenz vorhanden.

Answer 3

Hier ist eine weitere Alternative, die Rückrufe für maximale Flexibilität verwendet.

template <class Input1, class Input2 
      , class FuncAdd, class FuncRm, class FuncSame, class Comp> 
void set_difference_adv(Input1 firstOld, Input1 lastOld 
         ,Input2 firstNew, Input2 lastNew 
         ,FuncAdd onadded, FuncRm onremoved, FuncSame onsame, Comp comp) 
{ 
    while (firstOld != lastOld && firstNew != lastNew) { 

    if (comp(*firstOld, *firstNew)) { 
     onremoved(*firstOld++); 
    } else if (comp(*firstNew, *firstOld)) { 
     onadded(*firstNew++); 
    } else { 
     onsame(*firstOld++, *firstNew++); 
    } 
    } 

    std::for_each(firstOld, lastOld, onremoved); 
    std::for_each(firstNew, lastNew, onadded); 
} 

Dies hat folgende Vorteile:

• Output-Listen sind optional jetzt
• Ausgang kann ein anderer Typ sein (Transformation)
• Gemeinsame Elemente können weiter in Tandem verarbeitet werden (zusätzlicher Vergleich)

Beispiel "echte Welt" :

int main() 
{ 
    using File = std::pair<std::string, int>; 

    std::vector<File> files1{{"file1", 12}, {"file3", 8}, {"file4", 2}, {"file5", 10}}; 
    std::vector<File> files2{{"file1", 12}, {"file2", 5}, {"file3", 8}, {"file4", 33}}; 

    const auto less = [](const auto& o, const auto& n) { return o.first < n.first; }; 

    std::vector<std::string> addedNames; 
    std::vector<File> changedFiles; 

    set_difference_adv(std::cbegin(files1), std::cend(files1) 
        ,std::cbegin(files2), std::cend(files2) 
        , [&addedNames](const auto& val){ addedNames.push_back(val.first); } //< added (transform) 
        , [](const auto& val) {} //< removed (ignore) 
        , [&changedFiles](const auto& o, const auto& n){ if(n.second > o.second) changedFiles.push_back(n); } //< "same" (further compare) 
        , less 
        ); 
}