Clase CRBTree
Esta clase proporciona métodos para crear y usar un árbol Rojo-Negro.
Sintaxis
template <typename K,
typename V,
class KTraits = CElementTraits<K>,
class VTraits = CElementTraits<V>>
class CRBTree
Parámetros
K
Tipo de elemento clave.
V
Tipo de elemento de valor.
KTraits
Código usado para copiar o mover elementos de clave. Consulte CElementTraits (clase) para más información.
VTraits
Código usado para copiar o mover elementos de valor.
Miembros
Definiciones de tipos públicas
Nombre | Descripción |
---|---|
CRBTree::KINARGTYPE | Tipo usado cuando se pasa una clave como argumento de entrada. |
CRBTree::KOUTARGTYPE | Tipo utilizado cuando se devuelve una clave como argumento de salida. |
CRBTree::VINARGTYPE | Tipo que se usa cuando se pasa un valor como argumento de entrada. |
CRBTree::VOUTARGTYPE | Tipo que se usa cuando se pasa un valor como argumento de salida. |
Clases públicas
Nombre | Descripción |
---|---|
CRBTree::CPair Class | Clase que contiene los elementos de clave y valor. |
Constructores públicos
Nombre | Descripción |
---|---|
CRBTree::~CRBTree | El destructor . |
Métodos públicos
Nombre | Descripción |
---|---|
CRBTree::FindFirstKeyAfter | Llame a este método para buscar la posición del elemento que usa la siguiente clave disponible. |
CRBTree::GetAt | Llame a este método para obtener el elemento en una posición determinada del árbol. |
CRBTree::GetCount | Llame a este método para obtener el número de elementos del árbol. |
CRBTree::GetHeadPosition | Llame a este método para obtener el valor de posición del elemento en la cabeza del árbol. |
CRBTree::GetKeyAt | Llame a este método para obtener la clave de una posición determinada en el árbol. |
CRBTree::GetNext | Llame a este método para obtener un puntero a un elemento almacenado en el objeto CRBTree y avanzar la posición al siguiente elemento. |
CRBTree::GetNextAssoc | Llame a este método para obtener la clave y el valor de un elemento almacenado en la asignación y avanzar la posición al siguiente elemento. |
CRBTree::GetNextKey | Llame a este método para obtener la clave de un elemento almacenado en el árbol y avanzar la posición al siguiente elemento. |
CRBTree::GetNextValue | Llame a este método para obtener el valor de un elemento almacenado en el árbol y avanzar la posición al siguiente elemento. |
CRBTree::GetPrev | Llame a este método para obtener un puntero a un elemento almacenado en el objeto CRBTree y después actualice la posición al elemento anterior. |
CRBTree::GetTailPosition | Llame a este método para obtener el valor de posición del elemento en la cola del árbol. |
CRBTree::GetValueAt | Llame a este método para recuperar el valor almacenado en una posición determinada del objeto CRBTree . |
CRBTree::IsEmpty | Llame a este método para probar un objeto de árbol vacío. |
CRBTree::RemoveAll | Llame a este método para quitar todos los elementos del objeto CRBTree . |
CRBTree::RemoveAt | Llame a este método para quitar el elemento en la posición especificada del objeto CRBTree . |
CRBTree::SetValueAt | Llame a este método para cambiar el valor almacenado en una posición determinada del objeto CRBTree . |
Comentarios
Un árbol Rojo-Negro es un árbol de búsqueda binario que usa un bit adicional de información por nodo para asegurarse de que sigue siendo "equilibrado", es decir, de que el alto del árbol no crece de forma desproporcionada y afecta al rendimiento.
Esta clase de plantilla está diseñada para usarse en CRBMap y CRBMultiMap. La mayor parte de los métodos que componen estas clases derivadas se proporcionan mediante CRBTree
.
Para obtener una explicación más completa de las distintas clases de colección y sus características y características de rendimiento, consulte Clases de colección de ATL.
Requisitos
Encabezado: atlcoll.h
Clase CRBTree::CPair
Clase que contiene los elementos de clave y valor.
class CPair : public __POSITION
Comentarios
Los métodos CRBTree::GetAt, CRBTree::GetNext y CRBTree::GetPrev usan esta clase para tener acceso a los elementos de clave y valor almacenados en la estructura de árbol.
Los miembros son los siguientes:
Miembro de datos | Descripción |
---|---|
m_key |
Miembro de datos que almacena el elemento clave. |
m_value |
Miembro de datos que almacena el elemento value. |
CRBTree::~CRBTree
El destructor .
~CRBTree() throw();
Comentarios
Libera los recursos asignados. Llama a CRBTree::RemoveAll para eliminar todos los elementos.
CRBTree::FindFirstKeyAfter
Llame a este método para buscar la posición del elemento que usa la siguiente clave disponible.
POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();
Parámetros
key
Valor de clave.
Valor devuelto
Devuelve el valor de posición del elemento que usa la siguiente clave disponible. Si no hay más elementos, se devuelve NULL.
Comentarios
Este método facilita el recorrido a través del árbol sin tener que calcular los valores de posición de antemano.
CRBTree::GetAt
Llame a este método para obtener el elemento en una posición determinada del árbol.
CPair* GetAt(POSITION pos) throw();
const CPair* GetAt(POSITION pos) const throw();
void GetAt(POSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;
Parámetros
pos
Valor de la posición.
key
Variable que recibe la clave.
value
Variable que recibe el valor.
Valor devuelto
Los dos primeros formularios devuelven un puntero a CPair. El tercer formulario obtiene una clave y un valor para la posición especificada.
Comentarios
El valor de posición se puede determinar previamente con una llamada a un método como CRBTree::GetHeadPosition o CRBTree::GetTailPosition.
En las compilaciones de depuración, se producirá un error de aserción si pos es igual a NULL.
CRBTree::GetCount
Llame a este método para obtener el número de elementos del árbol.
size_t GetCount() const throw();
Valor devuelto
Devuelve el número de elementos (cada par clave-valor es un elemento) almacenado en el árbol.
CRBTree::GetHeadPosition
Llame a este método para obtener el valor de posición del elemento en la cabeza del árbol.
POSITION GetHeadPosition() const throw();
Valor devuelto
Devuelve el valor de posición del elemento en la cabeza del árbol.
Comentarios
El valor devuelto por GetHeadPosition
se puede usar con métodos como CRBTree::GetKeyAt o CRBTree::GetNext para recorrer el árbol y recuperar valores.
CRBTree::GetKeyAt
Llame a este método para obtener la clave de una posición determinada en el árbol.
const K& GetKeyAt(POSITION pos) const throw();
Parámetros
pos
Valor de la posición.
Valor devuelto
Devuelve la clave almacenada en posición pos en el árbol.
Comentarios
Si pos no es un valor de posición válido, los resultados son impredecibles. En las compilaciones de depuración, se producirá un error de aserción si pos es igual a NULL.
CRBTree::GetNext
Llame a este método para obtener un puntero a un elemento almacenado en el objeto CRBTree
y avanzar la posición al siguiente elemento.
const CPair* GetNext(POSITION& pos) const throw();
CPair* GetNext(POSITION& pos) throw();
Parámetros
pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.
Valor devuelto
Devuelve un puntero al siguiente valor CPair del árbol.
Comentarios
El contador de posición pos se actualiza después de cada llamada. Si el elemento recuperado es el último del árbol, pos se establece en NULL.
CRBTree::GetNextAssoc
Llame a este método para obtener la clave y el valor de un elemento almacenado en la asignación y avanzar la posición al siguiente elemento.
void GetNextAssoc(
POSITION& pos,
KOUTARGTYPE key,
VOUTARGTYPE value) const;
Parámetros
pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.
key
Parámetro de plantilla que especifica el tipo de clave del árbol.
value
Parámetro de plantilla que especifica el tipo de valor del árbol.
Comentarios
El contador de posición pos se actualiza después de cada llamada. Si el elemento recuperado es el último del árbol, pos se establece en NULL.
CRBTree::GetNextKey
Llame a este método para obtener la clave de un elemento almacenado en el árbol y avanzar la posición al siguiente elemento.
const K& GetNextKey(POSITION& pos) const throw();
Parámetros
pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.
Valor devuelto
Devuelve una referencia a la siguiente clave del árbol.
Comentarios
Actualiza el contador de posición actual, pos. Si no hay más entradas en el árbol, el contador de posición se establece en NULL.
CRBTree::GetNextValue
Llame a este método para obtener el valor de un elemento almacenado en el árbol y avanzar la posición al siguiente elemento.
const V& GetNextValue(POSITION& pos) const throw();
V& GetNextValue(POSITION& pos) throw();
Parámetros
pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.
Valor devuelto
Devuelve una referencia al siguiente valor del árbol.
Comentarios
Actualiza el contador de posición actual, pos. Si no hay más entradas en el árbol, el contador de posición se establece en NULL.
CRBTree::GetPrev
Llame a este método para obtener un puntero a un elemento almacenado en el objeto CRBTree
y después actualice la posición al elemento anterior.
const CPair* GetPrev(POSITION& pos) const throw();
CPair* GetPrev(POSITION& pos) throw();
Parámetros
pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.
Valor devuelto
Devuelve un puntero al valor CPair anterior almacenado en el árbol.
Comentarios
Actualiza el contador de posición actual, pos. Si no hay más entradas en el árbol, el contador de posición se establece en NULL.
CRBTree::GetTailPosition
Llame a este método para obtener el valor de posición del elemento en la cola del árbol.
POSITION GetTailPosition() const throw();
Valor devuelto
Devuelve el valor de posición del elemento situado en la cola del árbol.
Comentarios
El valor devuelto por GetTailPosition
se puede usar con métodos como CRBTree::GetKeyAt o CRBTree::GetPrev para recorrer el árbol y recuperar valores.
CRBTree::GetValueAt
Llame a este método para recuperar el valor almacenado en una posición determinada del objeto CRBTree
.
const V& GetValueAt(POSITION pos) const throw();
V& GetValueAt(POSITION pos) throw();
Parámetros
pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.
Valor devuelto
Devuelve una referencia al valor almacenado en la posición especificada del objeto CRBTree
.
CRBTree::IsEmpty
Llame a este método para probar un objeto de árbol vacío.
bool IsEmpty() const throw();
Valor devuelto
Devuelve TRUE si el árbol está vacío, FALSE de lo contrario.
CRBTree::KINARGTYPE
Tipo usado cuando se pasa una clave como argumento de entrada.
typedef KTraits::INARGTYPE KINARGTYPE;
CRBTree::KOUTARGTYPE
Tipo utilizado cuando se devuelve una clave como argumento de salida.
typedef KTraits::OUTARGTYPE KOUTARGTYPE;
CRBTree::RemoveAll
Llame a este método para quitar todos los elementos del objeto CRBTree
.
void RemoveAll() throw();
Comentarios
Borra el objeto CRBTree
, liberando la memoria usada para almacenar los elementos.
CRBTree::RemoveAt
Llame a este método para quitar el elemento en la posición especificada del objeto CRBTree
.
void RemoveAt(POSITION pos) throw();
Parámetros
pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.
Comentarios
Quita el par clave-valor almacenado en la posición especificada. La memoria usada para almacenar el elemento se libera. La posición a la que hace referencia pos no es válida y, mientras que el valor POSITION de cualquier otro elemento del árbol sigue siendo válido, no conservan necesariamente el mismo orden.
CRBTree::SetValueAt
Llame a este método para cambiar el valor almacenado en una posición determinada del objeto CRBTree
.
void SetValueAt(POSITION pos, VINARGTYPE value);
Parámetros
pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.
value
Valor del objeto que se va a agregar a CRBTree
.
Comentarios
Cambia el elemento de valor almacenado en la posición especificada del objeto CRBTree
.
CRBTree::VINARGTYPE
Tipo que se usa cuando se pasa un valor como argumento de entrada.
typedef VTraits::INARGTYPE VINARGTYPE;
CRBTree::VOUTARGTYPE
Tipo que se usa cuando se pasa un valor como argumento de salida.
typedef VTraits::OUTARGTYPE VOUTARGTYPE;