La meilleure façon de fusionner plusieurs conteneurs STL, en supprimant les éléments en double?

Question

J'ai deux conteneurs STL que je veux fusionner, en supprimant tous les éléments qui apparaissent plusieurs fois. Par exemple:

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, semble être pour les éléments adjacents seulement, et dans mon cas, les conteneurs pourrait être dans un ordre quelconque. Je pourrais faire quelques std :: set supercherie je suppose:

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

Y at-il une meilleure façon ou d'avoir manqué quelque chose que je saignement évident?

Answer 1

Pour une liste non ordonnée, votre tour de jeu est probablement l'un des meilleurs. Chaque insert doit être O (log n), avec N insertions requises, et traverser sera O (n), vous donnant O (N * log n). L'autre option consiste à exécuter std :: sort sur chaque liste individuellement, puis de les parcourir en parallèle en utilisant std::set_union, ce qui supprime les doublons pour vous. Ce sera également O (n * log n), donc si vous êtes inquiet au sujet de la performance, vous devrez le profiler. Si ce n'est pas le cas, faites ce qui vous semble le plus logique.

Edit: set_union ne fonctionnera que s'il n'y a pas de doublons dans les listes originales, sinon vous devrez aller avec sort, merge, unique et erase. La grande performance O est toujours la même, avec les mêmes mises en garde sur le profilage.

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

Ne pouvez-vous pas utiliser std::merge pour les fusionner, puis supprimer les doublons? Cependant, les conteneurs doivent être triés.

Answer 3

Utilisez le std::set_union algorithm à partir de la STL. Vous devrez d'abord trier vos listes d'entrées - ou créer des copies de vos listes d'entrée, les trier, puis utiliser std :: set_union.

Answer 4

Vous devrez trier (soit explicitement, soit implicitement via un conteneur trié tel que set).

Il existe un idiome courant utilisant std :: sort/std :: unique/std :: erase pour obtenir des éléments uniques dans un conteneur.

Créez donc un conteneur contenant le contenu de c1, ajoutez le contenu de c2, puis triez, déplacez les éléments uniques jusqu'à la fin et effacez-les. Quelque chose comme ceci:

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