Sdílet prostřednictvím

CRBTree – třída

  • Článek

Tato třída poskytuje metody pro vytváření a používání červeného stromu.

Syntaxe

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

Parametry

K
Typ klíčového prvku.

V
Typ prvku value.

KTraits
Kód použitý ke zkopírování nebo přesunutí klíčových prvků. Další podrobnosti najdete v tématu CElementTraits – třída .

VTraits
Kód použitý ke zkopírování nebo přesunutí hodnotových prvků.

Členové

Veřejné definice typedef

Jméno popis
CRBTree::KINARGTYPE Typ použitý při předání klíče jako vstupního argumentu.
CRBTree::KOUTARGTYPE Typ použitý při vrácení klíče jako výstupního argumentu.
CRBTree::VINARGTYPE Typ použitý při předání hodnoty jako vstupní argument.
CRBTree::VOUTARGTYPE Typ použitý při předání hodnoty jako výstupního argumentu.

Veřejné třídy

Jméno popis
CRBTree::CPair – třída Třída obsahující prvky klíče a hodnoty.

Veřejné konstruktory

Jméno popis
CRBTree::~CRBTree Destruktor.

Veřejné metody

Jméno popis
CRBTree::FindFirstKeyAfter Voláním této metody zjistíte pozici elementu, který používá další dostupný klíč.
CRBTree::GetAt Voláním této metody získáte prvek na dané pozici ve stromu.
CRBTree::GetCount Voláním této metody získáte počet prvků ve stromu.
CRBTree::GetHeadPosition Voláním této metody získáte hodnotu pozice prvku v hlavě stromu.
CRBTree::GetKeyAt Voláním této metody získáte klíč z dané pozice ve stromu.
CRBTree::GetNext Voláním této metody získejte ukazatel na prvek uložený v objektu CRBTree a přejděte na pozici na další prvek.
CRBTree::GetNextAssoc Voláním této metody získejte klíč a hodnotu elementu uloženého v mapě a přejděte na pozici na další prvek.
CRBTree::GetNextKey Voláním této metody získáte klíč prvku uloženého ve stromu a přejdete na pozici dalšího prvku.
CRBTree::GetNextValue Voláním této metody získáte hodnotu elementu uloženého ve stromu a přejdete na pozici dalšího prvku.
CRBTree::GetPrev Voláním této metody získáte ukazatel na prvek uložený v objektu CRBTree a potom aktualizujte pozici na předchozí prvek.
CRBTree::GetTailPosition Voláním této metody získáte hodnotu pozice prvku na konci stromu.
CRBTree::GetValueAt Voláním této metody načtěte hodnotu uloženou na dané pozici v objektu CRBTree .
CRBTree::IsEmpty Voláním této metody otestujete prázdný stromový objekt.
CRBTree::RemoveAll Voláním této metody odeberete všechny prvky z objektu CRBTree .
CRBTree::RemoveAt Voláním této metody odeberete prvek na dané pozici v objektu CRBTree .
CRBTree::SetValueAt Voláním této metody změníte hodnotu uloženou na dané pozici v objektu CRBTree .

Poznámky

Červený-černý strom je binární vyhledávací strom, který používá další bit informací na každém uzlu k zajištění toho, že zůstane "vyvážená", to znamená, že výška stromu nezvětší nepřiměřeně velký a ovlivňuje výkon.

Tato třída šablony je navržena tak, aby ji používal CRBMap a CRBMultiMap. Většina metod, které tvoří tyto odvozené třídy jsou poskytovány CRBTree.

Podrobnější informace o různých třídách kolekcí a jejich funkcích a charakteristikách výkonu najdete v tématu Třídy kolekcí ATL.

Požadavky

Hlavička: atlcoll.h

CRBTree::CPair – třída

Třída obsahující prvky klíče a hodnoty.

class CPair : public __POSITION

Poznámky

Tuto třídu používají metody CRBTree::GetAt, CRBTree::GetNext a CRBTree::GetPrev pro přístup k prvkům klíče a hodnoty uložené ve stromové struktuře.

Členové jsou následující:

Datový člen Popis
m_key Datový člen, který ukládá klíčový prvek.
m_value Datový člen, který ukládá prvek hodnoty.

CRBTree::~CRBTree

Destruktor.

~CRBTree() throw();

Poznámky

Uvolní všechny přidělené prostředky. Volá CRBTree::RemoveAll k odstranění všech prvků.

CRBTree::FindFirstKeyAfter

Voláním této metody zjistíte pozici elementu, který používá další dostupný klíč.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

Parametry

key
Hodnota klíče.

Vrácená hodnota

Vrátí hodnotu pozice prvku, který používá další dostupný klíč. Pokud nejsou k dispozici žádné další prvky, vrátí se hodnota NULL.

Poznámky

Tato metoda usnadňuje procházení stromu, aniž by bylo nutné předem vypočítat hodnoty pozice.

CRBTree::GetAt

Voláním této metody získáte prvek na dané pozici ve stromu.

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

Parametry

Pos
Hodnota pozice.

key
Proměnná, která obdrží klíč.

value
Proměnná, která přijímá hodnotu.

Vrácená hodnota

První dva formuláře vrátí ukazatel na CPair. Třetí formulář získá klíč a hodnotu pro danou pozici.

Poznámky

Hodnotu pozice lze dříve určit voláním metody, jako je CRBTree::GetHeadPosition nebo CRBTree::GetTailPosition.

V sestaveních ladění dojde k selhání kontrolního výrazu, pokud se pos rovná hodnotě NULL.

CRBTree::GetCount

Voláním této metody získáte počet prvků ve stromu.

size_t GetCount() const throw();

Vrácená hodnota

Vrátí počet prvků (každý pár klíč/hodnota je jeden prvek) uložený ve stromu.

CRBTree::GetHeadPosition

Voláním této metody získáte hodnotu pozice prvku v hlavě stromu.

POSITION GetHeadPosition() const throw();

Vrácená hodnota

Vrátí hodnotu pozice prvku v hlavě stromu.

Poznámky

Hodnotu vrácenou GetHeadPosition pomocí metod, jako je CRBTree::GetKeyAt nebo CRBTree::GetNext pro procházení stromu a načtení hodnot.

CRBTree::GetKeyAt

Voláním této metody získáte klíč z dané pozice ve stromu.

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

Parametry

Pos
Hodnota pozice.

Vrácená hodnota

Vrátí klíč uložený na pozici pos ve stromu.

Poznámky

Pokud hodnota pozice není platná, výsledky jsou nepředvídatelné. V sestaveních ladění dojde k selhání kontrolního výrazu, pokud se pos rovná hodnotě NULL.

CRBTree::GetNext

Voláním této metody získejte ukazatel na prvek uložený v objektu CRBTree a přejděte na pozici na další prvek.

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

Parametry

Pos
Čítač pozice vrácený předchozím voláním metod, jako je CRBTree::GetHeadPosition nebo CRBTree::FindFirstKeyAfter.

Vrácená hodnota

Vrátí ukazatel na další hodnotu CPair ve stromu.

Poznámky

Čítač pozice pos se po každém volání aktualizuje. Pokud je načtený prvek poslední ve stromu, je položka pos nastavena na HODNOTU NULL.

CRBTree::GetNextAssoc

Voláním této metody získejte klíč a hodnotu elementu uloženého v mapě a přejděte na pozici na další prvek.

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

Parametry

Pos
Čítač pozice vrácený předchozím voláním metod, jako je CRBTree::GetHeadPosition nebo CRBTree::FindFirstKeyAfter.

key
Parametr šablony určující typ klíče stromu

value
Parametr šablony určující typ hodnoty stromu

Poznámky

Čítač pozice pos se po každém volání aktualizuje. Pokud je načtený prvek poslední ve stromu, je položka pos nastavena na HODNOTU NULL.

CRBTree::GetNextKey

Voláním této metody získáte klíč prvku uloženého ve stromu a přejdete na pozici dalšího prvku.

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

Parametry

Pos
Čítač pozice vrácený předchozím voláním metod, jako je CRBTree::GetHeadPosition nebo CRBTree::FindFirstKeyAfter.

Vrácená hodnota

Vrátí odkaz na další klíč ve stromu.

Poznámky

Aktualizace čítače aktuální pozice, pos. Pokud ve stromu nejsou žádné další položky, je čítač pozice nastaven na hodnotu NULL.

CRBTree::GetNextValue

Voláním této metody získáte hodnotu elementu uloženého ve stromu a přejdete na pozici dalšího prvku.

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

Parametry

Pos
Čítač pozice vrácený předchozím voláním metod, jako je CRBTree::GetHeadPosition nebo CRBTree::FindFirstKeyAfter.

Vrácená hodnota

Vrátí odkaz na další hodnotu ve stromu.

Poznámky

Aktualizace čítače aktuální pozice, pos. Pokud ve stromu nejsou žádné další položky, je čítač pozice nastaven na hodnotu NULL.

CRBTree::GetPrev

Voláním této metody získáte ukazatel na prvek uložený v objektu CRBTree a potom aktualizujte pozici na předchozí prvek.

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

Parametry

Pos
Čítač pozice vrácený předchozím voláním metod, jako je CRBTree::GetHeadPosition nebo CRBTree::FindFirstKeyAfter.

Vrácená hodnota

Vrátí ukazatel na předchozí hodnotu CPair uloženou ve stromu.

Poznámky

Aktualizace čítače aktuální pozice, pos. Pokud ve stromu nejsou žádné další položky, je čítač pozice nastaven na hodnotu NULL.

CRBTree::GetTailPosition

Voláním této metody získáte hodnotu pozice prvku na konci stromu.

POSITION GetTailPosition() const throw();

Vrácená hodnota

Vrátí hodnotu pozice prvku na konci stromu.

Poznámky

Hodnotu vrácenou GetTailPosition pomocí metod, jako je CRBTree::GetKeyAt nebo CRBTree::GetPrev pro procházení stromu a načtení hodnot.

CRBTree::GetValueAt

Voláním této metody načtěte hodnotu uloženou na dané pozici v objektu CRBTree .

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

Parametry

Pos
Čítač pozice vrácený předchozím voláním metod, jako je CRBTree::GetHeadPosition nebo CRBTree::FindFirstKeyAfter.

Vrácená hodnota

Vrátí odkaz na hodnotu uloženou na dané pozici v objektu CRBTree .

CRBTree::IsEmpty

Voláním této metody otestujete prázdný stromový objekt.

bool IsEmpty() const throw();

Vrácená hodnota

Vrátí hodnotu PRAVDA, pokud je strom prázdný, jinak nepravda.

CRBTree::KINARGTYPE

Typ použitý při předání klíče jako vstupního argumentu.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KOUTARGTYPE

Typ použitý při vrácení klíče jako výstupního argumentu.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

Voláním této metody odeberete všechny prvky z objektu CRBTree .

void RemoveAll() throw();

Poznámky

Vymaže CRBTree objekt a uvolní paměť použitou k uložení prvků.

CRBTree::RemoveAt

Voláním této metody odeberete prvek na dané pozici v objektu CRBTree .

void RemoveAt(POSITION pos) throw();

Parametry

Pos
Čítač pozice vrácený předchozím voláním metod, jako je CRBTree::GetHeadPosition nebo CRBTree::FindFirstKeyAfter.

Poznámky

Odebere dvojici klíč/hodnota uloženou na zadané pozici. Paměť použitá k uložení prvku je uvolněna. Pozice, na kterou odkazuje pos , je neplatná a zatímco pozice všech ostatních prvků ve stromu zůstane platná, nemusí nutně zachovat stejné pořadí.

CRBTree::SetValueAt

Voláním této metody změníte hodnotu uloženou na dané pozici v objektu CRBTree .

void SetValueAt(POSITION pos, VINARGTYPE value);

Parametry

Pos
Čítač pozice vrácený předchozím voláním metod, jako je CRBTree::GetHeadPosition nebo CRBTree::FindFirstKeyAfter.

value
Hodnota, kterou chcete přidat k objektu CRBTree .

Poznámky

Změní prvek hodnoty uložený na dané pozici v objektu CRBTree .

CRBTree::VINARGTYPE

Typ použitý při předání hodnoty jako vstupní argument.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

Typ použitý při předání hodnoty jako výstupního argumentu.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Viz také

Přehled třídy