Überschneidung von Vektor des Paares C++

Question

I die folgenden Vektoren:

vector<unsigned> A,B1; 
vector<pair<unsigned,unsigned> > B2; 

Ich will die Kreuzung von (A,B1) und dann den Schnittpunkt der (A,B2) auszuführen. Ich möchte dann die Vereinigung der beiden Kreuzungsergebnisse durchführen. Die Vektoren A und B1 enthalten sortierte vorzeichenlose Ganzzahlen und der Vektor B2 enthält Paare von (start,end) Werten. Beispielvektoren A und B2, und deren Kreuzungsvektor wird unten dargestellt:

vector<unsigned> A(2,4,6,8,9,10,34,74,79,81,89,91,95); 
    vector<pair<unsigned,unsigned> > B2={ {2, 3}, {29, 40}, {60, 85} }; 
    vector<unsigned> intersection; //result of intersection of A and B2 -> Procedure of performing intersection is explained below 
    //intersection=(2,34,74,79,81); 

2 in Kreuzung als in 2{2,3} ist. Ebenso liegt 34 im Schnittpunkt wie 34 liegt zwischen {29,40}. Ähnlich liegen 74, 79, 81 im Schnittpunkt, da sie innerhalb des Bereichs B2 des letzten Elements {60,85} liegen.

Gibt es eine effiziente Art und Weise, durch die ich die gleichen Ergebnisse wie erhalten können:

(1). Kreuzung A und B1; (2). Schnittpunkt von A und B2; (3). Vereinigung der beiden in Schritt 1 und 2 durchgeführt Kreuzungen (d Kreuzung (A,B1) und (A,B2))

Answer 1

Update:

Nach der Frage Re-Lektüre ich, dass Sie wahrscheinlich realisiert wollte man alle drei Operationen tun.

Wir können die Anzahl der Iterationen der äußeren Schleife auf einen reduzieren und durch Zusammen drei Funktionen in ein und Zurückgeben eines Tupels eine innere Schleife entfernen:

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <iterator> 
#include <tuple> 


std::tuple<std::vector<unsigned>, std::vector<unsigned>, std::vector<unsigned>> 
find_everything(const std::vector<unsigned>& a, 
       const std::vector<std::pair<unsigned,unsigned> >& b1, 
       const std::vector<std::pair<unsigned,unsigned> >& b2) 
{ 
    std::vector<unsigned> r1, r2, both; 

    for (auto x : a) 
    { 
     auto either = false; 
     auto i = std::find_if(std::begin(b1), 
           std::end(b1), 
           [x](const auto& range) 
           { return x >= range.first && x < range.second; }); 
     if (i != std::end(b1)) { 
      either = true; 
      r1.push_back(x); 
     } 

     i = std::find_if(std::begin(b2), 
           std::end(b2), 
           [x](const auto& range) 
           { return x >= range.first && x < range.second; }); 
     if (i != std::end(b2)) { 
      either = true; 
      r2.push_back(x); 
     } 

     if (either) { 
      both.push_back(x); 
     } 
    } 
    return std::make_tuple(std::move(r1), std::move(r2), std::move(both)); 
} 



int main() 
{ 

    using namespace std; 

    vector<unsigned> A { 2,4,6,8,9,10,34,74,79,81,89,91,95 }; 
    vector<pair<unsigned,unsigned> > B1={ {4, 5}, {8, 10}, {90, 99} }; 
    vector<pair<unsigned,unsigned> > B2={ {2, 3}, {29, 40}, {60, 85} }; 

    auto results = find_everything(A, B1, B2); 
    const auto& r1 = std::get<0>(results); 
    const auto& r2 = std::get<1>(results); 
    const auto& both = std::get<2>(results); 
    copy(begin(r1), end(r1), ostream_iterator<unsigned>(cout, ", ")); 
    cout << endl; 

    copy(begin(r2), end(r2), ostream_iterator<unsigned>(cout, ", ")); 
    cout << endl; 

    copy(begin(both), end(both), ostream_iterator<unsigned>(cout, ", ")); 
    cout << endl; 

    return 0; 
} 

erwarteten Ergebnisse:

4, 8, 9, 91, 95, 
2, 34, 74, 79, 81, 
2, 4, 8, 9, 34, 74, 79, 81, 91, 95, 

Weitere Arbeit:

Es gibt zwei sofort offensichtliche Verbesserungen, die wir machen könnten, wenn die Datensätze groß sind:

1. Da A, B1 und B2 sortiert sind, können wir „Strom“ entsprechen Iteratoren verfolgen, den Suchraum für jedes Spiel oder nicht-Spiel zu reduzieren (das beginnt für std::lower_bound zu argumentieren)

2. oder wenn A ist deutlich größer als B1 und B2, wir könnten die Suche parallelisieren.

Haben Sie Spaß :)