Comment fonctionnent les multisets? Si un ensemble ne peut pas avoir une valeur mappée sur une clé, ne contient-il que des clés?
Aussi, comment fonctionnent les conteneurs associatifs? Je veux dire que le vecteur et la deque dans la mémoire sont situés de manière séquentielle, cela signifie que la suppression / la suppression (sauf début [deque] et la fin [vecteur, deque]) sont lentes si elles sont grandes.
et la liste est un ensemble de pointeurs qui ne sont pas localisés de manière séquentielle dans la mémoire qui provoque une recherche plus longue, mais plus vite Supprimer / Supprimer.
Comment sont les ensembles, les cartes, les multisets et les multimaps stockés et comment fonctionnent-ils?
3 Réponses :
Il peut y avoir n'importe quelle mise en œuvre, tant qu'ils correspondent aux spécifications standard de ces conteneurs.
AFAIK, les conteneurs associatifs sont mis en œuvre comme des arbres binaires (rouge-noir). Plus de détails ... en fonction de la mise en œuvre.
Ces 4 conteneurs sont généralement tous implémentés à l'aide de "nœuds". Un nœud est un objet qui stocke un élément. Dans le cas [Multi] Set, l'élément est juste la valeur; Dans la carte [MULTI] Carte, chaque nœud stocke une clé et sa valeur associée. Un nœud stocke également plusieurs pointeurs à d'autres nœuds. Contrairement à une liste, les nœuds des ensembles et des cartes forment un arbre. Vous l'organiseriez généralement de telle sorte que les branches de la "gauche" d'un certain nœud ont des valeurs inférieures à ce nœud, tandis que les branches sur le "droit" d'un certain nœud ont des valeurs supérieures à ce nœud.
Opérations telles que la recherche d'une clé de carte / une valeur définie sont maintenant assez rapides. Commencez au noeud racine de l'arbre. Si cela correspond, vous avez terminé. Si la racine est plus grande, recherchez dans la branche gauche. Si la racine est plus petite que la valeur que vous recherchez, suivez le pointeur à la bonne branche. Répétez la répétition jusqu'à la recherche d'une valeur ou d'une branche vide. P>
Insertion d'un élément est effectué en créant un nouveau nœud, en créant l'emplacement dans l'arborese où il doit être placé, puis insérez le nœud là en ajustant la pointeurs autour de cela. Enfin, il y a une opération «rééquilibrage» pour empêcher votre arbre de finir par tous les efforts. Idéalement, chaque branche droite et gauche a à peu près la même taille. Rééquilibrage fonctionne en déplaçant certains nœuds de gauche à droite ou inversement. Par exemple. Si vous avez des valeurs {1 2 3} et votre nœud racine serait 1, vous auriez 2 et 3 sur la branche gauche et une branche droite vide: p>
2 / \ 1 3
Donc, tous ces conteneurs sont-ils implémentés en utilisant AVL ARBRES ?
@JOS: "Ce n'est même pas spécifié dans la norme quelle technique doit être utilisée afin que les implémentations puissent différer.".
Toutes les classes de conteneurs associées (carte, multi-cartes, ensemble, multi-ensemble) sont implémentées avec un arbre rouge et noir (arbre R-B). La mise en œuvre de l'arborescence R-B pourrait donc être similaire à celle-ci: -
struct Rb_node {
int value;
struct node *left, *right;
int color;
int size;
};
Votre extrait de code ne montre aucune mise en œuvre, juste la structure de données. La mise en œuvre est l'endroit où tout le travail est fait et où l'utilité des arbres RB provient.
STL est essentiellement un code de modèle et le code source complet est disponible dans les fichiers d'en-tête. Vous pouvez prendre du code spécifique et vérifier la mise en œuvre interne.
Je pense que pour un programmeur junior, il n'est pas si facile de comprendre le code de modèle mis en oeuvre implémenté. Mais je pense que les concepts généraux et les cas d'utilisation pour la plupart des conteneurs sont décrits dans presque tous les livres de C ++.
Pas dans l'amorce C ++ après avoir lu des conteneurs associatifs. Il n'y a aucune idée de la performance et de l'explication de la façon dont cela fonctionne en interne :(