Используется эффективный поиск буфера со стеком модификаций данных

Question

Я пытаюсь написать библиотеку C++ 11 как часть более широкого проекта, реализующего стек изменений (модификация, вставка и удаление), реализованный поверх оригинала буфер. Затем цель состоит в том, чтобы иметь возможность быстро просматривать «изменения» и получать измененные данные.

Мой текущий подход:

• Поддерживать упорядоченный список изменений, упорядоченных по смещению начала изменения
• поддерживать также стек одних и тех же изменений, так что они могут быть свернуты в заказать
• Новые изменения в стек и вставляется в список в нужном месте
• могут быть изменены изменения-по-смещения списка, если изменение взаимодействует с другими
  • Например, модификация байтов 5-10 отменяет начало более ранней модификации от 8-12
  • Кроме того, изменения вставки или удаления изменят кажущееся смещение данных, происходящих после них (удаление байтов 5-10 означает что то, что раньше было байтом 20, теперь найдено в 15)
• Чтобы найти измененные данные, вы можете просмотреть список применяемых изменений (и смещение в пределах этого изменения - другое изменение может иметь недействительными некоторые из них) или найти правильное смещение в исходных данных, если изменения не коснулись этого смещения
  • Цель состоит в том, чтобы быстро выполнить поиск - добавление изменений может потребовать некоторых усилий, чтобы запутаться со списком, но позже просмотры, которые значительно превысят изменения, в упорядоченном списке должны быть довольно простыми.
  • Кроме того, вы не должны постоянно копировать данные - данные каждого изменения в хранится вместе с ним, а исходные данные нетронутым
• Undo затем реализуется выскакивают последнее изменение из стека и отбрасывания любой изменения, внесенные в него добавлением этого изменения.

Это, кажется, довольно сложная задача - есть много вещей, о которых нужно позаботиться, и я быстро накапливаю сложный код!

Я уверен, что это должно быть проблемой, которая была рассмотрена в другом программном обеспечении, но оглядываясь на различные шестнадцатеричные редакторы и т. Д., Не указала мне на полезную реализацию. Есть ли название для этой проблемы («data undo stack» и друзья не получили меня очень далеко!) Или библиотеку, которая может использоваться, даже как ссылка, для такого рода вещей?

Answer 1

Я считаю, что наиболее распространенный подход (один из которых я успешно использовал в прошлом) - это просто сохранить исходное состояние, а затем поместить каждую операцию изменения (что делается + аргументы) в стек отмены. Затем, чтобы перейти в определенное предварительное состояние, вы начинаете с оригинала и применяете все изменения, кроме тех, которые хотите отменить.

Это намного проще реализовать, чем пытаться определить, какие части данных были изменены, и работает хорошо, если сами операции не занимают много времени (и, следовательно, замедляют «воспроизведение» в исходное состояние).

Answer 2

Я бы посмотрел на постоянные структуры данных, такие как https://en.wikipedia.org/wiki/Persistent_data_structure и http://www.toves.org/books/persist/#s2 - или перейдите по ссылке с этих терминов.Я думаю, вы могли бы сделать это с постоянным деревом, листья которого несут короткие строки.