Смотрю, эта тема тут иногда поднимается. Вот и у меня вопрос.
Допустим, есть список строк. На этом списке выполняются операции редактирования строки, вставки строки и удаления строки.
Список, скажем, обычный С++'овский std::list.
Нужно сделать систему undo/redo для этого списка.

Первое, что пришло в голову: в UndoStack закладываем объекты, содержащие информацию о действии (редактирование/вставка/удаление), номер строки в списке и если нужно — данные, т.е. предыдущее состояние строки (перед редактированием или удалением).
Сохраняется именно номер в списке, а не указатель/итератор, потому что при удалении объект удаляется, и указатель/итератор становится недействительным.
Способ вроде хороший, но недостаток — для поиска места восстановления по номеру нужно O(n) времени.

Второй вариант — ничего не удалять, а просто помечать строку как удаленную. В этом случае в стеке можно хранить непосредственно указатели/итераторы; список будет фактически только увеличиваться и никогда не уменьшаться (до тех пор пока пользователь не закроет окно с редактируемой информацией). Время доступа становится O(1), но вот сам способ становится каким-то мудреным; при итерациях по списку нужно учитывать что некоторые объекты помечены как удаленные; т.е. операции "переход к следующей строке" и "переход к предыдущей строке" превращаются в циклы поиска; где-то нужно учитывать этот признак, а где-то — не нужно.

Как бы вы сделали?

Здравствуйте, include2h, Вы писали:

I>Смотрю, эта тема тут иногда поднимается. Вот и у меня вопрос.
I>Допустим, есть список строк. На этом списке выполняются операции редактирования строки, вставки строки и удаления строки.
I>Список, скажем, обычный С++'овский std::list.
I>Нужно сделать систему undo/redo для этого списка.

I>Первое, что пришло в голову: в UndoStack закладываем объекты, содержащие информацию о действии (редактирование/вставка/удаление), номер строки в списке и если нужно — данные, т.е. предыдущее состояние строки (перед редактированием или удалением).
I>Сохраняется именно номер в списке, а не указатель/итератор, потому что при удалении объект удаляется, и указатель/итератор становится недействительным.
I>Способ вроде хороший, но недостаток — для поиска места восстановления по номеру нужно O(n) времени.

I>Второй вариант — ничего не удалять, а просто помечать строку как удаленную. В этом случае в стеке можно хранить непосредственно указатели/итераторы; список будет фактически только увеличиваться и никогда не уменьшаться (до тех пор пока пользователь не закроет окно с редактируемой информацией). Время доступа становится O(1), но вот сам способ становится каким-то мудреным; при итерациях по списку нужно учитывать что некоторые объекты помечены как удаленные; т.е. операции "переход к следующей строке" и "переход к предыдущей строке" превращаются в циклы поиска; где-то нужно учитывать этот признак, а где-то — не нужно.

I>Как бы вы сделали?

Есть ещё иммутабельные структуры данных. При изменении делать новую копию списка (по возможности с минимумом копирования). Ну и хранить, соответственно, ссылки на старые варианты. В случае со односторонним связным списком, например, при изменении копируются все узлы перед изменяющимся узлом, а хвост остаётся общим.

Можно замудрить связный список с версиями. Т.е. у узла хранится не просто ссылка на следующий узел, а множество пар (ссылка, версия). В итераторе хранится версия. При итерировании выбирается пара (ссылка, версия), такая, что версия максимальная но меньше или равна версии итератора. Это множество логично хранить в сбалансированном двоичном дереве поиска относительно версии. Получится абсолютный минимум копирований. Но какая-то нереально навороченная структура данных на мой взгляд с кучей накладных расходов.

Я бы тупо иммутабельные массивы сделал и копировал их туда-сюда, если речь идёт про размеры в килобайты. Процессор последовательную память копирует шустро.

Здравствуйте, vsb, Вы писали:

vsb>Есть ещё иммутабельные структуры данных. При изменении делать новую копию списка (по возможности с минимумом копирования). Ну и хранить, соответственно, ссылки на старые варианты. В случае со односторонним связным списком, например, при изменении копируются все узлы перед изменяющимся узлом, а хвост остаётся общим.

Ты что, это же страшно неэффективно! У него же там C++, а ты предлагаешь хранить не просто изменения, а старые объекты целиком.

Здравствуйте, include2h, Вы писали:

I>Способ вроде хороший, но недостаток — для поиска места восстановления по номеру нужно O(n) времени.

И что? Это редкая операция, пусть хоть O(e^n) будет.

I>Как бы вы сделали?

Инкапсулировал бы каждое действие в команду и хранил историю команд.

Здравствуйте, smallpoxlet, Вы писали:

S>Ты что, это же страшно неэффективно! У него же там C++, а ты предлагаешь хранить не просто изменения, а старые объекты целиком.

Хранить все целиком конечно неэффективно. Мне бы такое даже в голову не пришло бы Ну и конечно на самом деле там не просто "список строк", а нечто побольше.
Просто интересно, а в каких языках это было бы эффективно?

Здравствуйте, include2h, Вы писали:

I>Просто интересно, а в каких языках это было бы эффективно?

В тех, у которых современная функциональная библиотека для работы с коллекциями, например Scala или Haskell.

Здравствуйте, smallpoxlet, Вы писали:

S>Инкапсулировал бы каждое действие в команду и хранил историю команд.

Это само собой понятно. Просто к команде прилагаются некие данные, и вопрос был — как лучше хранить эти данные.
Сам я склоняюсь к первому варианту, так как он не затрагивает существующую в проекте архитектуру структур данных, и вообще достаточно прозрачен для реализации. Просто интересно было бы узнать мнения — как такое вообще делается.

Здравствуйте, include2h, Вы писали:

I>Это само собой понятно. Просто к команде прилагаются некие данные, и вопрос был — как лучше хранить эти данные.

В команде в виде diff'а, рядом с методами do/undo

I>Сам я склоняюсь к первому варианту, так как он не затрагивает существующую в проекте архитектуру структур данных, и вообще достаточно прозрачен для реализации. Просто интересно было бы узнать мнения — как такое вообще делается.

В GOF есть прекрасный разбор этого кейса.

Здравствуйте, include2h, Вы писали:

I>Здравствуйте, smallpoxlet, Вы писали:

S>>Инкапсулировал бы каждое действие в команду и хранил историю команд.

I>Это само собой понятно. Просто к команде прилагаются некие данные, и вопрос был — как лучше хранить эти данные.
I>Сам я склоняюсь к первому варианту, так как он не затрагивает существующую в проекте архитектуру структур данных, и вообще достаточно прозрачен для реализации. Просто интересно было бы узнать мнения — как такое вообще делается.

не озвучены требования по производительности, по памяти и тд, так что конкретные советы сложно давать.

У нас анду-реду для документов (документы сложные, excel'е подобные) через банальный стриминг делается.

Здравствуйте, include2h, Вы писали:

I>Смотрю, эта тема тут иногда поднимается. Вот и у меня вопрос.

Вот на хабре статейка Undo/Redo — Иллюзия простоты.