CRBTree Class

This class provides methods for creating and utilizing a Red-Black tree.

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

K
The key element type.

V
The value element type.

KTraits
The code used to copy or move key elements. See CElementTraits Class for more details.

VTraits
The code used to copy or move value elements.

A Red-Black tree is a binary search tree that uses an extra bit of information per node to ensure that it remains "balanced," that is, the tree height doesn't grow disproportionately large and affect performance.

This template class is designed to be used by CRBMap and CRBMultiMap. The bulk of the methods that make up these derived classes are provided by CRBTree.

For a more complete discussion of the various collection classes and their features and performance characteristics, see ATL Collection Classes.

Header: atlcoll.h

A class containing the key and value elements.

class CPair : public __POSITION

This class is used by the methods CRBTree::GetAt, CRBTree::GetNext, and CRBTree::GetPrev to access the key and value elements stored in the tree structure.

The members are as follows:

The destructor.

~CRBTree() throw();

Frees any allocated resources. Calls CRBTree::RemoveAll to delete all elements.

Call this method to find the position of the element that uses the next available key.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

key
A key value.

Returns the position value of the element that uses the next available key. If there are no more elements, NULL is returned.

This method makes it easy to traverse the tree without having to calculate position values beforehand.

Call this method to get the element at a given position in the tree.

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

pos
The position value.

key
The variable that receives the key.

value
The variable that receives the value.

The first two forms return a pointer to a CPair. The third form obtains a key and a value for the given position.

The position value can be previously determined with a call to a method such as CRBTree::GetHeadPosition or CRBTree::GetTailPosition.

In debug builds, an assertion failure will occur if pos is equal to NULL.

Call this method to get the number of elements in the tree.

size_t GetCount() const throw();

Returns the number of elements (each key/value pair is one element) stored in the tree.

Call this method to get the position value for the element at the head of the tree.

POSITION GetHeadPosition() const throw();

Returns the position value for the element at the head of the tree.

The value returned by GetHeadPosition can be used with methods such as CRBTree::GetKeyAt or CRBTree::GetNext to traverse the tree and retrieve values.

Call this method to get the key from a given position in the tree.

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

pos
The position value.

Returns the key stored at position pos in the tree.

If pos is not a valid position value, results are unpredictable. In debug builds, an assertion failure will occur if pos is equal to NULL.

Call this method to obtain a pointer to an element stored in the CRBTree object, and advance the position to the next element.

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

pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.

Returns a pointer to the next CPair value in the tree.

The pos position counter is updated after each call. If the retrieved element is the last in the tree, pos is set to NULL.

Call this method to get the key and value of an element stored in the map and advance the position to the next element.

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

pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.

key
Template parameter specifying the type of the tree's key.

value
Template parameter specifying the type of the tree's value.

The pos position counter is updated after each call. If the retrieved element is the last in the tree, pos is set to NULL.

Call this method to get the key of an element stored in the tree and advance the position to the next element.

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

pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.

Returns a reference to the next key in the tree.

Updates the current position counter, pos. If there are no more entries in the tree, the position counter is set to NULL.

Call this method to get the value of an element stored in the tree and advance the position to the next element.

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

pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.

Returns a reference to the next value in the tree.

Updates the current position counter, pos. If there are no more entries in the tree, the position counter is set to NULL.

Call this method to obtain a pointer to an element stored in the CRBTree object, and then update the position to the previous element.

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

pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.

Returns a pointer to the previous CPair value stored in the tree.

Updates the current position counter, pos. If there are no more entries in the tree, the position counter is set to NULL.

Call this method to get the position value for the element at the tail of the tree.

POSITION GetTailPosition() const throw();

Returns the position value for the element at the tail of the tree.

The value returned by GetTailPosition can be used with methods such as CRBTree::GetKeyAt or CRBTree::GetPrev to traverse the tree and retrieve values.

Call this method to retrieve the value stored at a given position in the CRBTree object.

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

pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.

Returns a reference to the value stored at the given position in the CRBTree object.

Call this method to test for an empty tree object.

bool IsEmpty() const throw();

Returns TRUE if the tree is empty, FALSE otherwise.

Type used when a key is passed as an input argument.

typedef KTraits::INARGTYPE KINARGTYPE;

Type used when a key is returned as an output argument.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

Call this method to remove all elements from the CRBTree object.

void RemoveAll() throw();

Clears out the CRBTree object, freeing the memory used to store the elements.

Call this method to remove the element at the given position in the CRBTree object.

void RemoveAt(POSITION pos) throw();

pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.

Removes the key/value pair stored at the specified position. The memory used to store the element is freed. The POSITION referenced by pos becomes invalid, and while the POSITION of any other elements in the tree remains valid, they do not necessarily retain the same order.

Call this method to change the value stored at a given position in the CRBTree object.

void SetValueAt(POSITION pos, VINARGTYPE value);

pos
The position counter, returned by a previous call to methods such as CRBTree::GetHeadPosition or CRBTree::FindFirstKeyAfter.

value
The value to add to the CRBTree object.

Changes the value element stored at the given position in the CRBTree object.

Type used when a value is passed as an input argument.

typedef VTraits::INARGTYPE VINARGTYPE;

Type used when a value is passed as an output argument.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Class Overview