Recherche Sequence ou Sub-Sequence ds un Vector

Bonjour,

j'ai deux vecteurs de string et je veux retrouver la sequence du second vector ds le premier sinon je recherche une subsequence (je recherche les elements ds l'ordre, les subsequences commencent tjs par le premier element de vect2)

example 1
Vect_1 < "JAVA", "ADA", "C", "C++", "C#">
Vect_2 < "C++", "C#">

la recherche de vect_2 sequence ds vect_1 va me retourner vect_1 position 3 avec length 2

example 2
Vect_1 < "JAVA", "ADA", "C", "C++", "C#">
Vect_2 < "JAVA", "C#">

la recherche vect_2 sequence ds vect_1 va me retourner vect_1 position 0 avec length 1

je me demande si il y a un moyen simple et pas couteux pour faire ça (avant de me lancer ds des boucles for imbriquées)

merci de votre aide

hum il y'a std::set_intersection mais ça va te trouvé tout les éléments en commun. Sur ton exemple ça marcherait, sur du réel je sais pas si t'as plusieurs séquences distinctes.

Citation:

---

Envoyé par Goten

hum il y'a std::set_intersection mais ça va te trouvé tout les éléments en commun. Sur ton exemple ça marcherait, sur du réel je sais pas si t'as plusieurs séquences distinctes.

---

pour utiliser std::set_intersection il faut que les sequences soit triées avant tout, ce qui n'est pas mon cas
en plus l'intersection peux me trouver les elements mais pas dans le bon ordre, alors que pour moi les element trouvés doivent avoir le meme ordre ds les 2 vectors


example
Vect_1 < "JAVA", "ADA", "C", "C++", "C#">
Vect_2 < "C#", "C++">

la recherche de vect_2 sequence ds vect_1 va me retourner vect_1 position 4 avec length 1 ie seulement "C#" et pas l'intersection (C++, C#)

des idées :roll:

bon je me lance ds mes boucles For en attendant

merci

Je ne crois pas que ce soit possible de manière simple avec les algos de la STL. Désolé, il va effectivement falloir y aller à coup de boucle For ! :mouarf:

En revanche, si tu as accès à Boost, alors Boost.Range et Boost.Algo fournissent une superbe solution au problème :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <string> #include <vector> #include "boost/range.hpp" #include "boost/algorithm/string/find.hpp"   int main() { std::vector<std::string> v1; v1.push_back("JAVA"); v1.push_back("C"); v1.push_back("C++"); v1.push_back("C#");   std::vector<std::string> v2; v2.push_back("C++"); v2.push_back("C");   boost::sub_range<std::vector<std::string>> subrange; surbrange = boost::algorithm::find_first(v1, v2);   if(subrange.begin() != v1.end()) { std::cout << "Position : " << std::distance(v1.begin() , subrange.begin()) << std::endl; std::cout << "Longueur : " << subrange.size() << std::endl; } }

---

Bizarrement, le concept de range issu de Boost avait été proposé pour être inclus dans la nouvelle norme C++0x mais n'a pas été accepté ! C'est dommage...

std::search est directement fait pour ça, si j'ai bien compris.

Citation:

---

Envoyé par JolyLoic

std::search est directement fait pour ça, si j'ai bien compris.

---

le search marche bien :king:

merci