Discussion :

[Colbix]

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.

[alskaar]

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

[JolyLoic]

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.

[koala01]

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

[Colbix]

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 !

[mchk0123]

Il n'y a pas de hash table en standard C++, même si beaucoup de compilateurs en fournissent une version.

Tu parles de hash_map ? Elle est pas standardisée ?

Mince alors, pourtant on la retrouve partout (VC++, Builder, gcc, ...)

[alskaar]

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é.

[koala01]

(...)
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.
(...)

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

[JolyLoic]

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

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.

( qui en fonction de l'implementation est peut etre en arbre )

Je ne vois pas trop comment implémenter std::map autrement qu'avec un arbre.