Voila, j'aimerai savoir quelques petites choses sur la class Vector de la STL.
- Si elle est récursive
- La complexité de son algo de recherche (si c'est une recherche dichotomique, ou quelquechose du genre).
Merci d'avance, a bientôt.
Version imprimable
Voila, j'aimerai savoir quelques petites choses sur la class Vector de la STL.
- Si elle est récursive
- La complexité de son algo de recherche (si c'est une recherche dichotomique, ou quelquechose du genre).
Merci d'avance, a bientôt.
le find sur un vector fait une iteration sur le tableau donc c'est du O(n).
si tu veux un algo de type dichotomie te faut comme predicat que l'ensemble est ordonné.
si tu veux une recherche avec une fonction de hash tu auras aussi un conteneur specifique.
je suis pas aller voir le code mais le find sur un set doit en ln(n) et celui d'une map ... le temps du calcule du hash + x
pour choisir le bon contener:
http://c.developpez.com/faq/cpp/?pag...hoix_conteneur
La recherche dans une map est aussi en O(log n), la map n'étant pas basée sur une hash table, mais sur un arbre. Il n'y a pas de hash table en standard C++, même si beaucoup de compilateurs en fournissent une version, et si le TR1 (un avant goût du prochain standard, déjà disponible depuis un certain temps) en propose aussi, sous le nom unordered_map.
Salut,
Le std::vector réagit finalement exactement de la manière dont réagit un tableau "C style", hormis, bien sur que tu ne dois pas t'occuper de l'allocation de la mémoire, et qu'il fournit des méthodes de gestion efficaces (copie, ajout, suppression, insertion, itérateur etc.)
Si tu veilles à ce que ton tableau soit trié, rien ne t'empeche de faire une recherche dichotomique exactement comme tu la ferait sur un tableau C style, en prenant tableau.size()-1 comme indice du dernier élément du tableau (car, dans les vector, le premier élément est lui aussi à l'indice 0 ;) )
Ceci dit, si tu as des contraintes associative et/ou d'unicité, set et map - et leur pendant multiset et multimap - peuvent s'avérer plus intéressants
Merci pour ces infos,
J'avais déjà pensé au map, je vais donc faire mon propre algo de rechrche...
A bientôt, je vous tien au courant !
Tu parles de hash_map ? Elle est pas standardisée ?Citation:
Envoyé par JolyLoic
Mince alors, pourtant on la retrouve partout (VC++, Builder, gcc, ...)
ouep j etais incomplet :p merci de me reprendre ;)
http://www.sgi.com/tech/stl/hash_map.html
je crois que la hash_map a été plus ou moins abandonné au profit de la map
( qui en fonction de l'implementation est peut etre en arbre )
l'idée est surtout que la fonction de recherche depend du conteneur et de la maniere de trier ou non les elements. ca a pas de sens de faire une recherche dichotomique si les elements sont pas triés.
Au final les conteneurs qui ont une implementation qui permet une recherche plus rapide que l'iteration ont un find() implementé.
C'est meme purement et simplement impossible, car, comment décider, si on est sur un élément qui n'est pas celui recherché, d'aller voir sur sa gauche ou sur sa droite si on n'est pas sur, par exemple, d'avoir des élément N-1<N<N+2:question:Citation:
Envoyé par alskaar
Salut,
Koala01 écrit:
Pas mal. Une recherche dichotomique dans un vector<T> qui stocke ses données sans ordre de tri.Citation:
Le std::vector réagit finalement exactement de la manière dont réagit un tableau "C style", hormis, bien sur que tu ne dois pas t'occuper de l'allocation de la mémoire, et qu'il fournit des méthodes de gestion efficaces (copie, ajout, suppression, insertion, itérateur etc.)
Si tu veilles à ce que ton tableau soit trié, rien ne t'empeche de faire une recherche dichotomique exactement comme tu la ferait sur un tableau C style, en prenant tableau.size()-1 comme indice du dernier élément du tableau (car, dans les vector, le premier élément est lui aussi à l'indice 0 )
Je n'y avais pas pensé...
Selon moi, "dichotomie" est tout à fait incompatible avec "sans ordre de tri"...Citation:
Envoyé par dj.motte
Quand on y pense, "dichotomie" signifie "prend l'élément qui se trouve à la moitié de ce qu'il reste et, s'il n'est pas l'élément recherché, supprimes la moitié dont on est sur qu'elle ne contient pas l'élément recherché des possibilités avant de recommencer avec la moitié restante"...
Or, comment arriver à déterminer "la moitié dont on est sur qu'elle ne contient pas l'élément recherché" si les élements ne sont pas triés :question:
Elle n'a pas été abandonnée au profit de quoi que ce soit. Seule une question de temps a fait qu'elle ne fait pas partie du standard actuel (datant de 98). Elle fera assurément partie du prochain standard, et est déjà à moitié standardisée.Citation:
Envoyé par alskaar
Je ne vois pas trop comment implémenter std::map autrement qu'avec un arbre.Citation:
Envoyé par alskaar
merci pour les infos sur la hash_map
bin justement la hash_map ne se fait pas avec un arbre !Citation:
Envoyé par JolyLoic
bin justement std::map et std::hash_map sont 2 choses différentes :
std::map -> arbre
std::hash_map -> hash
J'crois que c'est clair ! ;-)
Il y a déjà des algorithmes pour la recherche dichotomique dans la bibliothèque standard, qui peuvent s'appliquer à n'importes quels itérateurs.
Quelle ou quelles structures de la stl sont déjà implémentées ?
Je recherche une structure qui me permet de stocker des objets ou des pointeurs vers ceux-ci dans l'ordre et il faudrait être très efficace parceque cette structure peut comporter jusqu'à 5000 objets ou pointeurs vers les objets.
Si vous avez des idées, ou proposition, je suis tout ouï !
Merci pour vos réponses !
A bientôt !
Si tu n'as pas besoin de tableau associatif, tu peux utiliser un std::set, c'est un conteneur trié (arbre).
---> Accès en O(log n) par recherche dichotomique (ben oui, c'est typiquement un arbre binaire de recherche).
Super, merci, je vai essayer, c'est pil poil ce que je cherchai, j'hésitai même a me faire un class arbre binaire moi même. lol ;)
Merci je vous tien au courant !
A+ dans le bus !