CRBTree Classe

Esta aula fornece métodos para criar e utilizar uma árvore de Red-Black.

Sintaxe

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

Parâmetros

K
O tipo de elemento-chave.

V
O tipo de elemento valor.

KTraits
O código usado para copiar ou mover elementos-chave. Consulte a Classe CElementTraits para mais detalhes.

VTraits
O código usado para copiar ou mover elementos de valor.

Membros

Definições de Tipos Públicas

Aulas Públicas

Construtores Públicos

Métodos Públicos

Observações

Uma árvore Red-Black é uma árvore binária de pesquisa que utiliza um bit extra de informação por nó para garantir que se mantém "equilibrada", ou seja, que a altura da árvore não cresce desproporcionalmente e não afeta o desempenho.

Esta classe modelo foi concebida para ser usada pelo CRBMap e pelo CRBMultiMap. A maioria dos métodos que compõem estas classes derivadas é fornecida por CRBTree.

Para uma discussão mais completa das várias classes de coleção e das suas características e características de desempenho, consulte Classes de Coleção ATL.

Requerimentos

Cabeçalho: atlcoll.h

CRBTree::CPair Class

Uma classe que contém os elementos chave e valor.

class CPair : public __POSITION

Observações

Esta classe é usada pelos métodos CRBTree::GetAt, CRBTree::GetNext e CRBTree::GetPrev para aceder aos elementos-chave e valor armazenados na estrutura em árvore.

Os membros são os seguintes:

CRBTree::~CRBTree

O destruidor.

~CRBTree() throw();

Observações

Liberta quaisquer recursos alocados. Chama CRBTree::RemoveAll para eliminar todos os elementos.

CRBTree::EncontrarPrimeiroChaveDepois

Chame este método para encontrar a posição do elemento que usa a próxima chave disponível.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

Parâmetros

chave
Um valor chave.

Valor de retorno

Devolve o valor da posição do elemento que usa a próxima chave disponível. Se não houver mais elementos, NULL é devolvido.

Observações

Este método facilita a percorrência da árvore sem ter de calcular previamente os valores de posição.

CRBTree::GetAt

Chame este método para obter o elemento numa posição dada na árvore.

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

Parâmetros

Ponto de venda
O valor da posição.

chave
A variável que recebe a chave.

value
A variável que recebe o valor.

Valor de retorno

As duas primeiras formas devolvem um apontador para um CPair. A terceira forma obtém uma chave e um valor para a posição dada.

Observações

O valor da posição pode ser previamente determinado com uma chamada para um método como CRBTree::GetHeadPosition ou CRBTree::GetTailPosition.

Em builds de depuração, ocorrerá uma falha de asserção se pos for igual a NULL.

CRBTree::GetCount

Chame este método para obter o número de elementos na árvore.

size_t GetCount() const throw();

Valor de retorno

Devolve o número de elementos (cada par chave/valor é um elemento) armazenados na árvore.

CRBTree::GetHeadPosition

Chame este método para obter o valor de posição do elemento na cabeça da árvore.

POSITION GetHeadPosition() const throw();

Valor de retorno

Devolve o valor da posição do elemento na cabeça da árvore.

Observações

O valor devolvido por GetHeadPosition pode ser usado com métodos como CRBTree::GetKeyAt ou CRBTree::GetNext para percorrer a árvore e recuperar valores.

CRBTree::GetKeyAt

Chame este método para obter a chave de uma posição dada na árvore.

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

Parâmetros

Ponto de venda
O valor da posição.

Valor de retorno

Devolve a chave armazenada na posição pos na árvore.

Observações

Se o pos não for um valor de posição válido, os resultados são imprevisíveis. Em builds de depuração, ocorrerá uma falha de asserção se pos for igual a NULL.

CRBTree::GetNext

Chame este método para obter um ponteiro para um elemento armazenado no CRBTree objeto e avance a posição para o elemento seguinte.

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

Parâmetros

Ponto de venda
O contador de posição, devolvido por uma chamada anterior a métodos como CRBTree::GetHeadPosition ou CRBTree::FindFirstKeyAfter.

Valor de retorno

Devolve um ponteiro para o próximo valor CPair na árvore.

Observações

O contador de posições pos é atualizado após cada chamada. Se o elemento recuperado for o último na árvore, pos é definido como NULL.

CRBTree::GetNextAssoc

Chame este método para obter a chave e o valor de um elemento armazenados no mapa e avançar a posição para o elemento seguinte.

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

Parâmetros

Ponto de venda
O contador de posição, devolvido por uma chamada anterior a métodos como CRBTree::GetHeadPosition ou CRBTree::FindFirstKeyAfter.

chave
Parâmetro template que especifica o tipo da chave da árvore.

value
Parâmetro modelo que especifica o tipo de valor da árvore.

Observações

O contador de posições pos é atualizado após cada chamada. Se o elemento recuperado for o último na árvore, pos é definido como NULL.

CRBTree::GetNextKey

Chama este método para obter a chave de um elemento armazenada na árvore e avançar a posição para o elemento seguinte.

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

Parâmetros

Ponto de venda
O contador de posição, devolvido por uma chamada anterior a métodos como CRBTree::GetHeadPosition ou CRBTree::FindFirstKeyAfter.

Valor de retorno

Devolve uma referência à próxima chave na árvore.

Observações

Atualiza o contador de posição atual, pos. Se não houver mais entradas na árvore, o contador de posição é definido como NULL.

CRBTree::GetNextValue

Chame este método para obter o valor de um elemento armazenado na árvore e avançar a posição para o elemento seguinte.

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

Parâmetros

Ponto de venda
O contador de posição, devolvido por uma chamada anterior a métodos como CRBTree::GetHeadPosition ou CRBTree::FindFirstKeyAfter.

Valor de retorno

Devolve uma referência ao valor seguinte na árvore.

Observações

Atualiza o contador de posição atual, pos. Se não houver mais entradas na árvore, o contador de posição é definido como NULL.

CRBTree::GetPrev

Chame este método para obter um ponteiro para um elemento armazenado no CRBTree objeto, e depois atualize a posição para o elemento anterior.

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

Parâmetros

Ponto de venda
O contador de posição, devolvido por uma chamada anterior a métodos como CRBTree::GetHeadPosition ou CRBTree::FindFirstKeyAfter.

Valor de retorno

Devolve um ponteiro para o valor CPair anterior armazenado na árvore.

Observações

Atualiza o contador de posição atual, pos. Se não houver mais entradas na árvore, o contador de posição é definido como NULL.

CRBTree::ObtendoPosiçãoDeCauda

Chame este método para obter o valor de posição do elemento na cauda da árvore.

POSITION GetTailPosition() const throw();

Valor de retorno

Devolve o valor da posição do elemento na cauda da árvore.

Observações

O valor devolvido por GetTailPosition pode ser usado com métodos como CRBTree::GetKeyAt ou CRBTree::GetPrev para percorrer a árvore e recuperar valores.

CRBTree::GetValueAt

Chame este método para recuperar o valor armazenado numa posição dada no CRBTree objeto.

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

Parâmetros

Ponto de venda
O contador de posição, devolvido por uma chamada anterior a métodos como CRBTree::GetHeadPosition ou CRBTree::FindFirstKeyAfter.

Valor de retorno

Devolve uma referência ao valor armazenado na posição dada no CRBTree objeto.

CRBTree::IsEmpty

Chame este método para testar um objeto de árvore vazio.

bool IsEmpty() const throw();

Valor de retorno

Retorna TRUE se a árvore estiver vazia, FALSE caso contrário.

CRBTree::KINARGTYPE

Tipo usado quando uma chave é passada como argumento de entrada.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KOUTARGTYPE

Tipo usado quando uma chave é devolvida como argumento de saída.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

Chame este método para remover todos os elementos do CRBTree objeto.

void RemoveAll() throw();

Observações

Limpa o CRBTree objeto, libertando a memória usada para armazenar os elementos.

CRBTree::RemoveAt

Chame este método para remover o elemento na posição dada no CRBTree objeto.

void RemoveAt(POSITION pos) throw();

Parâmetros

Ponto de venda
O contador de posição, devolvido por uma chamada anterior a métodos como CRBTree::GetHeadPosition ou CRBTree::FindFirstKeyAfter.

Observações

Remove o par chave/valor armazenado na posição especificada. A memória usada para armazenar o elemento é libertada. A POSIÇÃO referenciada por pos torna-se inválida e, embora a POSIÇÃO de quaisquer outros elementos na árvore permaneça válida, não mantêm necessariamente a mesma ordem.

CRBTree::SetValueAt

Chame este método para alterar o valor armazenado numa dada posição no CRBTree objeto.

void SetValueAt(POSITION pos, VINARGTYPE value);

Parâmetros

Ponto de venda
O contador de posição, devolvido por uma chamada anterior a métodos como CRBTree::GetHeadPosition ou CRBTree::FindFirstKeyAfter.

value
O valor a acrescentar ao CRBTree objeto.

Observações

Altera o elemento de valor armazenado na posição dada no CRBTree objeto.

CRBTree::VINARGTYPE

Tipo usado quando um valor é passado como argumento de entrada.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

Tipo usado quando um valor é passado como argumento de saída.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Consulte também

Visão geral da classe