Эффективный поиск буфера с применением стека модификаций данных
Я пытаюсь написать библиотеку C ++ 11 как часть более широкого проекта, который реализует стек изменений (модификация, вставка и удаление), реализованных поверх исходного буфера. Затем цель состоит в том, чтобы иметь возможность быстро просмотреть «изменения» и вывести измененные данные.
Мой текущий подход:
- Вести упорядоченный список изменений, упорядоченный по смещению начала изменения
- Также поддерживайте стек тех же самых изменений, чтобы их можно было откатить по порядку.
- Новые изменения помещаются в стек и вставляются в список в нужном месте.
- Список изменений по смещению может быть изменен, если изменение взаимодействует с другими
- Например, изменение байтов 5-10 делает недействительным начало более ранней модификации с 8-12
- Кроме того, изменения вставки или удаления изменят видимое смещение данных, возникающих после них (удаление байтов 5-10 означает, что то, что раньше было байтом 20, теперь находится в 15)
- Чтобы найти измененные данные, вы можете просмотреть список изменений, которые применяются (и смещение в этом изменении, которое применяется — другое изменение могло бы сделать недействительными некоторые из них), или найти правое смещение в исходных данных, если не было внесено никаких изменений это смещение
- Цель в том, чтобы сделать поиск быстрым — добавление изменения может потребовать некоторых усилий, чтобы возиться со списком, но поиск позже, который значительно превзойдет количество модификаций, в упорядоченном списке должен быть довольно простым.
- Также вам не нужно непрерывно копировать данные — данные каждого изменения хранятся вместе с ним, а исходные данные не затрагиваются.
- Отмена затем реализуется путем выталкивания последнего изменения из стека и отмены любых изменений, внесенных в него путем добавления этого изменения.
Это кажется довольно сложной задачей — нужно позаботиться о многих вещах, и я быстро накапливаю сложный код!
Я уверен, что это должно быть проблемой, с которой сталкивались другие программы, но просмотр различных шестнадцатеричных редакторов и т. Д. Не указал мне на полезную реализацию. Есть ли название для этой проблемы («стек отмены данных» и друзья не слишком далеко зашли!), Или библиотека, которую можно использовать, даже в качестве ссылки, для такого рода вещей?
Решение
Я считаю, что наиболее распространенный подход (который я успешно использовал в прошлом) — это просто сохранить исходное состояние и затем поместить каждую операцию изменения (что делается + аргументы) в стек отмены. Затем, чтобы перейти к определенному предыдущему состоянию, вы начинаете с оригинала и применяете все изменения, кроме тех, которые вы хотите отменить.
Это гораздо проще реализовать, чем пытаться определить, какие части данных изменились, и это работает хорошо, если сами операции не занимают много времени (и, следовательно, медленно «воспроизводят» исходное состояние).
Другие решения
Я бы посмотрел на постоянные структуры данных, такие как https://en.wikipedia.org/wiki/Persistent_data_structure а также http://www.toves.org/books/persist/#s2 — или веб-поиск на условиях из этих. Я думаю, что вы могли бы сделать это с постоянным деревом, листья которого несут короткие последовательности.