Udostępnij za pośrednictwem

Klasa CRBTree

  • Artykuł

Ta klasa udostępnia metody tworzenia i używania czerwonego czarnego drzewa.

Składnia

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

Parametry

K
Typ kluczowego elementu.

V
Typ elementu wartości.

KTraits
Kod używany do kopiowania lub przenoszenia kluczowych elementów. Aby uzyskać więcej informacji, zobacz Klasa CElementTraits.

VTraits
Kod używany do kopiowania lub przenoszenia elementów wartości.

Członkowie

Definicje typów publicznych

Nazwa/nazwisko opis
CRBTree::KINARGTYPE Typ używany, gdy klucz jest przekazywany jako argument wejściowy.
CRBTree::KOUTARGTYPE Typ używany, gdy klucz jest zwracany jako argument wyjściowy.
CRBTree::VINARGTYPE Typ używany, gdy wartość jest przekazywana jako argument wejściowy.
CRBTree::VOUTARGTYPE Typ używany, gdy wartość jest przekazywana jako argument wyjściowy.

Klasy publiczne

Nazwa/nazwisko opis
Klasa CRBTree::CPair Klasa zawierająca elementy klucza i wartości.

Konstruktory publiczne

Nazwa/nazwisko opis
CRBTree::~CRBTree Destruktora.

Metody publiczne

Nazwa/nazwisko opis
CRBTree::FindFirstKeyAfter Wywołaj tę metodę, aby znaleźć położenie elementu, który używa następnego dostępnego klucza.
CRBTree::GetAt Wywołaj tę metodę, aby pobrać element na danej pozycji w drzewie.
CRBTree::GetCount Wywołaj tę metodę, aby uzyskać liczbę elementów w drzewie.
CRBTree::GetHeadPosition Wywołaj tę metodę, aby uzyskać wartość pozycji elementu na czele drzewa.
CRBTree::GetKeyAt Wywołaj tę metodę, aby pobrać klucz z danej pozycji w drzewie.
CRBTree::GetNext Wywołaj tę metodę, aby uzyskać wskaźnik do elementu przechowywanego CRBTree w obiekcie, a następnie przejdź do następnego elementu.
CRBTree::GetNextAssoc Wywołaj tę metodę, aby pobrać klucz i wartość elementu przechowywanego na mapie i przejść do następnego elementu.
CRBTree::GetNextKey Wywołaj tę metodę, aby pobrać klucz elementu przechowywanego w drzewie i przejść do następnego elementu.
CRBTree::GetNextValue Wywołaj tę metodę, aby uzyskać wartość elementu przechowywanego w drzewie i przejść do następnego elementu.
CRBTree::GetPrev Wywołaj tę metodę, aby uzyskać wskaźnik do elementu przechowywanego CRBTree w obiekcie, a następnie zaktualizuj pozycję do poprzedniego elementu.
CRBTree::GetTailPosition Wywołaj tę metodę, aby uzyskać wartość pozycji elementu na ogonie drzewa.
CRBTree::GetValueAt Wywołaj tę metodę, aby pobrać wartość przechowywaną na danej pozycji w CRBTree obiekcie.
CRBTree::IsEmpty Wywołaj tę metodę, aby przetestować pusty obiekt drzewa.
CRBTree::RemoveAll Wywołaj tę metodę, aby usunąć wszystkie elementy z CRBTree obiektu.
CRBTree::RemoveAt Wywołaj tę metodę, aby usunąć element na danej pozycji w CRBTree obiekcie.
CRBTree::SetValueAt Wywołaj tę metodę, aby zmienić wartość przechowywaną na danej pozycji w CRBTree obiekcie.

Uwagi

Czerwone czarne drzewo to binarne drzewo wyszukiwania, które używa dodatkowych informacji na węzeł, aby upewnić się, że pozostaje "zrównoważony", czyli wysokość drzewa nie rośnie nieproporcjonalnie duży i wpływa na wydajność.

Ta klasa szablonu jest przeznaczona do użycia przez CRBMap i CRBMultiMap. Większość metod tworzących te klasy pochodne są dostarczane przez CRBTreeprogram .

Aby zapoznać się z bardziej kompletnym omówieniem różnych klas kolekcji oraz ich cech i cech wydajności, zobacz Klasy kolekcji ATL.

Wymagania

Nagłówek: atlcoll.h

Klasa CRBTree::CPair

Klasa zawierająca elementy klucza i wartości.

class CPair : public __POSITION

Uwagi

Ta klasa jest używana przez metody CRBTree::GetAt, CRBTree::GetNext i CRBTree::GetPrev , aby uzyskać dostęp do elementów klucza i wartości przechowywanych w strukturze drzewa.

Członkowie są następująco:

Element członkowski danych opis
m_key Element członkowski danych przechowujące klucz.
m_value Element członkowski danych przechowujące element wartości.

CRBTree::~CRBTree

Destruktora.

~CRBTree() throw();

Uwagi

Zwalnia wszystkie przydzielone zasoby. Wywołuje metodę CRBTree::RemoveAll , aby usunąć wszystkie elementy.

CRBTree::FindFirstKeyAfter

Wywołaj tę metodę, aby znaleźć położenie elementu, który używa następnego dostępnego klucza.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

Parametry

key
Wartość klucza.

Wartość zwracana

Zwraca wartość pozycji elementu, który używa następnego dostępnego klucza. Jeśli nie ma więcej elementów, zwracana jest wartość NULL.

Uwagi

Ta metoda ułatwia przechodzenie drzewa bez konieczności wcześniejszego obliczania wartości pozycji.

CRBTree::GetAt

Wywołaj tę metodę, aby pobrać element na danej pozycji w drzewie.

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

Parametry

Poz
Wartość pozycji.

key
Zmienna, która odbiera klucz.

wartość
Zmienna, która odbiera wartość.

Wartość zwracana

Pierwsze dwie formularze zwracają wskaźnik do CPair. Trzeci formularz uzyskuje klucz i wartość dla danej pozycji.

Uwagi

Wartość pozycji można wcześniej określić za pomocą wywołania metody, takiej jak CRBTree::GetHeadPosition lub CRBTree::GetTailPosition.

W kompilacjach debugowania wystąpi błąd asercji, jeśli wiersze są równe null.

CRBTree::GetCount

Wywołaj tę metodę, aby uzyskać liczbę elementów w drzewie.

size_t GetCount() const throw();

Wartość zwracana

Zwraca liczbę elementów (każda para klucz/wartość jest jednym elementem) przechowywanych w drzewie.

CRBTree::GetHeadPosition

Wywołaj tę metodę, aby uzyskać wartość pozycji elementu na czele drzewa.

POSITION GetHeadPosition() const throw();

Wartość zwracana

Zwraca wartość pozycji elementu na czele drzewa.

Uwagi

Wartość zwracana przez GetHeadPosition program może być używana z metodami, takimi jak CRBTree::GetKeyAt lub CRBTree::GetNext , aby przejść przez drzewo i pobrać wartości.

CRBTree::GetKeyAt

Wywołaj tę metodę, aby pobrać klucz z danej pozycji w drzewie.

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

Parametry

Poz
Wartość pozycji.

Wartość zwracana

Zwraca klucz przechowywany w punkcie pos w drzewie.

Uwagi

Jeśli pos nie jest prawidłową wartością pozycji, wyniki są nieprzewidywalne. W kompilacjach debugowania wystąpi błąd asercji, jeśli wiersze są równe null.

CRBTree::GetNext

Wywołaj tę metodę, aby uzyskać wskaźnik do elementu przechowywanego CRBTree w obiekcie, a następnie przejdź do następnego elementu.

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

Parametry

Poz
Licznik położenia zwrócony przez poprzednie wywołanie metod, takich jak CRBTree::GetHeadPosition lub CRBTree::FindFirstKeyAfter.

Wartość zwracana

Zwraca wskaźnik do następnej wartości CPair w drzewie.

Uwagi

Licznik położenia pos jest aktualizowany po każdym wywołaniu. Jeśli pobrany element jest ostatnim elementem w drzewie, element pos jest ustawiony na wartość NULL.

CRBTree::GetNextAssoc

Wywołaj tę metodę, aby pobrać klucz i wartość elementu przechowywanego na mapie i przejść do następnego elementu.

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

Parametry

Poz
Licznik położenia zwrócony przez poprzednie wywołanie metod, takich jak CRBTree::GetHeadPosition lub CRBTree::FindFirstKeyAfter.

key
Parametr szablonu określający typ klucza drzewa.

wartość
Parametr szablonu określający typ wartości drzewa.

Uwagi

Licznik położenia pos jest aktualizowany po każdym wywołaniu. Jeśli pobrany element jest ostatnim elementem w drzewie, element pos jest ustawiony na wartość NULL.

CRBTree::GetNextKey

Wywołaj tę metodę, aby pobrać klucz elementu przechowywanego w drzewie i przejść do następnego elementu.

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

Parametry

Poz
Licznik położenia zwrócony przez poprzednie wywołanie metod, takich jak CRBTree::GetHeadPosition lub CRBTree::FindFirstKeyAfter.

Wartość zwracana

Zwraca odwołanie do następnego klucza w drzewie.

Uwagi

Aktualizacje bieżącego licznika położenia, pos. Jeśli w drzewie nie ma więcej wpisów, licznik położenia jest ustawiony na wartość NULL.

CRBTree::GetNextValue

Wywołaj tę metodę, aby uzyskać wartość elementu przechowywanego w drzewie i przejść do następnego elementu.

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

Parametry

Poz
Licznik położenia zwrócony przez poprzednie wywołanie metod, takich jak CRBTree::GetHeadPosition lub CRBTree::FindFirstKeyAfter.

Wartość zwracana

Zwraca odwołanie do następnej wartości w drzewie.

Uwagi

Aktualizacje bieżącego licznika położenia, pos. Jeśli w drzewie nie ma więcej wpisów, licznik położenia jest ustawiony na wartość NULL.

CRBTree::GetPrev

Wywołaj tę metodę, aby uzyskać wskaźnik do elementu przechowywanego CRBTree w obiekcie, a następnie zaktualizuj pozycję do poprzedniego elementu.

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

Parametry

Poz
Licznik położenia zwrócony przez poprzednie wywołanie metod, takich jak CRBTree::GetHeadPosition lub CRBTree::FindFirstKeyAfter.

Wartość zwracana

Zwraca wskaźnik do poprzedniej wartości CPair przechowywanej w drzewie.

Uwagi

Aktualizacje bieżącego licznika położenia, pos. Jeśli w drzewie nie ma więcej wpisów, licznik położenia jest ustawiony na wartość NULL.

CRBTree::GetTailPosition

Wywołaj tę metodę, aby uzyskać wartość pozycji elementu na ogonie drzewa.

POSITION GetTailPosition() const throw();

Wartość zwracana

Zwraca wartość położenia elementu na ogonie drzewa.

Uwagi

Wartość zwracana przez GetTailPosition program może być używana z metodami, takimi jak CRBTree::GetKeyAt lub CRBTree::GetPrev , aby przejść przez drzewo i pobrać wartości.

CRBTree::GetValueAt

Wywołaj tę metodę, aby pobrać wartość przechowywaną na danej pozycji w CRBTree obiekcie.

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

Parametry

Poz
Licznik położenia zwrócony przez poprzednie wywołanie metod, takich jak CRBTree::GetHeadPosition lub CRBTree::FindFirstKeyAfter.

Wartość zwracana

Zwraca odwołanie do wartości przechowywanej na danej pozycji w CRBTree obiekcie.

CRBTree::IsEmpty

Wywołaj tę metodę, aby przetestować pusty obiekt drzewa.

bool IsEmpty() const throw();

Wartość zwracana

Zwraca wartość TRUE, jeśli drzewo jest puste, w przeciwnym razie wartość FALSE.

CRBTree::KINARGTYPE

Typ używany, gdy klucz jest przekazywany jako argument wejściowy.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KOUTARGTYPE

Typ używany, gdy klucz jest zwracany jako argument wyjściowy.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

Wywołaj tę metodę, aby usunąć wszystkie elementy z CRBTree obiektu.

void RemoveAll() throw();

Uwagi

Czyści CRBTree obiekt, zwalniając pamięć używaną do przechowywania elementów.

CRBTree::RemoveAt

Wywołaj tę metodę, aby usunąć element na danej pozycji w CRBTree obiekcie.

void RemoveAt(POSITION pos) throw();

Parametry

Poz
Licznik położenia zwrócony przez poprzednie wywołanie metod, takich jak CRBTree::GetHeadPosition lub CRBTree::FindFirstKeyAfter.

Uwagi

Usuwa parę klucz/wartość przechowywaną na określonej pozycji. Pamięć używana do przechowywania elementu jest zwalniana. Pozycja, do której odwołuje się funkcja pos , staje się nieprawidłowa, a pozycja innych elementów w drzewie pozostaje prawidłowa, niekoniecznie zachowują tę samą kolejność.

CRBTree::SetValueAt

Wywołaj tę metodę, aby zmienić wartość przechowywaną na danej pozycji w CRBTree obiekcie.

void SetValueAt(POSITION pos, VINARGTYPE value);

Parametry

Poz
Licznik położenia zwrócony przez poprzednie wywołanie metod, takich jak CRBTree::GetHeadPosition lub CRBTree::FindFirstKeyAfter.

wartość
Wartość do dodania CRBTree do obiektu.

Uwagi

Zmienia element wartości przechowywany na danej pozycji w CRBTree obiekcie.

CRBTree::VINARGTYPE

Typ używany, gdy wartość jest przekazywana jako argument wejściowy.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

Typ używany, gdy wartość jest przekazywana jako argument wyjściowy.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Zobacz też

Omówienie klasy