Compartilhar via

Classe CRBTree

  • Artigo

Essa classe fornece métodos para criar e utilizar uma árvore 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 key.

V
O tipo de elemento valor.

KTraits
O código usado para copiar ou mover elementos de chave. Confira a classe CElementTraits para obter mais detalhes.

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

Membros

Typedefs públicos

Nome Descrição
CRBTree::KINARGTYPE O tipo usado quando uma chave é passada como um argumento de entrada.
CRBTree::KOUTARGTYPE O tipo usado quando uma chave é retornada como um argumento de saída.
CRBTree::VINARGTYPE O tipo usado quando um valor é passado como um argumento de entrada.
CRBTree::VOUTARGTYPE O tipo usado quando um valor é passado como um argumento de saída.

Classes públicas

Nome Descrição
CRBTree::CPair Class Uma classe que contém os elementos key e value.

Construtores públicos

Nome Descrição
CRBTree::~CRBTree O destruidor.

Métodos públicos

Nome Descrição
CRBTree::FindFirstKeyAfter Chame esse método para localizar a posição do elemento que usa a próxima chave disponível.
CRBTree::GetAt Chame esse método para obter o elemento em uma determinada posição na árvore.
CRBTree::GetCount Chame esse método para obter o número de elementos na árvore.
CRBTree::GetHeadPosition Chame esse método para obter o valor de posição do elemento no início da árvore.
CRBTree::GetKeyAt Chame esse método para obter a chave de uma determinada posição na árvore.
CRBTree::GetNext Chame esse método para obter um ponteiro para um elemento armazenado no objeto CRBTree e avance a posição para o próximo elemento.
CRBTree::GetNextAssoc Chame esse método para obter a chave e o valor de um elemento armazenado no mapa e avance a posição para o próximo elemento.
CRBTree::GetNextKey Chame esse método para obter a chave de um elemento armazenado na árvore e avance a posição para o próximo elemento.
CRBTree::GetNextValue Chame esse método para obter o valor de um elemento armazenado na árvore e avance a posição para o próximo elemento.
CRBTree::GetPrev Chame esse método para obter um ponteiro para um elemento armazenado no objeto CRBTree e atualize a posição para o elemento anterior.
CRBTree::GetTailPosition Chame esse método para obter o valor de posição do elemento no fim da árvore.
CRBTree::GetValueAt Chame esse método para recuperar o valor armazenado em uma determinada posição no objeto CRBTree.
CRBTree::IsEmpty Chame esse método para testar um objeto de árvore vazio.
CRBTree::RemoveAll Chame esse método para remover todos os elementos do objeto CRBTree.
CRBTree::RemoveAt Chame esse método para remover o elemento na posição determinada no objeto CRBTree.
CRBTree::SetValueAt Chame esse método para alterar o valor armazenado em uma determinada posição no objeto CRBTree.

Comentários

Uma árvore Red-Black é uma árvore de pesquisa binária que usa um bit extra de informações por nó para garantir que ela permaneça "equilibrada", ou seja, a altura da árvore não aumenta desproporcionalmente e afeta o desempenho.

Essa classe de modelo foi criada para ser usada por CRBMap e CRBMultiMap. A maior parte dos métodos que compõem essas classes derivadas é fornecida por CRBTree.

Para obter uma discussão mais completa sobre as várias classes de coleção e seus recursos e características de desempenho, confira Classes de coleção da ATL.

Requisitos

Cabeçalho: atlcoll.h

Classe CRBTree::CPair

Uma classe que contém os elementos key e value.

class CPair : public __POSITION

Comentários

Essa classe é usada pelos métodos CRBTree::GetAt, CRBTree::GetNext e CRBTree::GetPrev para acessar os elementos key e value armazenados na estrutura da árvore.

Os membros são os seguintes:

Membro de dados Descrição
m_key O membro de dados que armazena o elemento key.
m_value O membro de dados que armazena o elemento value.

CRBTree::~CRBTree

O destruidor.

~CRBTree() throw();

Comentários

Libera todos os recursos alocados. Chama CRBTree::RemoveAll para excluir todos os elementos.

CRBTree::FindFirstKeyAfter

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

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

Parâmetros

chave
Um valor de chave.

Valor de retorno

Retorna o valor da posição do elemento que usa a próxima chave disponível. Se não houver mais elementos, NULL será retornado.

Comentários

Esse método facilita a passagem da árvore sem precisar calcular valores de posição com antecedência.

CRBTree::GetAt

Chame esse método para obter o elemento em uma determinada posição 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

pos
O valor da posição.

chave
A variável que recebe a chave.

value
A variável que recebe o valor.

Valor de retorno

Os dois primeiros formatos retornam um ponteiro para um CPair. O terceiro formato obtém uma chave e um valor para a posição determinada.

Comentários

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

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

CRBTree::GetCount

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

size_t GetCount() const throw();

Valor de retorno

Retorna o número de elementos (cada par key/value é um elemento) armazenado na árvore.

CRBTree::GetHeadPosition

Chame esse método para obter o valor de posição do elemento no início da árvore.

POSITION GetHeadPosition() const throw();

Valor de retorno

Retorna o valor da posição do elemento no início da árvore.

Comentários

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

CRBTree::GetKeyAt

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

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

Parâmetros

pos
O valor da posição.

Valor de retorno

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

Comentários

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

CRBTree::GetNext

Chame esse método para obter um ponteiro para um elemento armazenado no objeto CRBTree e avance a posição para o próximo elemento.

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

Parâmetros

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

Valor de retorno

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

Comentários

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

CRBTree::GetNextAssoc

Chame esse método para obter a chave e o valor de um elemento armazenado no mapa e avance a posição para o próximo elemento.

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

Parâmetros

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

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

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

Comentários

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

CRBTree::GetNextKey

Chame esse método para obter a chave de um elemento armazenado na árvore e avance a posição para o próximo elemento.

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

Parâmetros

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

Valor de retorno

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

Comentários

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

CRBTree::GetNextValue

Chame esse método para obter o valor de um elemento armazenado na árvore e avance a posição para o próximo elemento.

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

Parâmetros

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

Valor de retorno

Retorna uma referência ao próximo valor na árvore.

Comentários

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

CRBTree::GetPrev

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

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

Parâmetros

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

Valor de retorno

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

Comentários

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

CRBTree::GetTailPosition

Chame esse método para obter o valor de posição do elemento no fim da árvore.

POSITION GetTailPosition() const throw();

Valor de retorno

Retorna o valor da posição do elemento no fim da árvore.

Comentários

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

CRBTree::GetValueAt

Chame esse método para recuperar o valor armazenado em uma determinada posição no objeto CRBTree.

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

Parâmetros

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

Valor de retorno

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

CRBTree::IsEmpty

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

bool IsEmpty() const throw();

Valor de retorno

Retornará TRUE se a árvore estiver vazia. Caso contrário, FALSE.

CRBTree::KINARGTYPE

O tipo usado quando uma chave é passada como um argumento de entrada.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KOUTARGTYPE

O tipo usado quando uma chave é retornada como um argumento de saída.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

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

void RemoveAll() throw();

Comentários

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

CRBTree::RemoveAt

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

void RemoveAt(POSITION pos) throw();

Parâmetros

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

Comentários

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

CRBTree::SetValueAt

Chame esse método para alterar o valor armazenado em uma determinada posição no objeto CRBTree.

void SetValueAt(POSITION pos, VINARGTYPE value);

Parâmetros

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

value
O valor a ser adicionado ao objeto CRBTree.

Comentários

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

CRBTree::VINARGTYPE

O tipo usado quando um valor é passado como um argumento de entrada.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

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

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Confira também

Visão geral da aula