À l'aide du TSL Internes de mise en Œuvre de la Rouge-Noir Arbre

Je comprends que mon STL (qui vient avec g++ 4.x.x) utilise des arbres rouge-noir pour mettre en œuvre des conteneurs tels que la carte. Est-il possible d'utiliser la STL interne rouge-noir arbre directement. Si oui, comment? Si non, pourquoi - pourquoi ne STL exposez pas le rouge-noir arbre?

Étonnamment, je ne trouve pas de réponse à l'aide de google.

Edit: je recherche à l'aide de la rouge-noir l'arbre comme une solution à l'extra allocateur de l'appel du constructeur en matière d'insertion. Voir cette question. Mon STL utilise des arbres rouge-noir pour le plan de mise en œuvre.

"Je recherche l'aide de la rouge-noir l'arbre comme une solution à l'extra allocateur de l'appel du constructeur en matière d'insertion." Une bonne solution serait d'utiliser une mise en œuvre de conteneurs standard qui n'ont pas cette propriété. C++11, stateful allocateurs, de sorte que toute la bibliothèque standard qui prend en charge ce C++11 fonctionnalité permettra d'avoir plus d'un comportement raisonnable (bien que cela soit encore construire différents allocateur cas, il suffira de le faire à partir de l'original de l'allocateur de l'objet).
Il ne serait pas vous aider ici, parce que c'est l'arbre sous-jacente de la mise en œuvre que le constructeur appelle de toute façon. Essayer un nouveau compilateur gcc 4.1 serait une option (question précédente personnaliser l'allocateur de mémoire pour STL carte)

OriginalL'auteur Prasoon Tiwari | 2012-07-08

  1. 8

    En fait, la réponse est très simple, et indépendant de votre version de gcc. Vous pouvez télécharger le tsl code source de sgi site web, et de voir la mise en œuvre et l'utiliser pour vous-même.

    Par exemple, dans la version 3.2, vous pouvez voir les rouge-noir arbre de la mise en œuvre dans le stl_tree.h de fichier, et un exemple de son utilisation dans stl_set.h.

    Noter que depuis les classes de la stl sont des classes template, les implémentations sont en fait à l'intérieur de l'en-tête des fichiers.

    OriginalL'auteur Guy Adini

  2. 3

    Vous n'êtes même pas donné une garantie que la structure de données utilisée sera être rouge-noir de l'arbre (par exemple, il a été mis en œuvre au moins une fois comme un arbre AVL, et quelque chose comme le B-, B*, ou B+ tree serait probablement très bien).

    En tant que tel, la seule façon d'obtenir à l'intérieur de rechercher une mise en œuvre spécifique, et de faire usage des choses qu'il n'a pas (au moins essayer) exposer publiquement.

    Quant au pourquoi: je pense surtout parce que c'est une tentative d'abstraction, de ne pas exposer tous les détails de mise en œuvre.

    OriginalL'auteur Jerry Coffin

  3. 2

    La plupart des TSL, les implémentations de set et map sont rouge noir des arbres, je crois, mais rien n'empêche quelqu'un de leur mise en œuvre en utilisant une autre structure de données - si je me souviens bien, le C++ standard ne nécessite pas de RB arbre de la mise en œuvre.

    La STL ne pas exposer comme qui contreviendrait à la programmation orientée objet principes.. d'exposer la structure de données sous-jacente pourrait conduire à certains un comportement indésirable si quelqu'un d'autre utilise votre bibliothèque. C'est, précisément pour set et map, vous ne devraient être autorisés à avoir accès à des méthodes qui seraient conformes à la set et map structures de données.. exposant la représentation sous-jacente pourrait peut-être permettre à un utilisateur d'avoir des doublons à l'intérieur de set, ce qui est mauvais.

    Cela étant dit, il n'existe aucun moyen (à ma connaissance) d'utiliser directement le sous-jacent rouge noir de l'arbre.. ça dépend beaucoup de comment vous voulez utiliser. La mise en œuvre de votre propre rouge-noir arbre serait le plus susceptible d'être votre meilleur pari, ou consultez notre 3ème partie les bibliothèques (peut-être le coup de pouce?)

    OriginalL'auteur adelbertc