Partager via

CRBTree, classe

  • Article

Cette classe fournit des méthodes pour créer et utiliser une arborescence Rouge-Noir.

Syntaxe

template <typename K,
          typename V,
          class KTraits = CElementTraits<K>,
          class VTraits = CElementTraits<V>>
class CRBTree

Paramètres

K
Type d’élément clé.

V
Type d’élément value.

KTraits
Code utilisé pour copier ou déplacer des éléments clés. Pour plus d’informations, consultez la classe CElementTraits.

VTraits
Code utilisé pour copier ou déplacer des éléments de valeur.

Membres

Typedefs publics

Nom Description
CRBTree ::KINARGTYPE Type utilisé lorsqu’une clé est passée en tant qu’argument d’entrée.
CRBTree ::KOUTARGTYPE Type utilisé lorsqu’une clé est retournée en tant qu’argument de sortie.
CRBTree ::VINARGTYPE Type utilisé lorsqu’une valeur est passée en tant qu’argument d’entrée.
CRBTree ::VOUTARGTYPE Type utilisé lorsqu’une valeur est passée en tant qu’argument de sortie.

Classes publiques

Nom Description
CRBTree ::CPair, classe Classe contenant les éléments clé et valeur.

Constructeurs publics

Nom Description
CRBTree ::~CRBTree Destructeur.

Méthodes publiques

Nom Description
CRBTree ::FindFirstKeyAfter Appelez cette méthode pour rechercher la position de l’élément qui utilise la clé disponible suivante.
CRBTree ::GetAt Appelez cette méthode pour obtenir l’élément à une position donnée dans l’arborescence.
CRBTree ::GetCount Appelez cette méthode pour obtenir le nombre d’éléments dans l’arborescence.
CRBTree ::GetHeadPosition Appelez cette méthode pour obtenir la valeur de position de l’élément à la tête de l’arborescence.
CRBTree ::GetKeyAt Appelez cette méthode pour obtenir la clé à partir d’une position donnée dans l’arborescence.
CRBTree ::GetNext Appelez cette méthode pour obtenir un pointeur vers un élément stocké dans l’objet CRBTree et avancer la position vers l’élément suivant.
CRBTree ::GetNextAssoc Appelez cette méthode pour obtenir la clé et la valeur d’un élément stocké dans la carte et avancer la position vers l’élément suivant.
CRBTree ::GetNextKey Appelez cette méthode pour obtenir la clé d’un élément stocké dans l’arborescence et avancer la position vers l’élément suivant.
CRBTree ::GetNextValue Appelez cette méthode pour obtenir la valeur d’un élément stocké dans l’arborescence et avancer la position vers l’élément suivant.
CRBTree ::GetPrev Appelez cette méthode pour obtenir un pointeur vers un élément stocké dans l’objet CRBTree , puis mettez à jour la position vers l’élément précédent.
CRBTree ::GetTailPosition Appelez cette méthode pour obtenir la valeur de position de l’élément à la fin de l’arborescence.
CRBTree ::GetValueAt Appelez cette méthode pour récupérer la valeur stockée à une position donnée dans l’objet CRBTree .
CRBTree ::IsEmpty Appelez cette méthode pour tester un objet d’arborescence vide.
CRBTree ::RemoveAll Appelez cette méthode pour supprimer tous les éléments de l’objet CRBTree .
CRBTree ::RemoveAt Appelez cette méthode pour supprimer l’élément à la position donnée dans l’objet CRBTree .
CRBTree ::SetValueAt Appelez cette méthode pour modifier la valeur stockée à une position donnée dans l’objet CRBTree .

Notes

Un arbre Rouge-Noir est un arbre de recherche binaire qui utilise un bit d’informations supplémentaire par nœud pour s’assurer qu’il reste « équilibré », c’est-à-dire que la hauteur de l’arbre ne croît pas de manière disproportionnée et affecte les performances.

Cette classe de modèle est conçue pour être utilisée par CRBMap et CRBMultiMap. La majeure partie des méthodes qui composent ces classes dérivées sont fournies par CRBTree.

Pour une discussion plus complète sur les différentes classes de collection et leurs caractéristiques de performances, consultez les classes de collection ATL.

Spécifications

En-tête : atlcoll.h

CRBTree ::CPair, classe

Classe contenant les éléments clé et valeur.

class CPair : public __POSITION

Notes

Cette classe est utilisée par les méthodes CRBTree ::GetAt, CRBTree ::GetNext et CRBTree ::GetPrev pour accéder aux éléments de clé et de valeur stockés dans l’arborescence.

Les membres sont les suivants :

Membre de données Description
m_key Membre de données stockant l’élément clé.
m_value Membre de données stockant l’élément valeur.

CRBTree ::~CRBTree

Destructeur.

~CRBTree() throw();

Notes

Libère toutes les ressources allouées. Appelle CRBTree ::RemoveAll pour supprimer tous les éléments.

CRBTree ::FindFirstKeyAfter

Appelez cette méthode pour rechercher la position de l’élément qui utilise la clé disponible suivante.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

Paramètres

key
Valeur de clé.

Valeur de retour

Retourne la valeur de position de l’élément qui utilise la clé disponible suivante. S’il n’y a plus d’éléments, NULL est retourné.

Notes

Cette méthode facilite la traversée de l’arborescence sans avoir à calculer les valeurs de position au préalable.

CRBTree ::GetAt

Appelez cette méthode pour obtenir l’élément à une position donnée dans l’arborescence.

CPair* GetAt(POSITION pos) throw();
const CPair* GetAt(POSITION pos) const throw();
void GetAt(POSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;

Paramètres

pos
Valeur de la position.

key
Variable qui reçoit la clé.

value
Variable qui reçoit la valeur.

Valeur de retour

Les deux premiers formulaires retournent un pointeur vers un CPair. Le troisième formulaire obtient une clé et une valeur pour la position donnée.

Notes

La valeur de position peut être déterminée précédemment avec un appel à une méthode telle que CRBTree ::GetHeadPosition ou CRBTree ::GetTailPosition.

Dans les builds de débogage, une défaillance d’assertion se produit si pos est égal à NULL.

CRBTree ::GetCount

Appelez cette méthode pour obtenir le nombre d’éléments dans l’arborescence.

size_t GetCount() const throw();

Valeur de retour

Retourne le nombre d’éléments (chaque paire clé/valeur est un élément) stocké dans l’arborescence.

CRBTree ::GetHeadPosition

Appelez cette méthode pour obtenir la valeur de position de l’élément à la tête de l’arborescence.

POSITION GetHeadPosition() const throw();

Valeur de retour

Retourne la valeur de position de l’élément à la tête de l’arborescence.

Notes

La valeur retournée par GetHeadPosition peut être utilisée avec des méthodes telles que CRBTree ::GetKeyAt ou CRBTree ::GetNext pour parcourir l’arborescence et récupérer les valeurs.

CRBTree ::GetKeyAt

Appelez cette méthode pour obtenir la clé à partir d’une position donnée dans l’arborescence.

const K& GetKeyAt(POSITION pos) const throw();

Paramètres

pos
Valeur de la position.

Valeur de retour

Retourne la clé stockée à la position dans l’arborescence.

Notes

Si la pos n’est pas une valeur de position valide, les résultats sont imprévisibles. Dans les builds de débogage, une défaillance d’assertion se produit si pos est égal à NULL.

CRBTree ::GetNext

Appelez cette méthode pour obtenir un pointeur vers un élément stocké dans l’objet CRBTree et avancer la position vers l’élément suivant.

const CPair* GetNext(POSITION& pos) const throw();
CPair* GetNext(POSITION& pos) throw();

Paramètres

pos
Compteur de position, retourné par un appel précédent à des méthodes telles que CRBTree ::GetHeadPosition ou CRBTree ::FindFirstKeyAfter.

Valeur de retour

Retourne un pointeur vers la valeur CPair suivante dans l’arborescence.

Notes

Le compteur de position de pos est mis à jour après chaque appel. Si l’élément récupéré est le dernier de l’arborescence, pos a la valeur NULL.

CRBTree ::GetNextAssoc

Appelez cette méthode pour obtenir la clé et la valeur d’un élément stocké dans la carte et avancer la position vers l’élément suivant.

void GetNextAssoc(
    POSITION& pos,
    KOUTARGTYPE key,
    VOUTARGTYPE value) const;

Paramètres

pos
Compteur de position, retourné par un appel précédent à des méthodes telles que CRBTree ::GetHeadPosition ou CRBTree ::FindFirstKeyAfter.

key
Paramètre de modèle spécifiant le type de la clé de l’arborescence.

value
Paramètre de modèle spécifiant le type de la valeur de l’arborescence.

Notes

Le compteur de position de pos est mis à jour après chaque appel. Si l’élément récupéré est le dernier de l’arborescence, pos a la valeur NULL.

CRBTree ::GetNextKey

Appelez cette méthode pour obtenir la clé d’un élément stocké dans l’arborescence et avancer la position vers l’élément suivant.

const K& GetNextKey(POSITION& pos) const throw();

Paramètres

pos
Compteur de position, retourné par un appel précédent à des méthodes telles que CRBTree ::GetHeadPosition ou CRBTree ::FindFirstKeyAfter.

Valeur de retour

Retourne une référence à la clé suivante dans l’arborescence.

Notes

Met à jour le compteur de position actuel, pos. S’il n’y a plus d’entrées dans l’arborescence, le compteur de position est défini sur NULL.

CRBTree ::GetNextValue

Appelez cette méthode pour obtenir la valeur d’un élément stocké dans l’arborescence et avancer la position vers l’élément suivant.

const V& GetNextValue(POSITION& pos) const throw();
V& GetNextValue(POSITION& pos) throw();

Paramètres

pos
Compteur de position, retourné par un appel précédent à des méthodes telles que CRBTree ::GetHeadPosition ou CRBTree ::FindFirstKeyAfter.

Valeur de retour

Retourne une référence à la valeur suivante dans l’arborescence.

Notes

Met à jour le compteur de position actuel, pos. S’il n’y a plus d’entrées dans l’arborescence, le compteur de position est défini sur NULL.

CRBTree ::GetPrev

Appelez cette méthode pour obtenir un pointeur vers un élément stocké dans l’objet CRBTree , puis mettez à jour la position vers l’élément précédent.

const CPair* GetPrev(POSITION& pos) const throw();
CPair* GetPrev(POSITION& pos) throw();

Paramètres

pos
Compteur de position, retourné par un appel précédent à des méthodes telles que CRBTree ::GetHeadPosition ou CRBTree ::FindFirstKeyAfter.

Valeur de retour

Retourne un pointeur vers la valeur CPair précédente stockée dans l’arborescence.

Notes

Met à jour le compteur de position actuel, pos. S’il n’y a plus d’entrées dans l’arborescence, le compteur de position est défini sur NULL.

CRBTree ::GetTailPosition

Appelez cette méthode pour obtenir la valeur de position de l’élément à la fin de l’arborescence.

POSITION GetTailPosition() const throw();

Valeur de retour

Retourne la valeur de position de l’élément à la fin de l’arborescence.

Notes

La valeur retournée par GetTailPosition peut être utilisée avec des méthodes telles que CRBTree ::GetKeyAt ou CRBTree ::GetPrev pour parcourir l’arborescence et récupérer les valeurs.

CRBTree ::GetValueAt

Appelez cette méthode pour récupérer la valeur stockée à une position donnée dans l’objet CRBTree .

const V& GetValueAt(POSITION pos) const throw();
V& GetValueAt(POSITION pos) throw();

Paramètres

pos
Compteur de position, retourné par un appel précédent à des méthodes telles que CRBTree ::GetHeadPosition ou CRBTree ::FindFirstKeyAfter.

Valeur de retour

Retourne une référence à la valeur stockée à la position donnée dans l’objet CRBTree .

CRBTree ::IsEmpty

Appelez cette méthode pour tester un objet d’arborescence vide.

bool IsEmpty() const throw();

Valeur de retour

Retourne TRUE si l’arborescence est vide, FALSE sinon.

CRBTree ::KINARGTYPE

Type utilisé lorsqu’une clé est passée en tant qu’argument d’entrée.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree ::KOUTARGTYPE

Type utilisé lorsqu’une clé est retournée en tant qu’argument de sortie.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree ::RemoveAll

Appelez cette méthode pour supprimer tous les éléments de l’objet CRBTree .

void RemoveAll() throw();

Notes

Efface l’objet CRBTree , libérant la mémoire utilisée pour stocker les éléments.

CRBTree ::RemoveAt

Appelez cette méthode pour supprimer l’élément à la position donnée dans l’objet CRBTree .

void RemoveAt(POSITION pos) throw();

Paramètres

pos
Compteur de position, retourné par un appel précédent à des méthodes telles que CRBTree ::GetHeadPosition ou CRBTree ::FindFirstKeyAfter.

Notes

Supprime la paire clé/valeur stockée à la position spécifiée. La mémoire utilisée pour stocker l’élément est libérée. La position référencée par pos devient non valide et alors que la position d’autres éléments de l’arborescence reste valide, elles ne conservent pas nécessairement le même ordre.

CRBTree ::SetValueAt

Appelez cette méthode pour modifier la valeur stockée à une position donnée dans l’objet CRBTree .

void SetValueAt(POSITION pos, VINARGTYPE value);

Paramètres

pos
Compteur de position, retourné par un appel précédent à des méthodes telles que CRBTree ::GetHeadPosition ou CRBTree ::FindFirstKeyAfter.

value
Valeur à ajouter à l’objet CRBTree .

Notes

Modifie l’élément valeur stocké à la position donnée dans l’objet CRBTree .

CRBTree ::VINARGTYPE

Type utilisé lorsqu’une valeur est passée en tant qu’argument d’entrée.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree ::VOUTARGTYPE

Type utilisé lorsqu’une valeur est passée en tant qu’argument de sortie.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Voir aussi

Vue d’ensemble de la classe