CRBTree-Klasse
Diese Klasse stellt Methoden zum Erstellen und Verwenden einer Rot-Schwarz-Struktur bereit.
Syntax
template <typename K,
typename V,
class KTraits = CElementTraits<K>,
class VTraits = CElementTraits<V>>
class CRBTree
Parameter
K
Der Schlüsselelementtyp.
V
Der Wertelementtyp.
KTraits
Der Code zum Kopieren oder Verschieben von Schlüsselelementen. Weitere Details finden Sie unter CElementTraits Class .
VTraits
Der Code zum Kopieren oder Verschieben von Wertelementen.
Member
Öffentliche Typedefs
Name | Beschreibung |
---|---|
CRBTree::KINARGTYPE | Typ, der verwendet wird, wenn ein Schlüssel als Eingabeargument übergeben wird. |
CRBTree::KOUTARGTYPE | Typ, der verwendet wird, wenn ein Schlüssel als Ausgabeargument zurückgegeben wird. |
CRBTree::VINARGTYPE | Typ, der verwendet wird, wenn ein Wert als Eingabeargument übergeben wird. |
CRBTree::VOUTARGTYPE | Typ, der verwendet wird, wenn ein Wert als Ausgabeargument übergeben wird. |
Öffentliche Klassen
Name | Beschreibung |
---|---|
CRBTree::CPair-Klasse | Eine Klasse, die die Schlüssel- und Wertelemente enthält. |
Öffentliche Konstruktoren
Name | Beschreibung |
---|---|
CRBTree::~CRBTree | Der Destruktor. |
Öffentliche Methoden
Name | Beschreibung |
---|---|
CRBTree::FindFirstKeyAfter | Rufen Sie diese Methode auf, um die Position des Elements zu finden, das den nächsten verfügbaren Schlüssel verwendet. |
CRBTree::GetAt | Rufen Sie diese Methode auf, um das Element an einer bestimmten Position in der Struktur abzurufen. |
CRBTree::GetCount | Rufen Sie diese Methode auf, um die Anzahl der Elemente in der Struktur abzurufen. |
CRBTree::GetHeadPosition | Rufen Sie diese Methode auf, um den Positionswert für das Element am Kopf der Struktur abzurufen. |
CRBTree::GetKeyAt | Rufen Sie diese Methode auf, um den Schlüssel von einer bestimmten Position in der Struktur abzurufen. |
CRBTree::GetNext | Rufen Sie diese Methode auf, um einen Zeiger auf ein im CRBTree Objekt gespeichertes Element abzurufen und die Position zum nächsten Element zu wechseln. |
CRBTree::GetNextAssoc | Rufen Sie diese Methode auf, um den Schlüssel und Wert eines elements abzurufen, das in der Karte gespeichert ist, und die Position zum nächsten Element weiterzuschreiten. |
CRBTree::GetNextKey | Rufen Sie diese Methode auf, um den Schlüssel eines elements abzurufen, das in der Struktur gespeichert ist, und die Position zum nächsten Element weiterzuschreiten. |
CRBTree::GetNextValue | Rufen Sie diese Methode auf, um den Wert eines in der Struktur gespeicherten Elements abzurufen und die Position zum nächsten Element zu wechseln. |
CRBTree::GetPrev | Rufen Sie diese Methode auf, um einen Zeiger auf ein im CRBTree Objekt gespeichertes Element abzurufen, und aktualisieren Sie dann die Position auf das vorherige Element. |
CRBTree::GetTailPosition | Rufen Sie diese Methode auf, um den Positionswert für das Element am Ende der Struktur abzurufen. |
CRBTree::GetValueAt | Rufen Sie diese Methode auf, um den Wert abzurufen, der an einer bestimmten Position im CRBTree Objekt gespeichert ist. |
CRBTree::IsEmpty | Rufen Sie diese Methode auf, um auf ein leeres Strukturobjekt zu testen. |
CRBTree::RemoveAll | Rufen Sie diese Methode auf, um alle Elemente aus dem CRBTree Objekt zu entfernen. |
CRBTree::RemoveAt | Rufen Sie diese Methode auf, um das Element an der angegebenen Position im CRBTree Objekt zu entfernen. |
CRBTree::SetValueAt | Rufen Sie diese Methode auf, um den Wert zu ändern, der an einer bestimmten Position im CRBTree Objekt gespeichert ist. |
Hinweise
Eine rot-schwarze Struktur ist eine binäre Suchstruktur, die ein zusätzliches Informationselement pro Knoten verwendet, um sicherzustellen, dass sie "ausgeglichen" bleibt, d. h., die Baumhöhe wächst nicht unverhältnismäßig groß und wirkt sich auf die Leistung aus.
Diese Vorlagenklasse wurde für die Verwendung durch CRBMap und CRBMultiMap entwickelt. Der Großteil der Methoden, aus denen diese abgeleiteten Klassen bestehen, werden von CRBTree
.
Eine ausführlichere Erläuterung der verschiedenen Sammlungsklassen und deren Features und Leistungsmerkmale finden Sie unter ATL-Sammlungsklassen.
Anforderungen
Kopfzeile: atlcoll.h
CRBTree::CPair-Klasse
Eine Klasse, die die Schlüssel- und Wertelemente enthält.
class CPair : public __POSITION
Hinweise
Diese Klasse wird von den Methoden CRBTree::GetAt, CRBTree::GetNext und CRBTree::GetPrev verwendet, um auf die schlüssel- und Wertelemente zuzugreifen, die in der Struktur gespeichert sind.
Die Mitglieder sind wie folgt:
Datenmememm | Beschreibung |
---|---|
m_key |
Das Datenelement, das das Schlüsselelement speichert. |
m_value |
Das Datenmemm, das das Wertelement speichert. |
CRBTree::~CRBTree
Der Destruktor.
~CRBTree() throw();
Hinweise
Gibt alle zugeordneten Ressourcen frei. Ruft CRBTree::RemoveAll auf, um alle Elemente zu löschen.
CRBTree::FindFirstKeyAfter
Rufen Sie diese Methode auf, um die Position des Elements zu finden, das den nächsten verfügbaren Schlüssel verwendet.
POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();
Parameter
key
Ein Schlüsselwert.
Rückgabewert
Gibt den Positionswert des Elements zurück, das den nächsten verfügbaren Schlüssel verwendet. Wenn keine weiteren Elemente vorhanden sind, wird NULL zurückgegeben.
Hinweise
Diese Methode erleichtert das Durchlaufen der Struktur, ohne zuvor Positionswerte berechnen zu müssen.
CRBTree::GetAt
Rufen Sie diese Methode auf, um das Element an einer bestimmten Position in der Struktur abzurufen.
CPair* GetAt(POSITION pos) throw();
const CPair* GetAt(POSITION pos) const throw();
void GetAt(POSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;
Parameter
pos
Der Positionswert.
key
Die Variable, die den Schlüssel empfängt.
value
Die Variable, die den Wert empfängt.
Rückgabewert
Die ersten beiden Formulare geben einen Zeiger auf ein CPair zurück. Das dritte Formular erhält einen Schlüssel und einen Wert für die angegebene Position.
Hinweise
Der Positionswert kann zuvor mit einem Aufruf einer Methode wie CRBTree::GetHeadPosition oder CRBTree::GetTailPosition bestimmt werden.
In Debugbuilds tritt ein Assertionsfehler auf, wenn pos gleich NULL ist.
CRBTree::GetCount
Rufen Sie diese Methode auf, um die Anzahl der Elemente in der Struktur abzurufen.
size_t GetCount() const throw();
Rückgabewert
Gibt die Anzahl der Elemente zurück (jedes Schlüssel-Wert-Paar ist ein Element), das in der Struktur gespeichert ist.
CRBTree::GetHeadPosition
Rufen Sie diese Methode auf, um den Positionswert für das Element am Kopf der Struktur abzurufen.
POSITION GetHeadPosition() const throw();
Rückgabewert
Gibt den Positionswert für das Element am Kopf der Struktur zurück.
Hinweise
Der zurückgegebene GetHeadPosition
Wert kann mit Methoden wie CRBTree::GetKeyAt oder CRBTree::GetNext verwendet werden, um die Struktur zu durchlaufen und Werte abzurufen.
CRBTree::GetKeyAt
Rufen Sie diese Methode auf, um den Schlüssel von einer bestimmten Position in der Struktur abzurufen.
const K& GetKeyAt(POSITION pos) const throw();
Parameter
pos
Der Positionswert.
Rückgabewert
Gibt den Schlüssel zurück, der an position position in der Struktur gespeichert ist.
Hinweise
Wenn pos kein gültiger Positionswert ist, sind die Ergebnisse unvorhersehbar. In Debugbuilds tritt ein Assertionsfehler auf, wenn pos gleich NULL ist.
CRBTree::GetNext
Rufen Sie diese Methode auf, um einen Zeiger auf ein im CRBTree
Objekt gespeichertes Element abzurufen und die Position zum nächsten Element zu wechseln.
const CPair* GetNext(POSITION& pos) const throw();
CPair* GetNext(POSITION& pos) throw();
Parameter
pos
Der Positionszähler, der von einem vorherigen Aufruf von Methoden wie CRBTree::GetHeadPosition oder CRBTree::FindFirstKeyAfter zurückgegeben wird.
Rückgabewert
Gibt einen Zeiger auf den nächsten CPair-Wert in der Struktur zurück.
Hinweise
Der Pos-Positionszähler wird nach jedem Anruf aktualisiert. Wenn das abgerufene Element der letzte in der Struktur ist, wird pos auf NULL festgelegt.
CRBTree::GetNextAssoc
Rufen Sie diese Methode auf, um den Schlüssel und Wert eines elements abzurufen, das in der Karte gespeichert ist, und die Position zum nächsten Element weiterzuschreiten.
void GetNextAssoc(
POSITION& pos,
KOUTARGTYPE key,
VOUTARGTYPE value) const;
Parameter
pos
Der Positionszähler, der von einem vorherigen Aufruf von Methoden wie CRBTree::GetHeadPosition oder CRBTree::FindFirstKeyAfter zurückgegeben wird.
key
Vorlagenparameter, der den Typ des Schlüssels der Struktur angibt.
value
Vorlagenparameter, der den Typ des Strukturwerts angibt.
Hinweise
Der Pos-Positionszähler wird nach jedem Anruf aktualisiert. Wenn das abgerufene Element der letzte in der Struktur ist, wird pos auf NULL festgelegt.
CRBTree::GetNextKey
Rufen Sie diese Methode auf, um den Schlüssel eines elements abzurufen, das in der Struktur gespeichert ist, und die Position zum nächsten Element weiterzuschreiten.
const K& GetNextKey(POSITION& pos) const throw();
Parameter
pos
Der Positionszähler, der von einem vorherigen Aufruf von Methoden wie CRBTree::GetHeadPosition oder CRBTree::FindFirstKeyAfter zurückgegeben wird.
Rückgabewert
Gibt einen Verweis auf den nächsten Schlüssel in der Struktur zurück.
Hinweise
Aktualisiert den aktuellen Positionszähler pos. Wenn keine weiteren Einträge in der Struktur vorhanden sind, wird der Positionszähler auf NULL festgelegt.
CRBTree::GetNextValue
Rufen Sie diese Methode auf, um den Wert eines in der Struktur gespeicherten Elements abzurufen und die Position zum nächsten Element zu wechseln.
const V& GetNextValue(POSITION& pos) const throw();
V& GetNextValue(POSITION& pos) throw();
Parameter
pos
Der Positionszähler, der von einem vorherigen Aufruf von Methoden wie CRBTree::GetHeadPosition oder CRBTree::FindFirstKeyAfter zurückgegeben wird.
Rückgabewert
Gibt einen Verweis auf den nächsten Wert in der Struktur zurück.
Hinweise
Aktualisiert den aktuellen Positionszähler pos. Wenn keine weiteren Einträge in der Struktur vorhanden sind, wird der Positionszähler auf NULL festgelegt.
CRBTree::GetPrev
Rufen Sie diese Methode auf, um einen Zeiger auf ein im CRBTree
Objekt gespeichertes Element abzurufen, und aktualisieren Sie dann die Position auf das vorherige Element.
const CPair* GetPrev(POSITION& pos) const throw();
CPair* GetPrev(POSITION& pos) throw();
Parameter
pos
Der Positionszähler, der von einem vorherigen Aufruf von Methoden wie CRBTree::GetHeadPosition oder CRBTree::FindFirstKeyAfter zurückgegeben wird.
Rückgabewert
Gibt einen Zeiger auf den vorherigen CPair-Wert zurück, der in der Struktur gespeichert ist.
Hinweise
Aktualisiert den aktuellen Positionszähler pos. Wenn keine weiteren Einträge in der Struktur vorhanden sind, wird der Positionszähler auf NULL festgelegt.
CRBTree::GetTailPosition
Rufen Sie diese Methode auf, um den Positionswert für das Element am Ende der Struktur abzurufen.
POSITION GetTailPosition() const throw();
Rückgabewert
Gibt den Positionswert für das Element am Ende der Struktur zurück.
Hinweise
Der von GetTailPosition
ihnen zurückgegebene Wert kann mit Methoden wie CRBTree::GetKeyAt oder CRBTree::GetPrev verwendet werden, um die Struktur zu durchlaufen und Werte abzurufen.
CRBTree::GetValueAt
Rufen Sie diese Methode auf, um den Wert abzurufen, der an einer bestimmten Position im CRBTree
Objekt gespeichert ist.
const V& GetValueAt(POSITION pos) const throw();
V& GetValueAt(POSITION pos) throw();
Parameter
pos
Der Positionszähler, der von einem vorherigen Aufruf von Methoden wie CRBTree::GetHeadPosition oder CRBTree::FindFirstKeyAfter zurückgegeben wird.
Rückgabewert
Gibt einen Verweis auf den Wert zurück, der an der angegebenen Position im CRBTree
Objekt gespeichert ist.
CRBTree::IsEmpty
Rufen Sie diese Methode auf, um auf ein leeres Strukturobjekt zu testen.
bool IsEmpty() const throw();
Rückgabewert
Gibt TRUE zurück, wenn die Struktur leer ist, andernfalls FALSE.
CRBTree::KINARGTYPE
Typ, der verwendet wird, wenn ein Schlüssel als Eingabeargument übergeben wird.
typedef KTraits::INARGTYPE KINARGTYPE;
CRBTree::KOUTARGTYPE
Typ, der verwendet wird, wenn ein Schlüssel als Ausgabeargument zurückgegeben wird.
typedef KTraits::OUTARGTYPE KOUTARGTYPE;
CRBTree::RemoveAll
Rufen Sie diese Methode auf, um alle Elemente aus dem CRBTree
Objekt zu entfernen.
void RemoveAll() throw();
Hinweise
Löscht das CRBTree
Objekt, wobei der Zum Speichern der Elemente verwendete Speicher freigegeben wird.
CRBTree::RemoveAt
Rufen Sie diese Methode auf, um das Element an der angegebenen Position im CRBTree
Objekt zu entfernen.
void RemoveAt(POSITION pos) throw();
Parameter
pos
Der Positionszähler, der von einem vorherigen Aufruf von Methoden wie CRBTree::GetHeadPosition oder CRBTree::FindFirstKeyAfter zurückgegeben wird.
Hinweise
Entfernt das Schlüssel-Wert-Paar, das an der angegebenen Position gespeichert ist. Der zum Speichern des Elements verwendete Speicher wird freigegeben. Die position, auf die pos verweist, wird ungültig, und während die POSITION aller anderen Elemente in der Struktur gültig bleibt, behalten sie nicht unbedingt dieselbe Reihenfolge bei.
CRBTree::SetValueAt
Rufen Sie diese Methode auf, um den Wert zu ändern, der an einer bestimmten Position im CRBTree
Objekt gespeichert ist.
void SetValueAt(POSITION pos, VINARGTYPE value);
Parameter
pos
Der Positionszähler, der von einem vorherigen Aufruf von Methoden wie CRBTree::GetHeadPosition oder CRBTree::FindFirstKeyAfter zurückgegeben wird.
value
Der Wert, der dem CRBTree
Objekt hinzugefügt werden soll.
Hinweise
Ändert das Wertelement, das an der angegebenen Position im CRBTree
Objekt gespeichert ist.
CRBTree::VINARGTYPE
Typ, der verwendet wird, wenn ein Wert als Eingabeargument übergeben wird.
typedef VTraits::INARGTYPE VINARGTYPE;
CRBTree::VOUTARGTYPE
Typ, der verwendet wird, wenn ein Wert als Ausgabeargument übergeben wird.
typedef VTraits::OUTARGTYPE VOUTARGTYPE;