¿La mejor manera de combinar varios contenedores STL, eliminando elementos duplicados?

Question

Tengo dos contenedores STL que deseo fusionar, eliminando los elementos que aparecen más de una vez. Por ejemplo:

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 :: única parece ser sólo elementos adyacentes, y en mi caso los contenedores podrían estar en cualquier orden. Podría hacer algunas std :: set engaño supongo:

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

¿Hay una mejor manera o he perdido algo de sangrado obvio?

Answer 1

Para una lista desordenada, su truco es probablemente uno de los mejores. Cada inserción debe ser O (log n), con N inserciones requeridas, y el desplazamiento será O (n), lo que le dará O (N * log n). La otra opción es ejecutar std :: sort en cada lista individualmente y luego recorrerlas en paralelo usando std::set_union, que elimina los duplicados por usted. Esto también será O (n * log n), por lo que si le preocupa el rendimiento, tendrá que crear un perfil. Si no lo eres, haz lo que tenga más sentido para ti.

Editar: set_union sólo funcionará si no hay duplicados en las listas originales, de lo contrario tendrá que ir con sort, merge, unique y erase. El gran rendimiento de O sigue siendo el mismo, con las mismas advertencias sobre el perfil.

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

¿No puede usar std::merge para fusionarlos y luego eliminar los duplicados? Sin embargo, requiere que se clasifiquen los contenedores.

Answer 3

Utilice std::set_union algorithm del STL. Sin embargo, primero tendrá que ordenar sus listas de entrada, o crear copias de sus listas de entrada, ordenarlas y luego usar std :: set_union.

Answer 4

Va a necesitar ordenar (explícita o implícitamente a través de un contenedor clasificado como conjunto).

Hay una expresión común que usa std :: sort/std :: unique/std :: erase para obtener elementos únicos en un contenedor.

Cree un contenedor con los contenidos de c1, anexe el contenido de c2, luego ordene, mueva elementos únicos hasta el final y bórrelos. Algo como esto:

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