Смотрю, эта тема тут иногда поднимается. Вот и у меня вопрос.
Допустим, есть список строк. На этом списке выполняются операции редактирования строки, вставки строки и удаления строки.
Список, скажем, обычный С++'овский std::list.
Нужно сделать систему undo/redo для этого списка.
Первое, что пришло в голову: в UndoStack закладываем объекты, содержащие информацию о действии (редактирование/вставка/удаление), номер строки в списке и если нужно — данные, т.е. предыдущее состояние строки (перед редактированием или удалением).
Сохраняется именно номер в списке, а не указатель/итератор, потому что при удалении объект удаляется, и указатель/итератор становится недействительным.
Способ вроде хороший, но недостаток — для поиска места восстановления по номеру нужно O(n) времени.
Второй вариант — ничего не удалять, а просто помечать строку как удаленную. В этом случае в стеке можно хранить непосредственно указатели/итераторы; список будет фактически только увеличиваться и никогда не уменьшаться (до тех пор пока пользователь не закроет окно с редактируемой информацией). Время доступа становится O(1), но вот сам способ становится каким-то мудреным; при итерациях по списку нужно учитывать что некоторые объекты помечены как удаленные; т.е. операции "переход к следующей строке" и "переход к предыдущей строке" превращаются в циклы поиска; где-то нужно учитывать этот признак, а где-то — не нужно.
