Поделиться через

Класс 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;

См. также

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