Задание persistent_set

В этом задании требуется написать класс, реализующий персистентное бинарное дерево поиска (можно несбалансированное).

Список функций, которые необходимо реализовать, указаны в файле persistent_set.h. Семантика функций должна повторять поведение std::set из стандартной библиотеки. Помимо этого, должна быть реализована персистентность в следующем виде:

• Копирование и копирующее присваивание дерева производится без дополнительных аллокаций и с nothrow гарантией
• Удаление и добавление элементов меняет только то дерево, в котором они производятся, копии меняться не должны
• Удаление и добавление элементов всё так же должно производиться за O(h), где h - высота дерева, не должны копироваться все узлы дерева
• После добавления и удаления элементов имеющиеся итераторы указывают на элементы в изменённой версии дерева (поведение не должно отличаться от std::set)

В persistent_set.h указана требуемая вычислительная сложность и гарантии исключений для каждой функции, кроме persistent_set::begin, persistent_set::end, persistent_set::iterator::operator++ и persistent_set::iterator::operator--. Для них требуется, чтобы отдельно каждая из функций работала не больше чем за O(h).

Так же persistent_set не должен требовать от элементов конструктора по умолчанию. Вдобавок пустой persistent_set ни в какой момент не должен содержать данных на хипе и, соответсвенно, контсруктор по умолчанию не должен совершать никаких динамических аллокаций.

При выполнении задания разрешается (и рекомендуется) пользоваться умными указателями.