Discussion :

[pierrotlenageur]

Bonjour, je suis etudiant en 3eme anée dinformatique et dans le cadre de mon projet de licence je m'interesse a la facon dont sont gerer les données au sein d'un set, et de ce fait la complexité des algorithme (insert et find notamment)
j'ai deja bien cherché mais ce que je trouve ne semble pas concorder puisque j'ai vu que les set etait generalement implementé a la facon des ABR voire des arbre rouge et noir, cependant jai egalement vu ke les operations etait en O(n), et enfin j'ai egalement entendu parler de conteneur associatif avec des histoires de (clés,value) que je ne comprend pas tres bien avrai dire. si quelquun pouvait meclairer dici la fin de semaine sur la veritable implementation.. Alors dans ce cas merci beaucoup d'avance

[koala01]

Salut,

Les set sont tout simplement des arbre binaires.

Que tu les nomme arbre binaire, arbre rouge noir ou ABR, ce n'est en définitive chaque fois que la même chose, à quelques détails minimes près

La recherche se fait en O(log(n)) selon le principe du

• si je cherche une valeur plus petite que la valeur actuelle, je vais à gauche
• si je cherche une valeur plus grande, je vais à droite
• si la valeur que je recherche n'est pas plus petite que la valeur actuelle, et qu'elle n'est pas non plus plus grande, c'est donc que j'ai trouvé la valeur que je cherchais (il s'agit en réalité de trouver une équivalence de valeur, et non une égalité)

La complexité de l'insertion est généralement algorithmique ou algorithmique amortie (en Nlog(N) s'il s'agit d'insérer N éléments préalablement triés)

La différence entre la map et le set tient tout simplement dans le fait que la clé (la valeur identifiant l'objet de manière unique) et l'objet sont deux choses différentes pour la map (p.e map<int, objet> ou l'entier est la clé et objet est... l'objet (qui l'aurait deviné :quesiton ) alors que la clé est l'objet pour le set, mais il s'agit dans les deux cas de conteneurs associatifs.
Si la clé n'est pas un type primitif - qu'il s'agisse de la clé pour les map ou de l'objet pour les set - il s'agira de prévoir un prédicat permettant de déterminer si objet1 est plus petit que objet2 (prédicat "less")

[loufoque]

La recherche comme l'insertion sont logarithmiques, et ce sans analyse amortie.

[pierrotlenageur]

Merci beaucoup pour cette reponse rapide et claire. Bonne continuation!

[JolyLoic]

Petit détail : Les set et map sont implémentés sous forme d'arbres rouges noirs, mais l'interface d'utilisation de ces conteneurs fait totalement abstraction de ça, et l'utilisateur peut très bien ignorer que ce genre d'arbres est utilisé derrière. D'où la notion d'interface par clef/valeur pour les maps, et non une notion de parcours d'arbre.