Najlepszy sposób na połączenie wielu kontenerów STL, usuwanie duplikatów elementów?

Question

Mam dwa kontenery STL, które chcę scalić, usuwając wszelkie elementy, które pojawiają się więcej niż raz. Na przykład:

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 :: unique wydaje się być tylko dla sąsiednich elementów, aw moim przypadku kontenery mogą być w dowolnej kolejności. Mógłbym zrobić kilka std :: set oszustwa Chyba:

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

Czy istnieje lepszy sposób lub mieć coś przeoczyłem krwawienie oczywiste?

Answer 1

W przypadku list nieuporządkowanych, ustawiona sztuczka jest prawdopodobnie jedną z najlepszych. Każda wstawka powinna mieć postać O (log n), przy czym wymagane są wstawki N, a przejście będzie O (n), dając O (N * log n). Inną opcją jest uruchamianie std :: sort na każdej liście osobno, a następnie przechodzenie przez nie równolegle za pomocą std::set_union, która usuwa duplikaty dla ciebie. Będzie to również O (n * log n), więc jeśli martwisz się o wydajność, będziesz musiał profilować. Jeśli nie jesteś, rób to, co ma dla ciebie większy sens.

Edit: set_union będzie działać tylko wtedy, gdy nie ma duplikatów w oryginalnym list, w przeciwnym razie będziesz musiał iść z sort, merge, unique i erase. Duża wydajność O jest wciąż taka sama, z tymi samymi zastrzeżeniami dotyczącymi profilowania.

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

Nie możesz użyć numeru std::merge, aby je scalić, a następnie usunąć duplikaty? Nie wymaga to jednak sortowania pojemników.

Answer 3

Użyj std::set_union algorithm ze STL. Najpierw jednak musisz posortować listy wejściowe - lub utworzyć kopie list wejściowych, posortować je, a następnie użyć polecenia std :: set_union.

Answer 4

Będziesz musiał albo sortować (albo jawnie, albo niejawnie przez posortowany kontener, taki jak zestaw).

Istnieje popularny idiom używający std :: sort/std :: unique/std :: erase, aby uzyskać unikalne elementy w kontenerze.

Stwórz więc kontener z zawartością c1, dopisz zawartość c2, a następnie posortuj, przenieś unikatowe elementy na koniec i usuń je. Coś w tym stylu:

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