Hello,
 
Quelle est la méthode la plus rapide pour chercher un élément dans un vector ? J'ai deux cas de figures précis :

• Ce que je cherche est unique dans le vector
• Ce que je cherche est la première valeur correspondante en partant de "vector [0]"

Pour l'instant je fais bête et méchant, une boucle for qui déroule tout le vector un par un jusqu'à rencontrer ce que je veux. Mais comme j'ai un grand nombre de lignes ça met pas mal de temps... Je n'ai pas trouvé de fonction "search" ou "find" dans la doc    
 
Merci !

Salut !
 
   Dans les algorithmes de la STL tu trouvera le std::find. Mais il fera la même chose que ton for...
   Pour optimiser, je dirai qu'il faudrai définir une relation d'ordre sur tes éléments et faire une recherche dichotomique.  
Après je sais pas si c'est compatible avec ton problème...

suivant les types d'accès que tu as a faire et la nature des élements, l'idée serait d'utiliser des conteneurs croisés. (soit maison soit les trucs de boost)

Merci   .
 
Pas de recherche dichotomique possible dans la plupart des cas, je travaille beaucoup avec des strings. Le truc qui m'aiderait le plus serait une fonction qui puisse, à partir du tableau suivant, me retourner tous les "numéros de ligne" (n'étant pas programmateur de métier le vocabulaire m'échappe...) pour lesquels une condition est remplie, par exemple que le champ soit égal à "Paris".
 
Ligne || Valeur
0 || Marseille
1 || Paris
2 || Nantes
3 || Paris
...
 
Mon vector de travail est donc un vector <string>, et en retour je veux un vector <int> avec les numéros de ligne.
 
Bien sûr je peux coder ça moi-même, mais j'ai dans l'idée que si ça existe déjà ça sera un peu plus optimisé que mon approche amateur...
 
J'espère que mon exemple éclaircit ce dont j'ai besoin.
 
L'idée des conteneurs croisés m'a l'air sympa, mais après un peu de recherche dans les librairies de boost je n'ai pas réussi à trouver quelle section en parlait. Tu peux m'aiguiller un peu ?
http://www.boost.org/doc/libs/1_35 [...] raries.htm
 
Merci d'avance !

 
moi non plus, ça c'est un programmateur :

 
et ça un prograMMEUR :

 
pour ton problème, y a pas de miracle à moins de changer de SDD.

si je puis me permettre, une recherche dichotomique c'est possible sur des string : tu as l'ordre alphabétique...
 
enfin après vous voyez

d'un autre coté c'est un programmeur flou

 
bah regarde là:
http://www.boost.org/doc/libs/1_35 [...] ast_lookup

il est possible d'établir une relation d'ordre sur des chaines, sinon le tri alphabetique n'existerai pas.
 
mon idée est que tu devrais utiliser un "set" voire meme une "map" si ca te chante pour associer des nombres a tes chaines.
(cependant avec le "set" tu n'en aura plus besoin).
 
tout deviendra alors logarithmique en temps d'acces et de recherche.
(autant dire instantané par rapport au linéaire qui te prend actuellement un temps au moins "visible" par un humain si j'ai bien compris)
 
pour rechercher, tu devras alors utiliser ton_set.find(ta_chaine_a_trouver) et déréférencer l'itérateur pour acceder au contenu. (comme un pointeur)
 
choisir sa structure de donnée correctement en fonction des complexités algoroithmiques et les besoins de l'utilisateur est un probleme classique de l'ingéniérie logicielle.
évidemment, ce n'est pas le travail d'un non professionel, et on le concoit bien.

Pour la recherche dichotomique en fait c'est parce que je travaille avec une bdd clientèle, qui est ordonnée par date, et donc si je commence à tout trier ça va vite être le bordel pour la lisibilité  
 
Le concept de set/map j'aime bien, c'est en gros ce à quoi je pensais et c'est toujours mieux que de réinventer la roue avec la création de 50 fonctions déjà existantes   L'utilisateur étant moi-même, je ne m'embête pas avec la sophistication que je demanderai à un vrai ingé informatique, mais ça fait du bien aux neurones  
 
Par contre la page de boost indiquée emploie des mots (et des codes) qui échappent pour l'instant à mon petit cerveau !
 
Merci à tous en tous cas (et désolé pour le "programmateur" )

wof. si le jeu de données est fixe, la dichotomie est meilleure. Tu tries une fois pour toute et après ça roule.

sinon t'as toutes les blagues pour annuaire genre "trie"

recherche de toutes les valeurs "Paris" dans un vecteur non trié (ici on affiche les valeurs)
 

 
Avec un vecteur trié dans l'ordre lexicographique, comme le conseille à juste titre Taz :
 

 
sous reserve de boulettes, j'ai pas testé.
Pour compléter ce qu'a dit Taz, l'intérêt du vecteur trié face au std::set c'est qu'on évite la charge de tous ces pointeurs qu'on trouve dans les nodes des std::set et std::map. C'est à la fois + rapide et - gourmand en mémoire.