Extrait l'élément de 2 vecteurs?

Question

J'ai 2 vecteur avec un a vec1 {e1, e2, e3, e4} et l'autre avec vec2 {e2, e4, e5, e7}

Comment obtenir trois vecteur efficace de vecteurs ci-dessus, tels que 1.has éléments qui ne sont disponibles que dans vec1 de même 2 ne dispose que vec2 éléments et 3.Avec éléments communs

Answer 1

std::set_intersection devrait faire l'affaire, si les deux vecteurs sont classés: http://msdn.microsoft.com/en-us/library/zfd331yx.aspx

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3)); 

Un prédicat personnalisé peut être utilisé pour la comparaison aussi:

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3), my_equal_functor()); 

Si elles ne sont pas triés, vous pouvez les trier bien sûr d'abord, ou bien, vous pouvez itérer vec1, et pour chaque élément, utilisez std :: find pour voir si elle existe dans vec2.

Answer 2

Si le nombre d'éléments est faible, vous pouvez utiliser l'approche naïve qui est facile à implémenter et qui a un temps d'exécution O (n).

Si vous avez un grand nombre d'éléments, vous pouvez créer une table de hachage à partir de l'un d'eux et y rechercher les éléments d'autres vecteurs. Alternativement, vous pouvez trier l'un d'eux et la recherche binaire à travers elle.

Answer 3

Le problème que vous décrivez est l'intersection vectorielle. Cela dépend de la taille des vecteurs d'entrée.

Si les tailles des deux vecteurs sont proches l'une de l'autre, une fusion (comme dans un tri par fusion) est la meilleure. Si un vecteur est beaucoup plus petit que l'autre, procédez comme suit: Pour chaque élément du vecteur plus petit, recherchez cet élément dans le plus grand vecteur en utilisant la recherche binaire.

Ceci est un problème courant dans la recherche d'information, où vous devez recouper des indices inversés. Il y a des documents de recherche à ce sujet.

Answer 4

Ce que vous demandez est vec3 être l'intersection des deux autres. Jalf montre comment remplir vec3 en utilisant la fonction std::set_intersection de the <algorithm> header. Mais rappelez-vous que pour que les fonctions set fonctionnent, les vecteurs doivent être triés.

alors vous voulez vec1 et vec2 pour être la différence entre eux et vec3. Dans la notation de jeu:

Vous pouvez utiliser la fonction std::set_difference pour cela, mais vous ne pouvez pas l'utiliser pour modifier les vecteurs en place. Vous auriez à calculer un autre vecteur pour tenir la différence:

std::vector<foo> temp; 
std::set_difference(vec1.begin(), vec1.end(), 
        vec3.begin(), vec3.end(), 
        std::back_inserter(temp)); 
vec1 = temp; 
temp.clear(); 
std::set_difference(vec2.begin(), vec2.end(), 
        vec3.begin(), vec3.end(), 
        std::back_inserter(temp)); 
vec2 = temp;