| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
| Максимальный балл: | 8 |
Задание: Консистентное дерево или список.
У каждого нода появляются поля deleted и ref_count для поддержки консистентных итераторов. В начале у узла всегда ref_count=2, а левый и правый sentinel никогда не удаляются. Итераторы на время указания на объект увеличивают ref_count.
Если при обратном уменьшении ref_count значение достигло нуля и выставлен флаг deleted, то узел полностью удаляется.
Итераторы не гарантируют, что ++-- вернётся на тот-же объект, однако все операции всегда приводят к консистентному состоянию.
При переходе на соседний нод, нужно проускать удалённые. Реализуется это либо через поле deleted, либо через проверку инварианта двусвязного списка node->next->prev == node
Отправьте ссылку на конкретный коммит в репозитории на Github, например
https://github.com/klenin/cats-main/commit/dce22c8348808959881ed7d6852c520a41e47c9a
В качестве среды разработки укажите Answer text.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|