2.5 KiB
Домашнее задание №4
📗 В домашнем задании нужно реализовать упорядоченный словарь.
Идея упорядоченного словаря заключается в том, что он будет реализован на основе бинарного дерева поиска (BST). Дерево будет строиться только по ключам элементов, значения элементов при построении дерева не учитываются. Элементы с одинаковыми ключами в упорядоченном словаре хранить нельзя.
Поподробнее с бинарными деревьями поиска можно познакомиться здесь.
API для упорядоченного словаря будет выглядеть следующим образом:
type OrderedMap struct { ... }
func NewOrderedMap() OrderedMap // создать упорядоченный словарь
func (m *OrderedMap) Insert(key, value int) // добавить элемент в словарь
func (m *OrderedMap) Erase(key int) // удалить элемент из словари
func (m *OrderedMap) Contains(key int) bool // проверить существование элемента в словаре
func (m *OrderedMap) Size() int // получить количество элементов в словаре
func (m *OrderedMap) ForEach(action func(int, int)) // применить функцию к каждому элементу словаря от меньшего к большему
📌 Для выполнения домашнего задания подготовлен шаблон кода и основные тесты, которую помогут проверить корректность реализации конвертации. Шаблона доступен по ссылке.
Задание со звездочкой
Выполнять необязательно, но если вы уже знакомы c дженериками в Go, то попробуйте реализовать обобщенную OrderedMap, которая сможет работать с любыми comparable типами данных в качестве ключей и абсолютно любыми типами данных в качестве значений.