Condividi tramite

Classe CRBTree

  • Articolo

Questa classe fornisce metodi per la creazione e l'utilizzo di un albero Red-Black.

Sintassi

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

Parametri

K
Tipo di elemento chiave.

V
Tipo di elemento value.

KTraits
Codice utilizzato per copiare o spostare elementi chiave. Per altri dettagli, vedere Classe CElementTraits.

VTraits
Codice utilizzato per copiare o spostare elementi valore.

Membri

Typedef pubblici

Nome Descrizione
CRBTree::KINARGTYPE Tipo utilizzato quando una chiave viene passata come argomento di input.
CRBTree::KUTARGTYPE Tipo utilizzato quando viene restituita una chiave come argomento di output.
CRBTree::VINARGTYPE Tipo utilizzato quando un valore viene passato come argomento di input.
CRBTree::VOUTARGTYPE Tipo utilizzato quando un valore viene passato come argomento di output.

Classi pubbliche

Nome Descrizione
Classe CRBTree::CPair Classe contenente gli elementi chiave e valore.

Costruttori pubblici

Nome Descrizione
CRBTree::~CRBTree Distruttore.

Metodi pubblici

Nome Descrizione
CRBTree::FindFirstKeyAfter Chiamare questo metodo per trovare la posizione dell'elemento che usa la chiave disponibile successiva.
CRBTree::GetAt Chiamare questo metodo per ottenere l'elemento in una determinata posizione nell'albero.
CRBTree::GetCount Chiamare questo metodo per ottenere il numero di elementi nell'albero.
CRBTree::GetHeadPosition Chiamare questo metodo per ottenere il valore di posizione per l'elemento all'inizio dell'albero.
CRBTree::GetKeyAt Chiamare questo metodo per ottenere la chiave da una determinata posizione nell'albero.
CRBTree::GetNext Chiamare questo metodo per ottenere un puntatore a un elemento archiviato nell'oggetto CRBTree e spostare la posizione sull'elemento successivo.
CRBTree::GetNextAssoc Chiamare questo metodo per ottenere la chiave e il valore di un elemento archiviato nella mappa e far avanzare la posizione all'elemento successivo.
CRBTree::GetNextKey Chiamare questo metodo per ottenere la chiave di un elemento archiviato nell'albero e passare alla posizione successiva.
CRBTree::GetNextValue Chiamare questo metodo per ottenere il valore di un elemento archiviato nell'albero e passare alla posizione successiva.
CRBTree::GetPrev Chiamare questo metodo per ottenere un puntatore a un elemento archiviato nell'oggetto CRBTree e quindi aggiornare la posizione all'elemento precedente.
CRBTree::GetTailPosition Chiamare questo metodo per ottenere il valore di posizione per l'elemento nella parte finale dell'albero.
CRBTree::GetValueAt Chiamare questo metodo per recuperare il valore archiviato in una determinata posizione nell'oggetto CRBTree .
CRBTree::IsEmpty Chiamare questo metodo per verificare la ricerca di un oggetto albero vuoto.
CRBTree::RemoveAll Chiamare questo metodo per rimuovere tutti gli elementi dall'oggetto CRBTree .
CRBTree::RemoveAt Chiamare questo metodo per rimuovere l'elemento in corrispondenza della posizione specificata nell'oggetto CRBTree .
CRBTree::SetValueAt Chiamare questo metodo per modificare il valore archiviato in una determinata posizione nell'oggetto CRBTree .

Osservazioni:

Un albero rosso-nero è un albero di ricerca binario che usa un bit aggiuntivo di informazioni per ogni nodo per garantire che rimanga "bilanciato", ovvero l'altezza dell'albero non aumenta in modo sproporzionato e influisce sulle prestazioni.

Questa classe modello è progettata per essere usata da CRBMap e CRBMultiMap. La maggior parte dei metodi che costituiscono queste classi derivate vengono fornite da CRBTree.

Per una descrizione più completa delle varie classi di raccolte e delle relative caratteristiche e caratteristiche delle prestazioni, vedere Classi di raccolta ATL.

Requisiti

Intestazione: atlcoll.h

Classe CRBTree::CPair

Classe contenente gli elementi chiave e valore.

class CPair : public __POSITION

Osservazioni:

Questa classe viene usata dai metodi CRBTree::GetAt, CRBTree::GetNext e CRBTree::GetPrev per accedere agli elementi chiave e valore archiviati nella struttura ad albero.

I membri sono i seguenti:

Membro dati Descrizione
m_key Membro dati che archivia l'elemento chiave.
m_value Membro dati che archivia l'elemento value.

CRBTree::~CRBTree

Distruttore.

~CRBTree() throw();

Osservazioni:

Libera tutte le risorse allocate. Chiama CRBTree::RemoveAll per eliminare tutti gli elementi.

CRBTree::FindFirstKeyAfter

Chiamare questo metodo per trovare la posizione dell'elemento che usa la chiave disponibile successiva.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

Parametri

key
Valore della chiave.

Valore restituito

Restituisce il valore di posizione dell'elemento che utilizza la chiave disponibile successiva. Se non sono presenti altri elementi, viene restituito NULL.

Osservazioni:

Questo metodo semplifica l'attraversamento dell'albero senza dover calcolare in anticipo i valori di posizione.

CRBTree::GetAt

Chiamare questo metodo per ottenere l'elemento in una determinata posizione nell'albero.

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

Parametri

pos
Valore di posizione.

key
Variabile che riceve la chiave.

value
Variabile che riceve il valore.

Valore restituito

Le prime due forme restituiscono un puntatore a un oggetto CPair. Il terzo modulo ottiene una chiave e un valore per la posizione specificata.

Osservazioni:

Il valore della posizione può essere determinato in precedenza con una chiamata a un metodo, ad esempio CRBTree::GetHeadPosition o CRBTree::GetTailPosition.

Nelle compilazioni di debug si verificherà un errore di asserzione se pos è uguale a NULL.

CRBTree::GetCount

Chiamare questo metodo per ottenere il numero di elementi nell'albero.

size_t GetCount() const throw();

Valore restituito

Restituisce il numero di elementi (ogni coppia chiave/valore è un elemento) archiviato nell'albero.

CRBTree::GetHeadPosition

Chiamare questo metodo per ottenere il valore di posizione per l'elemento all'inizio dell'albero.

POSITION GetHeadPosition() const throw();

Valore restituito

Restituisce il valore di posizione per l'elemento nella parte superiore dell'albero.

Osservazioni:

Il valore restituito da GetHeadPosition può essere usato con metodi come CRBTree::GetKeyAt o CRBTree::GetNext per attraversare l'albero e recuperare i valori.

CRBTree::GetKeyAt

Chiamare questo metodo per ottenere la chiave da una determinata posizione nell'albero.

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

Parametri

pos
Valore di posizione.

Valore restituito

Restituisce la chiave archiviata in corrispondenza della posizione pos nell'albero.

Osservazioni:

Se pos non è un valore di posizione valido, i risultati sono imprevedibili. Nelle compilazioni di debug si verificherà un errore di asserzione se pos è uguale a NULL.

CRBTree::GetNext

Chiamare questo metodo per ottenere un puntatore a un elemento archiviato nell'oggetto CRBTree e spostare la posizione sull'elemento successivo.

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

Parametri

pos
Contatore di posizione, restituito da una chiamata precedente a metodi come CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valore restituito

Restituisce un puntatore al valore CPair successivo nell'albero.

Osservazioni:

Il contatore della posizione pos viene aggiornato dopo ogni chiamata. Se l'elemento recuperato è l'ultimo nell'albero, pos è impostato su NULL.

CRBTree::GetNextAssoc

Chiamare questo metodo per ottenere la chiave e il valore di un elemento archiviato nella mappa e far avanzare la posizione all'elemento successivo.

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

Parametri

pos
Contatore di posizione, restituito da una chiamata precedente a metodi come CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

key
Parametro del modello che specifica il tipo della chiave dell'albero.

value
Parametro modello che specifica il tipo del valore dell'albero.

Osservazioni:

Il contatore della posizione pos viene aggiornato dopo ogni chiamata. Se l'elemento recuperato è l'ultimo nell'albero, pos è impostato su NULL.

CRBTree::GetNextKey

Chiamare questo metodo per ottenere la chiave di un elemento archiviato nell'albero e passare alla posizione successiva.

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

Parametri

pos
Contatore di posizione, restituito da una chiamata precedente a metodi come CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valore restituito

Restituisce un riferimento alla chiave successiva nell'albero.

Osservazioni:

Aggiornamenti il contatore di posizione corrente, pos. Se nell'albero non sono presenti altre voci, il contatore della posizione viene impostato su NULL.

CRBTree::GetNextValue

Chiamare questo metodo per ottenere il valore di un elemento archiviato nell'albero e passare alla posizione successiva.

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

Parametri

pos
Contatore di posizione, restituito da una chiamata precedente a metodi come CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valore restituito

Restituisce un riferimento al valore successivo nell'albero.

Osservazioni:

Aggiornamenti il contatore di posizione corrente, pos. Se nell'albero non sono presenti altre voci, il contatore della posizione viene impostato su NULL.

CRBTree::GetPrev

Chiamare questo metodo per ottenere un puntatore a un elemento archiviato nell'oggetto CRBTree e quindi aggiornare la posizione all'elemento precedente.

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

Parametri

pos
Contatore di posizione, restituito da una chiamata precedente a metodi come CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valore restituito

Restituisce un puntatore al valore CPair precedente archiviato nell'albero.

Osservazioni:

Aggiornamenti il contatore di posizione corrente, pos. Se nell'albero non sono presenti altre voci, il contatore della posizione viene impostato su NULL.

CRBTree::GetTailPosition

Chiamare questo metodo per ottenere il valore di posizione per l'elemento nella parte finale dell'albero.

POSITION GetTailPosition() const throw();

Valore restituito

Restituisce il valore di posizione per l'elemento nella parte finale dell'albero.

Osservazioni:

Il valore restituito da GetTailPosition può essere usato con metodi come CRBTree::GetKeyAt o CRBTree::GetPrev per attraversare l'albero e recuperare i valori.

CRBTree::GetValueAt

Chiamare questo metodo per recuperare il valore archiviato in una determinata posizione nell'oggetto CRBTree .

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

Parametri

pos
Contatore di posizione, restituito da una chiamata precedente a metodi come CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valore restituito

Restituisce un riferimento al valore archiviato nella posizione specificata nell'oggetto CRBTree .

CRBTree::IsEmpty

Chiamare questo metodo per verificare la ricerca di un oggetto albero vuoto.

bool IsEmpty() const throw();

Valore restituito

Restituisce TRUE se l'albero è vuoto, FAL edizione Standard in caso contrario.

CRBTree::KINARGTYPE

Tipo utilizzato quando una chiave viene passata come argomento di input.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KUTARGTYPE

Tipo utilizzato quando viene restituita una chiave come argomento di output.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

Chiamare questo metodo per rimuovere tutti gli elementi dall'oggetto CRBTree .

void RemoveAll() throw();

Osservazioni:

Cancella l'oggetto CRBTree liberando la memoria utilizzata per archiviare gli elementi.

CRBTree::RemoveAt

Chiamare questo metodo per rimuovere l'elemento in corrispondenza della posizione specificata nell'oggetto CRBTree .

void RemoveAt(POSITION pos) throw();

Parametri

pos
Contatore di posizione, restituito da una chiamata precedente a metodi come CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Osservazioni:

Rimuove la coppia chiave/valore archiviata nella posizione specificata. La memoria utilizzata per archiviare l'elemento viene liberata. Position a cui fa riferimento pos diventa non valido e, mentre l'elemento POSITION di qualsiasi altro elemento dell'albero rimane valido, non mantiene necessariamente lo stesso ordine.

CRBTree::SetValueAt

Chiamare questo metodo per modificare il valore archiviato in una determinata posizione nell'oggetto CRBTree .

void SetValueAt(POSITION pos, VINARGTYPE value);

Parametri

pos
Contatore di posizione, restituito da una chiamata precedente a metodi come CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

value
Valore da aggiungere all'oggetto CRBTree .

Osservazioni:

Modifica l'elemento valore archiviato nella posizione specificata nell'oggetto CRBTree .

CRBTree::VINARGTYPE

Tipo utilizzato quando un valore viene passato come argomento di input.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

Tipo utilizzato quando un valore viene passato come argomento di output.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Vedi anche

Cenni preliminari sulla classe