В этой подзадаче вам нужно реализовать упрощенный аналог класса std::set под названием Set. Ваш Set должен иметь два шаблонных параметра: Key - тип, хранящийся в Set и C - сравнение на отношение "строго меньше", определяющее линейный порядок на элементах типа Key. Гарантируется, что в тестах все порядки будут линейными. Заметьте, ваш Set должен уметь работать без уточнения второго шаблонного параметра с типами, для которых есть оператор сравнения меньше (и только он). Для этого загляните в functional, там есть полезное для вас решение.
В данной задаче предполагается, что вы сами выбираете, какое дерево поиска использовать. Если используете декартово, то ознакомьтесь с тем, как правильно генерировать псевдослучайные числа. Для этого изучите API std::mt19337 и std::uniform_distribution. Заметьте, мы делаем не аналог std::multiset, а именно std::set, так что не нужно думать о поддержке уникальных элементов.
Детали реализации контейнера Set
Класс должен поддерживать следующий функционал:
- Конструктор по умолчанию - создает пустое множество (как можете догадаться, памяти не должно никакой аллоцироваться)
- Правило "трех":
- Конструктор копирования, выполняющий полное копирование. Должен работать за линейное время от размера Set (то есть нельзя так просто взять и вставить все элементы)
- Копирующий оператор присваивания, аналогично интерфейсу выше
- Деструктор
- Метод Size() - возвращает размер
- Метод Empty() - пуст ли контейнер
- Метод Clear() - очищает контейнер, но оставляет его пригодным для использования
- Метод void Insert(const Key& elem) - добавляет elem в множество
- Метод void Erase(const Key& elem) - удаляет элемент elem из множества. Если таковой отсутствует, то ничего не делать. Обратите внимание, что std::set умеет делать куда больше различных удалений, однако обойдемся только одним.
В жизни мы привыкли работать с массивами или хотя бы с контейнерами, по которым можно проитерироваться. В случае с std::set очевиден порядок итерирования, однако совсем неочевидно, как это делать? Вторая часть задачи посвящена как раз посвящена итераторам над вашим Set. Заметьте, что полное итерирование по Set происходит в порядке in-order traverse, который осуществляется рекурсивно, но в нашем случае мы должны умело сохранять рекурсию и уметь останавливаться в фиксированный момент.
Детали реализации итераторов
-
Вам надо реализовать Bidirectional Iterator, в ходе лекции по итераторам вам рассказывали API итераторов различных категорий и про iterator_traits, вам надо реализовать все это.
-
Также необходимо реализовать методы cbegin и cend, crbegin и crend для Set.
-
Реализуйте оператор меньше для лексикографического сравнения сетов.
- Методы LowerBound(const Key& elem) и UpperBound(const Key& elem). Загляните в документацию std::set, чтобы прописать полную сигнатуру и понять эффект.
- Метод Find(const Key& elem) - загляните в документацию std::set, чтобы прописать полную сигнатуру и понять эффект.