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