J'essaie de comparer deux objets vectoriels et de renvoyer un vecteur unique contenant tous les caractères qui apparaissent dans les deux vecteurs.
Comment ira-je à ce sujet sans écrire une méthode manuelle horriblement complexe qui compare tous les caractères dans le premier vecteur à chaque charcuter dans le deuxième vecteur et à l'aide d'un autre pour l'ajouter à un troisième vecteur (qui serait renvoyé) si elles match.
Peut-être que mon manque d'expérience réelle avec les vecteurs me fait imaginer que cela sera plus difficile que ce sera vraiment, mais je soupçonne qu'il y a une manière plus simple que je n'ai pas été incapable de trouver grâce à la recherche.
7 Réponses :
Peut-être devriez-vous utiliser STD :: Strings au lieu de vecteurs, si vous avez des personnages entre eux? Les chaînes ont beaucoup de fonctionnalités pour la recherche, etc.
Je pense que vous recherchez std :: set_intersection code> . Les vecteurs source doivent être triés cependant. Si vous ne vous souciez pas de l'ordre de votre vecteur de sortie, vous pouvez toujours l'exécuter sur des copies triées de vos vecteurs source.
et BTW, la voie naïve manuelle n'est pas terriblement complexe. Compte tenu de deux vecteurs source s1 code> et s2 code> et d'un vecteur de destination det code>, vous pouvez écrire quelque chose qui ressemble à ceci: p> for (std::vector<char>::iterator i = s1.begin(); i != s1.end(); ++i)
{
if (std::find(s2.begin(), s2.end(), *i) != s2.end())
{
dest.push_back(*i);
}
}
Merci. Je m'attendais à ce que ce soit comme ça.
La réponse de Kristo @Billyonéal ne comprenait pas cette partie lorsque j'ai quitté le commentaire.
@ Jon-Eric: En fait, il l'a fait. La première révision a cette information. Vérifiez l'historique de modification si vous ne me croyez pas.
Ok les gars, pas besoin de discuter. J'ai construit ma réponse avec plusieurs modifications de succession rapide. Apparemment, tous n'étaient pas enregistrés comme des révisions séparées par le moteur SO.
Il est important de noter que binary_search nécessite que la plage soit commandée, de sorte que la mise en œuvre manuelle ne fonctionne que si S2 est en fait commandé. Si aucune des gammes n'est commandée, vous pouvez utiliser std :: trouver au lieu de std :: binaire_search qui sera plus lent ( o (n ^ 2) pour l'algorithme entier) mais ne nécessite pas de commander.
@David, bonne prise. Je pense que je mettais à jour ma réponse alors que vous avez écrit votre commentaire. :-)
int temp[5000]; // declare this globally if you're going to be
// doing a lot of set_intersection calls
int main() {
char x[]={'a','b','c','d','e'};
char y[]={'b','c','g'};
vector<char> v1(x,x+sizeof x/sizeof x[0]);
vector<char> v2(y,y+sizeof y/sizeof y[0]);
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end()); // the vectors *must* be sorted!!!!!!
vector<char> inter=vector<char>(temp,set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),temp)); // inter contains {'b','c'}
int cnt=set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),temp) - temp; // cnt=2
for(int i = 0; i < (int)inter.size(); ++i) {
cout<<inter[i]<<" ";
}
cout<<endl;
return 0;
}
Permettez-moi de vérifier cela, comme je pense que cela m'a aidé à comprendre les choses à propos de Set_InterSection que j'ai trouvé depuis la publication de la question. Inter contient B et C, qui sont les caractères communs à x et y non?
@Sam Phelps - Oui, c'est vrai. Et CNT contient le nombre d'éléments qui se trouvent dans l'intersection (je viens de mettre cela au cas où vous n'aviez besoin que d'obtenir le nombre d'éléments intersectés pour une raison quelconque).
Il peut être plus clair d'utiliser Insérer des itérateurs au lieu d'attribuer une matrice de taille fixe pour votre vecteur de destination.
Si je devais faire cela sur deux vecteurs non traduits (sans aide de la bibliothèque), je pense que j'ajouterais tous les éléments d'un à une hache, puis itérale à travers la seconde levant chacun - devrait être plus efficace que de trier les deux liste d'abord aussi.
Cela ne s'étend pas bien au-delà du type de caractère standard (peut-être à UNICODE, en fonction de l'application), mais si vous êtes intéressé à le faire dans O (n) temps, cela devrait fonctionner.
#include <vector>
#include <string>
#include <iostream>
std::vector<char> intersect(const std::vector<bool>& x,
const std::vector<bool>& y)
{
std::vector<char> rv;
std::vector<bool>::const_iterator ix, iy;
size_t i;
for (i=0, ix = x.begin(), iy = y.begin();
ix != x.end() && iy != y.end();
++i, ++ix, ++iy)
if (*ix && *iy) rv.push_back( (char) i);
return rv;
}
std::vector<bool> poll(const std::vector<char>& x)
{
std::vector<bool> rv(256, false);
for (std::vector<char>::const_iterator i = x.begin(); i != x.end(); ++i)
rv[*i] = true;
return rv;
}
std::vector<char> build(const std::string& val)
{
std::vector<char> rv;
for (size_t i = 0; i < val.size(); ++i)
rv.push_back(val[i]);
return rv;
}
int main(int argc, char *argv[])
{
std::vector<char> x1 = build("The Quick Brown Fox Jumps Over The Lazy Dog");
std::vector<char> x2 = build("Oh give me a home where the buffalo roam");
std::vector<char> intersection = intersect(poll(x1), poll(x2));
for (std::vector<char>::iterator i=intersection.begin();
i != intersection.end(); ++i)
std::cout << *i;
std::cout << std::endl;
return 0;
}
Comme il s'avère de votre question ultérieure, vous ne vous souciez que de 26 caractères: en fait un avec boost_foreach, le code a même l'air raisonnable: P> bitset wchar_t code>. P> assert(UCHAR_MAX <= 512 && "What kind of crazy machine is this?");
std::bitset<UCHAR_MAX> in;
BOOST_FOREACH(unsigned char c, first) {
in[c] = true;
}
BOOST_FOREACH(unsigned char c, second) {
if (in[c]) {
result.push_back(c);
// this line is only needed if 'second' can contain duplicates
in[c] = false;
}
}
Modifié le titre légèrement car dans l'incarnation précédente, on dirait que vous recherchiez
std :: vecteur :: opérateur << / code> :)