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.
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Des info sur Vector de la STL
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.
Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.
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
A méditer: La solution la plus simple est toujours la moins compliquée
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 ?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
Salut,
Koala01 écrit:
Pas mal. Une recherche dichotomique dans un vector<T> qui stocke ses données sans ordre de tri.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"...
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
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.
Je ne vois pas trop comment implémenter std::map autrement qu'avec un arbre.
Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.
merci pour les infos sur la hash_map
bin justement la hash_map ne se fait pas avec un arbre !
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).
SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.
"Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
Apparently everyone. -- Raymond Chen.
Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.
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 !
Répondre avec citation
Partager