Je veux apprendre des codes de l'arbre noir rouge dans STL. Et j'ai trouvé une fonction nommée _rb_tree_incrènement dans les bits de fichier / stl_tree.h
Il écrit: mais je ne trouve pas la définition de cette fonction. Tout le monde peut aider? Merci beaucoup.
3 Réponses :
Cette définition dépend de quelle bibliothèque standard vous avez. Les fournisseurs de compilation différents offrent différentes implémentations de la bibliothèque standard avec leurs compilateurs. Il semble que vous ayez trouvé une fonction Nontemplate. Cela devrait être défini dans certains CPP et il sera expédié avec le compilateur dans le fichier LIB. Vous ne pouvez donc pas accéder directement au code, car il ne sera pas expédié avec votre compilateur - ce n'est tout simplement pas nécessaire.
Si votre compilateur est un compilateur propriétaire, par exemple De Microsoft ou Borland, c'est tout ce que vous obtiendrez. Si vous avez un GCC Toutefois, vous avez eu la chance: GCC est open source et vous pouvez trouver les sources de la mise en œuvre de la GCC de la bibliothèque standard en ligne.
OP utilise évidemment l'expédition de mise en œuvre STDLIBC ++ avec GCC.
Génial Merci, Arne, votre réponse a frappé le point ("Il semble que vous ayez trouvé une fonction Nontemplate. Cela devrait être défini dans certains CPP et il sera expédié avec le compilateur dans le fichier LIB"). :)
Ce sera dans le code source de la bibliothèque, que vous n'avez probablement pas.
On dirait que vous regardez les en-têtes de la bibliothèque GNU, de sorte que ici serait un bon endroit pour commencer à chercher la source.
Merci, Mike. Votre lien est très utile. :)
Comme @Mike Seymour a déclaré, j'ai trouvé la définition sur le chemin source de la bibliothèque, plus précisément à l'intérieur GCC-4.8.1 / LIBSTDC ++ - V3 / SRC / C ++ 98 / TRET.CC :
Merci beaucoup, Massa. Je pense que je dois télécharger le code source de GCC. :)
Pour des points bonus, comment la fonction d'incrément est-elle dans l'algorithme rouge-noir?
@RagerDL Il semble que "Incrément" est C ++ Speak pour "Itérateur :: opérateur ++", qui se traduirait par "Sibling" sur EN.Wikipedia.org/wiki/red%e2%80%93black_tree Notez que" Décrément "est l'opération inverse (point de mon frère antérieur) qui n'est pas défini sur le La page Wikipedia pointée.
En regardant le deuxième si Énoncé: comment __ x -> _ m_right est déjà égal à __ y (c'est-à-dire son grand-parent)?
GitHub Mirror: GITUB.COM/GCC-MIRROR/GCC/BLOB/MASTER/LIBSTDC%2B%2B-V3/SRC/...
@ user2023370 J'ai été aussi compliqué avec cette condition. Je pense que c'est une sorte de lastophole ruse. Comme vous pouvez le constater dans le moment où la déclaration ci-dessus, x peut "brouiller" sur une racine, mais __ y = __Y -> _ m_parent . Comment se fait-il que vous puissiez vérifier __ x == __Y -> _ m_right si x est une racine? Cela signifie qu'un parent d'une racine n'est pas nullptr ? Il me semble qu'un parent d'une racine est son enfant gauche (peut-être, je ne suis pas sûr)
@Aryatarifullin Il y a quelques invariants que vous négligez;
@ user2023370 Si vous regardez la source de la fonction adverse, _rb_tree_decrement (), vous trouvez le code suivant là-bas: si (... __x -> _ m_parent -> _ m_parent == __x) . Alors oui, vers la racine, le grand-parent d'un élément peut être cet élément lui-même. Ceci est probablement de maintenir des pointeurs spéciaux sur le premier et dernier élément de l'arborescence, de sorte que commence () , fin et std :: prev (fin) < / Code> sont toutes efficaces et n'ont pas besoin de passer à travers l'arborescence pour trouver le premier ou le dernier élément, respectivement.
@ user2023370 En regardant _rb_tree_insert_and_rebalance () , on peut voir, que __ header._m_parent fait référence au nœud racine, tandis que __ cashore._m_left et < Code> __ header._m_right Reportez-vous au nœud le plus à gauche (= commencements () ) et le nœud le plus à droite (= std :: prev (fin de code>) ) respectivement. L'en-tête __ () Le nœud lui-même représente l'extrémité () itérateur. La condition spéciale, que vous avez vue, est probablement là, de sorte que opérateur ++ et opérateur - ne dépasse pas le début / la fin.