set_difference e set_intersection contemporaneamente

Question

Mi chiedo se nella libreria standard ci sia qualche possibilità di calcolare l'intersezione impostata e impostare la differenza tra due intervalli ordinati. Qualcosa con una firma lungo le linee di:

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

Tale che dopo una chiamata a decompose sets, result1 contiene tutti gli elementi [first1,last1) che non sono in [first2,last2), result2 contiene tutti gli elementi [first2,last2) che non sono in [first1,last1), e result3 contiene tutti gli elementi che sono comuni in [first1,last1) e [first2,last2).

Le implementazioni di esempio di set_difference e set_intersection di cplusplus.com sembrano come se possano aiutarmi a creare un'implementazione efficiente che esegue solo una scansione anziché tre. Se è nella libreria standard, però, non vorrei reinventare la ruota.

esempio, su richiesta:

Dati due insiemi a = {0, 1, 2, 3, 4} e b = {2, 4, 5, 6} allora vorrebbe costruire seguenti tre insiemi:

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

Answer 1

Non esiste un algoritmo di libreria standard che lo esegua in un'unica scansione ma è facile da scrivere. Il seguente aspetto è corretto e l'output ha senso 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

non esiste funzione STL , ma c'è set_symmetric_difference() che costruisce una sequenza ordinata degli elementi presenti nella prima sequenza ma non presenti nella seconda, e quegli elementi presenti nella seconda sequenza non sono presenti nella prima.

Answer 3

Ecco un'altra alternativa, che utilizza le richiamate per la massima flessibilità.

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

Ciò presenta i seguenti vantaggi:

• Uscita elenca facoltativi ora
• uscita può essere di tipo diverso (Transform)
• elementi comuni possono essere ulteriormente elaborati in tandem (confronto aggiuntivo)

Esempio "mondo reale" :

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