36 lines
2.5 KiB
Markdown
36 lines
2.5 KiB
Markdown
# Домашнее задание №4
|
||
|
||
📗 В домашнем задании нужно реализовать упорядоченный словарь.
|
||
|
||
|
||
|
||
Идея упорядоченного словаря заключается в том, что он будет реализован на основе бинарного дерева поиска (BST). Дерево будет строиться только по ключам элементов, значения элементов при построении дерева не учитываются. Элементы с одинаковыми ключами в упорядоченном словаре хранить нельзя.
|
||
|
||
|
||
|
||
Поподробнее с бинарными деревьями поиска можно познакомиться здесь.
|
||
|
||
|
||
|
||
API для упорядоченного словаря будет выглядеть следующим образом:
|
||
|
||
|
||
```go
|
||
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 типами данных в качестве ключей и абсолютно любыми типами данных в качестве значений.
|
||
|