Класс CRBTree

Этот класс предоставляет методы для создания и использования дерева Red-Black.

Синтаксис

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

Параметры

K
Тип ключевого элемента.

V
Тип элемента value.

KTraits
Код, используемый для копирования или перемещения ключевых элементов. Дополнительные сведения см. в классе CElementTraits.

Виртуальные признаки
Код, используемый для копирования или перемещения элементов значения.

Участники

Общедоступные определения типов

Имя	Описание
CRBTree::KINARGTYPE	Тип, используемый при передаче ключа в качестве входного аргумента.
CRBTree::KOUTARGTYPE	Тип, используемый при возврате ключа в качестве выходного аргумента.
CRBTree::VINARGTYPE	Тип, используемый при передаче значения в качестве входного аргумента.
CRBTree::VOUTARGTYPE	Тип, используемый при передаче значения в качестве выходного аргумента.

Открытые классы

Имя	Описание
Класс CRBTree::CPair	Класс, содержащий элементы ключа и значения.

Открытые конструкторы

Имя	Описание
CRBTree::~CRBTree	Деструктор

Открытые методы

Имя	Описание
CRBTree::FindFirstKeyAfter	Вызовите этот метод, чтобы найти позицию элемента, использующего следующий доступный ключ.
CRBTree::GetAt	Вызовите этот метод, чтобы получить элемент в заданной позиции в дереве.
CRBTree::GetCount	Вызовите этот метод, чтобы получить количество элементов в дереве.
CRBTree::GetHeadPosition	Вызовите этот метод, чтобы получить значение позиции для элемента в голове дерева.
CRBTree::GetKeyAt	Вызовите этот метод, чтобы получить ключ из заданной позиции в дереве.
CRBTree::GetNext	Вызовите этот метод, чтобы получить указатель на элемент, хранящийся в объекте CRBTree , и перейти к следующему элементу.
CRBTree::GetNextAssoc	Вызовите этот метод, чтобы получить ключ и значение элемента, хранящегося в карте, и перейти к следующему элементу.
CRBTree::GetNextKey	Вызовите этот метод, чтобы получить ключ элемента, хранящегося в дереве, и перейти к следующему элементу.
CRBTree::GetNextValue	Вызовите этот метод, чтобы получить значение элемента, хранящегося в дереве, и перейти к следующему элементу.
CRBTree::GetPrev	Вызовите этот метод, чтобы получить указатель на элемент, хранящийся в объекте CRBTree , а затем обновите положение до предыдущего элемента.
CRBTree::GetTailPosition	Вызовите этот метод, чтобы получить значение позиции для элемента в хвосте дерева.
CRBTree::GetValueAt	Вызовите этот метод, чтобы получить значение, хранящееся в заданной позиции в объекте CRBTree .
CRBTree::IsEmpty	Вызовите этот метод для проверки пустого объекта дерева.
CRBTree::RemoveAll	Вызовите этот метод, чтобы удалить все элементы из CRBTree объекта.
CRBTree::RemoveAt	Вызовите этот метод, чтобы удалить элемент в заданной позиции в объекте CRBTree .
CRBTree::SetValueAt	Вызовите этот метод, чтобы изменить значение, хранящееся в заданной позиции в объекте CRBTree .

Замечания

Дерево Red-Black — это дерево двоичного поиска, которое использует дополнительную битовую информацию для каждого узла, чтобы гарантировать, что она остается "сбалансированной", т. е. высота дерева не увеличивается непропорционально большой и влияет на производительность.

Этот класс шаблона предназначен для использования CRBMap и CRBMultiMap. Основная часть методов, составляющих эти производные классы, предоставляются CRBTree.

Более подробное обсуждение различных классов коллекций и их характеристик и характеристик производительности см. в классах коллекций ATL.

Требования

Заголовок: atlcoll.h

Класс CRBTree::CPair

Класс, содержащий элементы ключа и значения.

class CPair : public __POSITION

Замечания

Этот класс используется методами CRBTree::GetAt, CRBTree::GetNext и CRBTree::GetPrev для доступа к элементам ключа и значения, хранящимся в структуре дерева.

Члены приведены следующим образом:

Элемент данных	Description
m_key	Элемент данных, в котором хранится ключевой элемент.
m_value	Элемент данных, в котором хранится элемент value.

CRBTree::~CRBTree

Деструктор

~CRBTree() throw();

Замечания

Освобождает все выделенные ресурсы. Вызывает CRBTree::RemoveAll для удаления всех элементов.

CRBTree::FindFirstKeyAfter

Вызовите этот метод, чтобы найти позицию элемента, использующего следующий доступный ключ.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

Параметры

key
Значение ключа.

Возвращаемое значение

Возвращает значение позиции элемента, использующего следующий доступный ключ. Если больше элементов нет, возвращается значение NULL.

Замечания

Этот метод упрощает обход дерева без необходимости вычислять значения позиции заранее.

CRBTree::GetAt

Вызовите этот метод, чтобы получить элемент в заданной позиции в дереве.

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

Параметры

pos
Позиция.

key
Переменная, получающая ключ.

значение
Переменная, получающая значение.

Возвращаемое значение

Первые две формы возвращают указатель на CPair. Третья форма получает ключ и значение для заданной позиции.

Замечания

Значение позиции можно определить ранее с помощью вызова метода, например CRBTree::GetHeadPosition или CRBTree::GetTailPosition.

В сборках отладки произойдет сбой утверждения, если pos равен NULL.

CRBTree::GetCount

Вызовите этот метод, чтобы получить количество элементов в дереве.

size_t GetCount() const throw();

Возвращаемое значение

Возвращает количество элементов (каждая пара "ключ-значение" является одним элементом), хранящимся в дереве.

CRBTree::GetHeadPosition

Вызовите этот метод, чтобы получить значение позиции для элемента в голове дерева.

POSITION GetHeadPosition() const throw();

Возвращаемое значение

Возвращает значение позиции элемента в верхней части дерева.

Замечания

Возвращаемое GetHeadPosition значение можно использовать с такими методами, как CRBTree::GetKeyAt или CRBTree::GetNext для обхода дерева и получения значений.

CRBTree::GetKeyAt

Вызовите этот метод, чтобы получить ключ из заданной позиции в дереве.

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

Параметры

pos
Позиция.

Возвращаемое значение

Возвращает ключ, хранящийся в позиции pos в дереве.

Замечания

Если значение позиции не является допустимым, результаты непредсказуемы. В сборках отладки произойдет сбой утверждения, если pos равен NULL.

CRBTree::GetNext

Вызовите этот метод, чтобы получить указатель на элемент, хранящийся в объекте CRBTree , и перейти к следующему элементу.

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

Параметры

pos
Счетчик позиции, возвращаемый предыдущим вызовом методов, таких как CRBTree::GetHeadPosition или CRBTree::FindFirstKeyAfter.

Возвращаемое значение

Возвращает указатель на следующее значение CPair в дереве.

Замечания

Счетчик позиции pos обновляется после каждого вызова. Если извлеченный элемент является последним в дереве, pos имеет значение NULL.

CRBTree::GetNextAssoc

Вызовите этот метод, чтобы получить ключ и значение элемента, хранящегося в карте, и перейти к следующему элементу.

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

Параметры

pos
Счетчик позиции, возвращаемый предыдущим вызовом методов, таких как CRBTree::GetHeadPosition или CRBTree::FindFirstKeyAfter.

key
Параметр шаблона, указывающий тип ключа дерева.

значение
Параметр шаблона, указывающий тип значения дерева.

Замечания

Счетчик позиции pos обновляется после каждого вызова. Если извлеченный элемент является последним в дереве, pos имеет значение NULL.

CRBTree::GetNextKey

Вызовите этот метод, чтобы получить ключ элемента, хранящегося в дереве, и перейти к следующему элементу.

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

Параметры

pos
Счетчик позиции, возвращаемый предыдущим вызовом методов, таких как CRBTree::GetHeadPosition или CRBTree::FindFirstKeyAfter.

Возвращаемое значение

Возвращает ссылку на следующий ключ в дереве.

Замечания

Обновляет счетчик текущей позиции, pos. Если в дереве больше нет записей, счетчик позиции имеет значение NULL.

CRBTree::GetNextValue

Вызовите этот метод, чтобы получить значение элемента, хранящегося в дереве, и перейти к следующему элементу.

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

Параметры

pos
Счетчик позиции, возвращаемый предыдущим вызовом методов, таких как CRBTree::GetHeadPosition или CRBTree::FindFirstKeyAfter.

Возвращаемое значение

Возвращает ссылку на следующее значение в дереве.

Замечания

Обновляет счетчик текущей позиции, pos. Если в дереве больше нет записей, счетчик позиции имеет значение NULL.

CRBTree::GetPrev

Вызовите этот метод, чтобы получить указатель на элемент, хранящийся в объекте CRBTree , а затем обновите положение до предыдущего элемента.

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

Параметры

pos
Счетчик позиции, возвращаемый предыдущим вызовом методов, таких как CRBTree::GetHeadPosition или CRBTree::FindFirstKeyAfter.

Возвращаемое значение

Возвращает указатель на предыдущее значение CPair , хранящееся в дереве.

Замечания

Обновляет счетчик текущей позиции, pos. Если в дереве больше нет записей, счетчик позиции имеет значение NULL.

CRBTree::GetTailPosition

Вызовите этот метод, чтобы получить значение позиции для элемента в хвосте дерева.

POSITION GetTailPosition() const throw();

Возвращаемое значение

Возвращает значение позиции элемента в хвосте дерева.

Замечания

Возвращаемое GetTailPosition значение можно использовать с такими методами, как CRBTree::GetKeyAt или CRBTree::GetPrev для обхода дерева и получения значений.

CRBTree::GetValueAt

Вызовите этот метод, чтобы получить значение, хранящееся в заданной позиции в объекте CRBTree .

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

Параметры

pos
Счетчик позиции, возвращаемый предыдущим вызовом методов, таких как CRBTree::GetHeadPosition или CRBTree::FindFirstKeyAfter.

Возвращаемое значение

Возвращает ссылку на значение, хранящееся в заданной позиции объекта CRBTree .

CRBTree::IsEmpty

Вызовите этот метод для проверки пустого объекта дерева.

bool IsEmpty() const throw();

Возвращаемое значение

Возвращает значение TRUE, если дерево пусто, значение FALSE в противном случае.

CRBTree::KINARGTYPE

Тип, используемый при передаче ключа в качестве входного аргумента.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KOUTARGTYPE

Тип, используемый при возврате ключа в качестве выходного аргумента.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

Вызовите этот метод, чтобы удалить все элементы из CRBTree объекта.

void RemoveAll() throw();

Замечания

Очищает CRBTree объект, освобождая память, используемую для хранения элементов.

CRBTree::RemoveAt

Вызовите этот метод, чтобы удалить элемент в заданной позиции в объекте CRBTree .

void RemoveAt(POSITION pos) throw();

Параметры

pos
Счетчик позиции, возвращаемый предыдущим вызовом методов, таких как CRBTree::GetHeadPosition или CRBTree::FindFirstKeyAfter.

Замечания

Удаляет пару "ключ-значение", хранящуюся в указанной позиции. Память, используемая для хранения элемента, освобождается. Позиция, на которую ссылается pos, становится недопустимой, и в то время как позиция любых других элементов в дереве остается допустимой, они не обязательно сохраняют тот же порядок.

CRBTree::SetValueAt

Вызовите этот метод, чтобы изменить значение, хранящееся в заданной позиции в объекте CRBTree .

void SetValueAt(POSITION pos, VINARGTYPE value);

Параметры

pos
Счетчик позиции, возвращаемый предыдущим вызовом методов, таких как CRBTree::GetHeadPosition или CRBTree::FindFirstKeyAfter.

значение
Значение, добавляемое в CRBTree объект.

Замечания

Изменяет элемент значения, хранящийся в заданной позиции в объекте CRBTree .

CRBTree::VINARGTYPE

Тип, используемый при передаче значения в качестве входного аргумента.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

Тип, используемый при передаче значения в качестве выходного аргумента.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

См. также

Общие сведения о классе