Die beste Methode zum Zusammenführen mehrerer STL-Container, doppelte Elemente entfernen?

Question

Ich habe zwei STL-Container, die ich zusammenführen möchte, entfernen alle Elemente, die mehr als einmal angezeigt werden. Zum Beispiel:

typedef std::list<int> container; 
container c1; 
container c2; 

c1.push_back(1); 
c1.push_back(2); 
c1.push_back(3); 

c2.push_back(2); 
c2.push_back(3); 
c2.push_back(4); 

container c3 = unique_merge(c1, c2); 
// c3 now contains the following 4 elements: 
// 1, 2, 3, 4 

std :: einzigartig scheint nur für benachbarte Elemente zu sein, und in meinem Fall die Behälter in beliebiger Reihenfolge sein könnten. Ich konnte einige std :: tun List gesetzt Ich denke:

container unique_merge(const container& c1, const container& c2) 
{ 
    std::set<container::value_type> s; 
    BOOST_FOREACH(const container::value_type& val, c1) 
     s.insert(val); 
    BOOST_FOREACH(const container::value_type& val, c2) 
     s.insert(val); 
    return container(s.begin(), s.end()); 
} 

Gibt es einen besseren Weg, oder habe ich etwas Blutungen offensichtlich verpasst?

Answer 1

Für eine ungeordnete Liste ist Ihr Set-Trick wahrscheinlich einer der besten. Jede Einfügung sollte O (log n) sein, mit N Einfügungen erforderlich, und das Durchlaufen wird O (n) sein, was O (N * log n) ergibt. Die andere Option besteht darin, std :: sort für jede einzelne Liste einzeln auszuführen und dann parallel durchzugehen, indem Sie std::set_union verwenden, wodurch Duplikate für Sie entfernt werden. Dies ist auch O (n * log n). Wenn Sie sich Sorgen um die Leistung machen, müssen Sie ein Profil erstellen. Wenn Sie nicht sind, tun Sie, was auch immer für Sie sinnvoller ist.

Edit: set_union wird nur funktionieren, wenn es keine Duplikate in den ursprünglichen Listen sind, sonst werden Sie mit sort, merge, unique und erase gehen. Die große O-Leistung ist immer noch die gleiche, mit den gleichen Vorbehalte gegenüber Profiling.

template <typename container> 
container unique_merge(container c1, container c2) 
{ 
    std::sort(c1.begin(), c1.end()); 
    std::sort(c2.begin(), c2.end()); 
    container mergeTarget; 
    std::merge(c1.begin(), c1.end(), c2.begin(), c2.end(), 
     std::insert_iterator(mergeTarget, mergeTarget.end()) 
    ); 
    std::erase(
     std::unique(mergeTarget.begin(), mergeTarget.end()), 
     mergeTarget.end() 
    ); 

    return mergeTarget; 
} 

Answer 2

Können Sie std::merge nicht verwenden, um sie zusammenzuführen und dann Duplikate zu entfernen? Allerdings müssen die Container sortiert werden.

Answer 3

Verwenden Sie die std::set_union algorithm von der STL. Sie müssen Ihre Eingangslisten jedoch zuerst sortieren - oder Kopien Ihrer Eingangslisten erstellen, sie sortieren und dann std :: set_union verwenden.

Answer 4

Sie müssen entweder (explizit oder implizit über einen sortierten Container wie set) sortieren.

Es gibt ein allgemeines Idiom, das std :: sort/std :: unique/std :: erase verwendet, um eindeutige Elemente in einem Container zu erhalten.

So erstellen Sie einen Container mit dem Inhalt von c1, fügen Sie den Inhalt von c2, dann sortieren, verschieben Sie eindeutige Elemente an das Ende, und löschen Sie sie. So etwas wie dieses:

container c(c1.begin(), c1.end()); 
c.insert(c.end(), c2.begin(), c2.end()); 
c.erase(std::unique(c.begin(), c.end()), c.end());