Teilen über

CRBTree-Klasse

  • Artikel

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;

Siehe auch

Klassenübersicht