Мне нужна структура данных, похожая на карту (на C++) для хранения пар (Key,T) со следующей функциональностью:
- Вы можете вставлять новые элементы (Key,T) в текущую структуру
- Вы можете искать элементы на основе ключа в текущей структуре
- Вы можете сделать «снимок» текущей версии структуры
- Вы можете переключиться на одну из версий структур, с которых вы сделали снимок, и продолжить все операции оттуда.
- Полностью удалить одну из версий
Что мне не нужно
- Удаление элемента из конструкции
- Слияние разных вариантов конструкции в один
- Итерация по всем (или некоторым) элементам, хранящимся в настоящее время в структуре
Другими словами, у вас есть некоторая структура поиска, которую вы можете создать, но в любой момент вы можете перейти в историю и расширить более раннюю/другую версию структуры другим способом. Позже вы можете переключаться между этими разными версиями.
В моем проекте Key и T, скорее всего, будут целыми числами или значениями указателя, но не строками.
Основная цель состоит в том, чтобы уменьшить временную сложность; потребление пространства вторично (но также должно быть разумным). Чтобы уточнить, для меня log(N)+log(S) (где N-количество элементов, S-количество снимков) было бы достаточно, хотя чем быстрее, тем лучше :)
У меня есть приблизительное представление о том, как это реализовать --- например: будучи структурой бинарного дерева поиска, вставка нового элемента может клонировать путь от корня до места вставки, сохраняя при этом остальную часть дерева нетронутой. Переключение версий дерева было бы эквивалентно выбору другой версии корневого узла, для которого некоторые изменения просто не видны.
Однако, чтобы сделать это пользовательское дерево эффективным (например, самобалансирующимся), потребуются дополнительные усилия и тщательное программирование. Конечно, я могу сделать это сам, но, возможно, для этого уже существуют библиотеки?
Кроме того, вероятно, есть правильное имя для такого типа структуры данных, которое я просто не знаю, что делает мои поиски в Google (или SO-поиски) полными неудачами...
Спасибо за помощь!
