Undo/Redo — Иллюзия простоты

    Такая простая и привычная функция в любом текстовом и графическом редакторе. Казалось бы, какие могут быть сложности с её реализацией? Впервые столкнувшись с разработкой Undo/Redo для текстового редактора XtraRichEdit, мы задумались, а какой же подход нам избрать?



    Было очевидно, что должен существовать некий объект, отвечающий за историю изменений. В этом объекте должен храниться список элементов, представляющих собой отдельные действия. Каждый такой элемент должен хранить достаточно информации чтобы откатить действие (Undo), а также повторить его (Redo).

    Поскольку действия могут быть самыми разными (вставка текста, изменение шрифта, добавление красной строки в параграф), мы сразу решили, что элементы буфера Undo будут не только хранить все необходимые данные для отката/повтора операции, но и будут сами ответственны за выполнение отката и повтора:

    public abstract class HistoryItem {
        public abstract void Undo(Document document);
        public abstract void Redo(Document document);
    }

    Первый прототип класса для буфера Undo выглядел следующим образом:

    public class History {
        readonly List<HistoryItem> items = new List<HistoryItem>();
    
        public History(Document document) {
            this.document = document;
        }
    
        public void Undo() {
        }
        public void Redo() {
        }
        public void Add(HistoryItem item) {
            items.Add(item);
        }
    }

    Руки так и тянутся написать метод Undo:

    public void Undo() {
        items[items.Count - 1].Undo(document);
    }

    Лаконично, изящно… но совершенно неправильно.

    Для начала, при попытке вызвать метод Undo при пустом списке, вылетит исключение. Исправляем:

    public bool CanUndo { get { return items.Count > 0; } }
    public void Undo() {
        if (!CanUndo)
            return;
        items[items.Count - 1].Undo(document);
    }

    И вновь получаем неправильный код. Ведь если вызвать метод Undo несколько раз подряд, то будет раз за разом вызываться Undo для последнего элемента в списке, что неправильно. Вносим изменения:

    public void Undo() {
        if (!CanUndo)
            return;
        items[items.Count - 1].Undo(document);
        items.RemoveAt(items.Count - 1);
    }

    Вот теперь всё хорошо. Что-ж, пора приниматься за Redo. Ничего сложного…

    public void Redo() {
        if (!CanRedo)
            return;
        // ???
    }

    Oops! Приехали.
    В нашей реализации Undo мы в процессе отката безвозвратно теряем откатанные элементы, поэтому делать Redo просто некому. Придется завести индекс, указывающий на текущий элемент в буфере обмена. Итак:

    int currentIndex = -1;
    public bool CanUndo { get { return currentIndex >= 0; } }
    public bool CanRedo { get { return items.Count > 0 && currentIndex < items.Count - 1; } }
    
    public void Undo() {
        if (!CanUndo)
            return;
        items[currentIndex].Undo(document);
        this.currentIndex--;
    }
    
    public void Redo() {
        if (!CanRedo)
            return;
        this.currentIndex++;
        items[currentIndex].Redo(document);
    }
    
    public void Add(HistoryItem item) {
        items.Add(item);
        this.currentIndex++;
    }

    Уже лучше, по крайней мере похоже на что-то работоспособное. Обратите внимание, что в случае Undo индекс изменяется после отката, а в случае Redo — до наката. Мы также не забыли инкрементировать индекс при добавлении элемента в историю.

    А теперь давайте посмотрим внимательно на метод Add и зададимся вопросом, как он будет себя вести в случае, если мы выполнили и записали в историю 5 действий, затем откатили 3 из них и собираемся выполнить новое действие? Поразмыслив и посмотрев как сделано у других (всё уже украдено до нас) приходим к выводу, что в таком случае та часть истории действий, что находится после текущего индекса, должна быть потеряна, а вместо неё начнут записываться новые действия:

    public void Add(HistoryItem item) {
        CutOffHistory();
        items.Add(item);
        this.currentIndex++;
    }
    
    void CutOffHistory() {
        int index = currentIndex + 1;
        if (index < Count)
            items.RemoveRange(index, Count - index);
    }

    Вот теперь, наконец, простейшая реализация Undo/Redo стала работоспособной.

    Задумаемся, как мы будем её использовать. Первым делом в голову лезет такая последовательность действий:
    1. Выполняем действие;
    2. Заносим информацию об этом действии в буфер undo для дальнейшего отката/повтора.

    Но ведь еще в самом начале мы решили, что элементы undo-буфера способны не только хранить необходимые данные, но и самостоятельно выполнять нужные операции по откату/повтору. А что такое повтор операции? Это и есть её прямое выполнение из текущего состояния. Т.е. чтобы выполнить любую операцию, можно делать так:
    1. Создаем элемент буфера undo, и заносим его в буфер undo для дальнейшего отката/повтора;
    2. Выполняем Redo для этого элемента:

    void DoAction() {
        HistoryItem item = CreateActionHistoryItem();
        document.History.Add(item);
        item.Redo(document);
    }

    Получилось элегантно и красиво. Первое выполнение действия — это Redo этого действия из текущего состояния. Откат — Undo из текущего состояния. Повтор — вновь выполнение операции из текущего на тот момент состояния.

    В последних фразах мы несколько раз употребили слово состояние. Дело в том, что та информация, которая сохраняется в буфере undo, является вполне корректной в момент сохранения. Однако уже в следующий момент она может стать некорректной. Простейший пример. У нас есть текст «Hello World!».



    Мы выполняем операцию вставки текста « DevExpress » перед словом «World». При этом в буфер undo мы поместим информацию о том, что в позицию с индексом 6 (считаем с 0) был вставлен текст « DevExpress».



    Выполним следующее действие: вставим в начало текста строку «We say: ». Разумеется после этого действия информация о позиции, куда надо вставить строку « DevExpress» станет некорректной.



    Если в этот момент вызвать Undo для первой операции, то содержимое документа будет испорчено. Чтобы информация стала корректной, необходимо произвести перерасчёт.

    А можно ли в каком-то случае обойтись без перерасчёта? Безусловно, можно, если предположить, что откат каждой операции приводит документ ровно в то состояние, которое он имел на момент выполнения операции. Аналогичное требование следует наложить и на повтор операции.

    В этом получается, что информация в буфере undo автоматически «становится» корректной, как только документ приходит в то исходное состояние, в котором эта информация была сохранена. Если же состояние отлично от исходного, то эта информация в общем случае некорректна и использовать её нельзя. А поскольку откат операций происходит в порядке, обратном их выполнению, то мы никогда не сможем воспользоваться информацией до того, как документ будет приведён в исходное состояние.

    Вот примерно какими соображениями можно пользоваться при реализации простенького Undo/Redo менеджера для собственного текстового или графического редактора. Однако, в жизни всё бывает несколько иначе, о чём мы поведаем вам в следующей статье.

    А вот ссылка на крайнюю статью на эту же тему.

    PS:
    В процессе написания этой статьи мы заинтересовались, а когда же появилась такая полезная вещь как Undo?

    Старательно погуглив, пришли к выводу, что это произошло где-то в период с 1971 по 1976 годы. Так, современные мануалы по редактору ed, утверждают, что в нём поддерживается undo. Однако, в мануале от первого юникса за 1971 год упоминания об Undo ещё нет. А вот в редакторе vi, первая версия которого вышла в 1976 году Undo похоже было изначально.

    Сам термин undo был упомянут, возможно впервые, также в 1976 году: “It would be quite useful, to permit users to ‘take back’ at least the immediately preceding command (by issuing some special ‘undo’ command).” (Lance A. Miller and John C. Thomas of I.B.M., “Behavioral Issues in the Use of Interactive Systems.”) (см. статью в NY Times Magazine, 5-й абзац).
    Developer Soft
    88,00
    Компания
    Поделиться публикацией

    Похожие публикации

    Комментарии 86

      +8
      Опечатка:

      public void Undo() {
      if (!CanRedo)
      return;
      items[items.Count — 1].Undo(document);
      items.RemoveAt(items.Count — 1);
      }

      Кроме того:
      У вас нарушена искапсуляция. List и currentIndex надо бы объединить в объект ActionHistortyStorage, так как их независимосе изменение может нарушить целостность данных. Но ещё лучше вместо List и currentIndex использовать два Stack.
        +3
        Спасибки, поправил.
        Насчет инкапсуляции, это все же пример, а не боевой код.
          +1
          Полагаю, что в примере можно забивать на исключительные ситуации, но не инкапсуляцию. Особенно если пример на выбор хорошего решения.
        +3
        Инкапсуляция, не инкапсуляция, скриншот зацените. Красиво — же… Прям как новый твиттер!
          –2
          ужасное меню.
          // да-да, я понимаю откуда такой подход… но все равно ужасное. и неэкономное по площади.
            0
            Нормальное тоже есть. А риббон, он сам по себе на любителя, да и не для каждого приложения подходит в принципе.
              +2
              При большом количестве пунктов меню и грамотном подходе к их организации — риббон становится очень удобен ;-)
            +24
              +1
              В книжке Reusable Software Design Patterns в качестве примера этого шаблона как раз приводится операция Undo в текстовом редакторе.
                0
                Четкое понимание и пути решения проблем данного вопроса хорошо описаны в книге Алана Купера «Об интерфейсе».
                +1
                Undo-redo — это частный случай реализации системы контроля версий. Если плясать от этого, то всё становится немного понятнее.
                  +1
                  Кстати да, задачки родственные.
                    +1
                    Более того, если смотреть с этого угла — то открываются широкие возможности в улучшении «стандартной» реализации. Например можно сделать бранчинг, можно хранить историю версий на диске, можно сделать синхронизацию.
                      0
                      Тут уже все зависит от поставленной задачи. Многим приложениям (и многим пользователям) такой навороченный инструмент не нужен. Не знаю, к сожалению или к счастью.
                        0
                        Многим да. Но вот в редакторах кода мне очень не хватает локального контроля версий, встроенного прямо в редактор, доступного по кнопкам undo-redo.

                        В простых текстовых редакторах это наверное не нужно, а вот сохранение истории правок на диск (тоже фича из VCS) — это нужно мне практически всегда.
                          0
                          В ворде track changes для этого сделали. До тех пор, пока дело не доходит до серьезных изменений в таблицах даже работает адекватно. А вот мы у себя ещё не сподобились реализовать.
                            +1
                            В vim'e, кстати, есть дерево изменений с возможностью перескакивать с ветки на ветку. И сохранение истории правок на диск тоже вроде появилась.
                              +1
                              Local History есть у Eclipse и у NetBeans — изменения сохраняются на диск, можно просмотреть историю изменений, откатиться. Веток, вроде нет.
                              0
                              В графических редакторах такой инструмент (с бранчами, и возможностью сохранения истории на диск для последующего пользования) был бы просто незаменим.
                                0
                                Насколько я помню в фотошопе частично это есть.
                                Но я никогда не пользовался, так что не могу ручаться.
                              +2
                              Майкрософт в ворде в свое время баловался в ворде быстрым сохранением. Суть как раз и была в том, что в конец исходного документа писались изменения, доводящие документ до нужного результата. Но как-то не прижилось.
                              С бранчингом они заморачиваться не стали. Впрочем в текстовом редакторе это нечасто бывает нужно, а геммороя в реализации там вагон и маленькая тележка.
                          0
                          Если выполнение действия не удалось по какой-либо причине, последний элемент листа придется удалять. Логичнее было бы сначала попытаться выполнить а в случае успеха уже добавлять в лист.
                            +1
                            Поразмыслив и посмотрев как сделано у других (всё уже украдено до нас) приходим к выводу, что в таком случае та часть истории действий, что находится после текущего индекса, должна быть потеряна

                            Порой это очень раздражает. Бывает, что хочется откатить процесс отката и изменения. В Фотошопе это сделано лучше всего — там отображается история действий.
                              0
                              Тогда это уже multibranch undo получается. А там все очень не просто с сохранением состояния в местах, где идет ветвление истории, да и сделать нормальный UI для такого Undo/Redo нетривиально.
                              +9
                              Чтобы поддерживать операции Undo & Redo сначала нужно представить «документ» в виде набора объектов и определить атомарные операции над над ними. Затем для каждой такой операции разработать обратную ей (это можно сделать не всегда).
                              Невозможно обсуждать реализацию Undo & Redo, отдельно от типа документа и набора операций над ним.

                              Допустим мы делаем вставку изображения в графическом редакторе по верх уже имеющегося, где «документ» представлен просто цельным изображением. Тогда при исполнении операции «вставка» нужно скопировать в буффер/запомнить ту часть изображения, которая была на этом месте. Если делать любую операцию, которая затрагивает весь документ (например размытие), придется хранить в history все старое изображение целиком. Расход памяти при этом так велик, что вам придется отказаться либо от данной структуры документа поддержки либо от поддержки операции Undo.

                              При нажатии Undo, возможно, нужно будет откатить парочку транзакций в локальной базе данных. Ваша модель к этому готова?
                              В вашем примере есть две функции CreateActionHistoryItem() & item.Redo(Document document). 90% времени вы проведете пытаясь написать их нормальную реализацию в любом реальном проекте.
                                +1
                                Как в развитие поднятой Вами темы мы продолжение написали. Опубликуем скоро.
                                  +1
                                  С нетерпением жду продолжения… не затягивайте с публикацией :)
                                +3
                                А если добавить в список возможных операций перемещение по документу с выделениями, и объединением таких перемещений в одну операцию, то вобщем-то проблема легко решается. Кстати, многие редакторы так и делают — это заметно когда на Undo они просто перемещают курсор в старую позицию или возвращают выделение. Более серьезные вопросы возникают, когда программа имеет многодокументный интерфейс. Иметь ли Undo на все документы или на каждый? Включать ли в историю переключение между документами. Ответы зависят от задачи. Тут же еще могут возникнуть и другие задачи, когда редактирование одного текстового документа лишь часть сложного use case. Выделять ли редактирование документа в отдельный undo-список или вносить в общую кучу. Вобщем — да, задача Undo — не самая тривиальная область программирования интерфейса.
                                  0
                                  Вспомнил нашу реализацию Undo/Redo. «Склеивание операций» используется довольно часто. Даже если мы печатаем текст, то не каждую же букву Undo-шить? А т.к. я думаю ваши классы вы будете использовать и в своих других проектах, то стоит эту возможность включить в прототип.
                                    +1
                                    С текстом да, в некоторых случаях можно подпатчивать последний элемент в буфере Undo, чтобы не добавлять туда лишнего. Мы не смогли (впрочем и не стояло такой задачи) затащить этот функционал именно в UndoManager, у нас на уровне редактирования модели решается, то ли новый элемент в Undo совать, то ли существующий править.
                                      0
                                      такая задача решается элементарно — делаемм снэпшоты с троттлинком миллисекунд в 200. то есть сохранение будет происходить между «сеансами ввода»
                                        0
                                        Ну какбы логичнее «засовывать» отдельные слова ;). А так «склеивать» нужно не только с текстом. Например может имеет смысл «склеивать» в векторном редакторе перетаскивание элемента клавишами, может даже мышкой.
                                          0
                                          нет, засовывать надо то, что для пользователя является атомарным действием. для текста — это сессия ввода/удаления, вставка/вырезка, изменение атрубутов
                                            0
                                            Я иногда пишу в течении большого времени " не отходя от кассы ". Что в этом случае делать? Могу написать целый обзац не отрываясь. ВОт этот коммент например я пишу не отрываясь. Т.е. если я нажму сейчас анду, то получится весь коммент исчезнет. Надо как-то совместить чтоли эти два подхода, пока не знаю.
                                              0
                                              Написать большой кусок текста подряд без ошибок и не отрываясь, конечно можно, но чаще всё же в процессе то лишнюю буковку впишешь, то пропустишь чего. Приходится править. Любая такая правка атомарность разрывает. Начало нового абзаца также разрыв атомарности.
                                              Вообще на эту тему забавно было наблюдать за вордом со включенной автозаменой. Пишешь предложение из нескольких слов с маленькой буквы. Откатываешь. Откатывает все слова, кроме первого. Потом замену малой буквы на большую откатывает. И наконец первую букву в слове. Т.е. автозамена тоже атомарность разорвала, что в общем-то логично.
                                  +4
                                  О да, какая знакомая проблема. В моём случае всё еще куда более запущено. Я пишу редактор языка блочных диаграмм передаточных функций для программирования контроллеров. Редактор сделан на WPF и использованием популярного паттерна M-V-VM. Собственно проблем возникло много, особенности реализации класса UndoRedoJournal самые мелкие из них.
                                  Проблема №1 заключалась в том, что действия Undo/Redo не могли хранить ссылки на объекты модели, по тому что в ходе редактирования объекты удалялись из модели, а при необходимости откатить операцию удаления создавалась идентичная копия объекта. Пришлось ввести систему идентификации элементов, а в действиях отката вместо ссылок хранить идентификаторы.
                                  Проблема №2 более интересная. Она была вызвана солидным количеством возможных типов элементарных модификаций модели (микро-действий) — около сотни. Т.е. действий типа «добавить», «удалить», «изменить свойство» и т.д. При том многие конечные операции модификации (макро-действия) состояли из десятка элементарных, количество возможных вариаций групповых модификаций стремилось к критическому количеству. Поэтому подход «1 класс действия на 1 макро-действие » никак не канал. С другой же стороны, не канал и подход «1 класс действия на 1 микро-действие», т.к. код макро-действия раздувался до совершенно неимоверных размеров из-за необходимости оперировать микродействиями.
                                  И всё это усугублялось уже до совсем феерической сложности, тем отмеченным вами фактом, что следующая элементарная модификация должна была основываться на состоянии модели после выполнения предыдущей.
                                  В итоге я решил эту проблему фундаментальным образом, вывернув описанный вами в статье паттерн на изнанку.
                                  // Интерфейс транзакции модификации модели.
                                  public interface IModelEditTransaction : IDisposable
                                  {
                                      // Зафиксировать транзакцию.
                                      UndoRedoOperation Commit(UndoRedoJournal journal, string name);
                                  }
                                  
                                  //  Класс модели документа.
                                  public sealed class DocumentModel
                                  {
                                      // Открыть транзакцию редактирования модели.
                                      public IModelEditTransaction BeginEdit() 
                                      { 
                                          //...
                                      }
                                     
                                      // Изменить что-то.
                                      public void ChangeXXX()
                                      {
                                          if (!IsEditing) throw new InvalidOperationException();
                                          ProcessChangeXXX();
                                      }
                                  }
                                  
                                  Код примерный, не надо указывать на опечатки.
                                  В саму модель я добавил функциональность транзактивной модификации, все изменения вносятся в модель в рамках транзакции. Код просто открывает транзакцию и изменяет состояние модели как хочет. При этом последовательность элементарных изменений автоматически «режется» кодом обработки изменений на действия отката с некоторой оптимизацией.
                                  Гипотетический код, изменяющий модель выглядит так:
                                  void EditModel(DocumentModel model, UndoRedoJournal journal)
                                  {
                                      using (IModelEditTransaction tran = model.BeginEdit())
                                     {
                                          model.ChangeXXX();
                                          tran.Commit(journal, "Поменяли XXX").
                                     }
                                  }
                                    +1
                                    Вполно разумно сделано.

                                    Но мы пошли по пути минимизации количества хранимых данных для каждого микродействия в вашей терминологии. Для этого пришлось переосмыслить строение внутренних структур данных. Зато когда переосмыслили, огромная куча микродействий как у Вас свелась к одному единственному базовому классу. Итого различных микродействий стало порядка десятка.

                                    Кстати хранить ссылки на «живые» объекты иногда вполне допустимо, хотя мы вначале тоже от этого шарахались.
                                      +2
                                      Да, на счет ссылок я долго думал, но решил что проще всего от них отказаться. Реализация команды «Обновить» при хранении ссылок превращалась в настоящий кошмар, да и много чего еще усложнялось. Ссылки в действиях вполне допустимо хранить на неизменяетмые (immutable) объекты. А у меня «живое» почти всё.
                                      +1

                                      Это что бы было ясно о чем речь.
                                      0
                                      Точно так же работают стандартный IDesignerHost и DesignerTransaction.

                                      Только текст транзакции задается вначале. UndoRedoService подписывается на события IComponentChangeService для регистрации изменений.

                                      –7
                                      это .NET?
                                      разве там нету Undo/Redo framework`а?
                                        0
                                        хвост феи?
                                          +3
                                          Tail != Tale.
                                          +2
                                          Мне давали как раз такую задачку (undo/redo для текстового редактора) на одном из собеседований для решения в уме (без компьютера и даже без бумажки).

                                          Если честно, то довольно странно читать «Если сделаем вот так, то получим исключение, поэтому делаем вот так. И опять неправильно, потому что будет вызываться одно и то же, поэтому делаем вот так. И опять неправильно....»
                                            +1
                                            надо же из чего-то статью высосать ;-)
                                              +1
                                              Согласен, мне было не приятно читать статью в которой человек пишет заведомо кривой код, потом торжественно объясняет почему он кривой, исправляет… Но опять неверно. Почему нельзя сразу и правильно?!
                                                +1
                                                >Почему нельзя сразу и правильно?!

                                                Как правильно заметили выше, потому что в этом случае не получилось бы статьи. Ну сами подумайте: какая может быть статья, если бы автор написал «мы реализовали механизм undo/redo вот так-то» — и один листинг в 30-40 строк? Ну, реализовали, ну молодцы. Вот только задачи подобного уровня решаются тысячами программистов ежедневно, и ничего экстраординарного в ней нет. А тут и статья, и заодно ненавязчивая ссылка на проект.

                                                Вот только проиллюстрированный подход к разработке у меня очень, очень плохо увязывается с ценой продукта по ссылке. Нет-нет, я ни в коем случае не «считаю чужие деньги» и не «учу никого вести бизнес» — просто озвучиваю своё собственное впечатление от прочитанного и увиденного. Не более.
                                                  –1
                                                  А вы зануда
                                                    0
                                                    Спасибо, я в курсе.
                                              +1
                                              Не мучайтесь, gof всё придумали за вас.
                                                –9
                                                Как же я рад, что пишу под Мак и мне не приходится выдумывать велосипед.
                                                  +4
                                                  А под Мак подобные компоненты рождаются из вулканического пепла, что ли? Нет, товарищ, представьте себе: их тоже кто-то пишет. И в них тоже реализован обсуждаемый механизм. Схожим (или не очень) образом.
                                                  Поэтому Ваша ремарка немного (хотя лучше сказать совершенно) не в кассу.
                                                    –1
                                                    Написать свой NSUndoManager — задача 10 минут используя Objective-C, но этого не требуется — всё есть. Допустим есть метод addObject и обратный к нему — removeObject, тогда первая строка метода addObject будет выглядеть так:
                                                    [[_undoManager prepareWithInvocationTarget:self] removeObject:object];
                                                    И первая строка метода removeObject:
                                                    [[_undoManager prepareWithInvocationTarget:self] addObject:object];
                                                    Готово!
                                                    За что минуса?
                                                      +1
                                                      Написать свой Undo/Redo Manager — «задача 10 минут» используя любой высокоуровневый язык (и об этом я, кстати, сказал где-то тут). Не вижу никакой «эксклюзивности» Мака в этой ситуации.
                                                      И уж тем более не вижу эксклюзивности в случае «не пишем сами, а используем готовые решения» — их есть у нас под любыми системами в достатке.
                                                        0
                                                        Видимо за то, что вы весело ворвались в тред для разработчиков .NET с комментарием «А я пишу под Мак а вы все умственно отсталые» ;)
                                                      0
                                                      А что, функционал Undo/Redo для произвольных объектов под Мак поддерживается уже на уровне операционной системы?
                                                        –2
                                                        Что Вы имеете в виду «на уровне операционной системы»?
                                                        На уровне фреймворков, которые идут вместе с системой — да. Конечно же можно писать код под мак и не используя вшитый в систему Cocoa, но зачем?
                                                      0
                                                      Я бы использовал двунаправленный список, ссылка на начало, ссылка на текущий HistoryItem. Итерация быстрее, «хвост отбрасывать» быстрее, навигация вперед — назад тоже. Ну и LOH не расходуется.
                                                        0
                                                        Сейчас Вам опять скажут «ну это же не боевой код, а всего лишь пример» ;)
                                                          0
                                                          Нет, сейчас неработающую фигню принято называть прототипом.
                                                          +1
                                                          Это-ж сколько элементов надо будет сунуть в List чтобы он в LOH лёг? От 10-20 тысяч получается. Сдается мне документ всё же закроют раньше :)
                                                            0
                                                            Ну, LOH может и не станет проблемой, но вот разница между перемещением по массиву (и удалением элементов) по индексам супротив итеративного перемещения по двунаправленному списку (и «отбрасывания хвоста») будет весьма существенной во вполне реальных условиях более-менее продолжительной правки документа.
                                                              0
                                                              Перемещаться-то по массиву зачем? CurrentIndex есть, заинкрементить/задекрементить его недолго, а больше и не нужно ничего. Хвост обрезать тоже невелика беда, память-то выделять по-новой не надо, размер блока достаточно уменьшить. Вот когда массив растёт, realloc-и есть, но у List достаточно эффективный алгоритм внутри сидит, чтобы об этом не задумываться.
                                                              Да и в целом, менять подход есть смысл, когда профайлер покажет, что именно в данном месте есть проблема с производительностью. Если же брать то же текстовый редактор, то замеры кусков текста и отрисовка на многие порядки «тяжелее» любой модификации модели документа, не говоря уж об буфере undo.
                                                                0
                                                                Насчет профайлера — это все так.

                                                                Но использовать List везде, где только не лень — это бомба замедленного действия :)

                                                                Когда начнутся якобы беспричинные OutOfMemoryException-ы, припомните мой совет ;)

                                                                Совет не относится к конкретному случаю (не боевой код), просто вспомнилось.
                                                                  0
                                                                  >Перемещаться-то по массиву зачем? CurrentIndex есть, заинкрементить/задекрементить его недолго, а больше и не нужно ничего.

                                                                  После недолгого инкремента/декремента индекса наступает вполне себе долгая операция «получить элемент массива по этому индексу» — Вы об этом забыли?

                                                                  А в случае двунаправленного списка получение предыдущего/следующего элемента осуществляется одной очень быстрой операцией: переходом по ссылке на предыдущий/следующий объект, которая хранится в каждом элементе двунаправленного списка. Причём скорость этой операции остаётся неизменной для списков любой длины (в отличие от).
                                                                    +1
                                                                    Не пугайте меня. С каких пор конструкция pointer[index] стала работать кардинально медленнее, чем разыменовывание указателя (что суть *pointer или pointer[0]). И уж тем более как это от размера массива зависит?
                                                                    Или вы думаете, что в .NET List это и вправду однонаправленный список? Так неправда это, там обычный массив внутри.
                                                                      0
                                                                      Ну List делает проверку на попадание в используемую область массива. Плюс сам массив проверят доступ на безопасный диапазон.

                                                                      Хотя соглашусь, на современном железе — это уже непринципиально
                                                                        0
                                                                        Похоже мы друг друга поняли.

                                                                        С определённого момента стал следовать правилу: 1. make it work; 2. make it work right; 3. make it work fast. А когда слез с C++ и пересел на C# осознал, что лучшая оптимизация — эффективный алгоритм. Никакой ассемблер не заменит правильно организованных структур данных и BinarySearch.
                                                                          0
                                                                          >Хотя соглашусь, на современном железе — это уже непринципиально

                                                                          Да знаю я, знаю: я старый, упёртый ретроград, напрочь испорченный программированием под встраиваемые системы и мобильные девайсы :)
                                                                          0
                                                                          Так, стоп машина. Я с другой реализацией попутал (давно шарпа не касался, каюсь).

                                                                          Внутри, разумеется, обычный массив, и что касается скорости доступа Вы абсолютно правы. Однако, во-первых нас всё равно подстерегают прелести переаллокации (прозрачной и незаметной, но всё же). Ну либо резервирования массива «достаточного» размера, что тоже не фонтан. А второй момент касается не самого списка, а конкретной реализации в обсуждаемой статье: отбрасывание хвоста путём откусывания по одному элементу в цикле вместо list.RemoveRange() — хм…
                                                                          Да, я помню, что «это не боевой код, а всего лишь пример», но я не понимаю, зачем в «примере» использовать заведомо неоптимальное решение.
                                                                            0
                                                                            В такой формулировке с критикой полностью согласен. Поправим завтра поутру на RemoveRange.
                                                                        0
                                                                        В крайнем случае можно было бы использовать итераторы — те же яйца, вид в профиль. Но уж точно не числовые индексы.
                                                                          0
                                                                          Для интерфейса, возможно, понадобится BindableCollection :)

                                                                          Но это же уже ViewModel, так ведь? :)
                                                                            0
                                                                            BindableCollection [HistoryItem] (парсер л..)
                                                                      0
                                                                      На x64 по идее = массив поинтеров на 10K… А учитывая, что List растит массив каждый раз в два раза больше — то 5К записей.

                                                                      5К записей — это всегод лишь 2-3 страницы текста набрать. И это не учитывая опечатки, коррективы и т.д.

                                                                      Другое дело, что в 4 версии дотнета вроде бы LOH границу увеличили…
                                                                        0
                                                                        Насчёт LOH: объекты в списке могут быть разные. К примеру, если у нас не plain text, а ещё и стили/цвета/размеры/етц, то загреметь в LOH можно куда раньше, чем на 10-20 тысячах объектов.
                                                                          0
                                                                          нет.

                                                                          учитывается только сплошной размер объекта. на практике — это только массивы
                                                                            0
                                                                            Действительно. Спасибо за поправку.
                                                                              0
                                                                              Угу. Я на LOH налетал только со StringBuilder и то, когда туда строки мегабайт на 10-20 приходилось засовывать.
                                                                                0
                                                                                StringBuilder работает с байт-массивом, что в 4 раза дешевле объект-массива на x86 и в 8 раз дешевле на x64 ;)
                                                                                  +2
                                                                                  Тоже позанудствую чуток :) Таки с char-массивом, каждый char по 16 бит, ибо юникодные они в дотнете.
                                                                                    0
                                                                                    Точняк :)

                                                                                    (Безюникодовое Дельфийское Прошлое)
                                                                        0
                                                                        Вовсе необязательно так все разжевывать:

                                                                        public void Undo() {
                                                                        items[items.Count — 1].Undo(document);
                                                                        }

                                                                        Лаконично, изящно… но совершенно неправильно.

                                                                        Для начала, при попытке вызвать метод Undo при пустом списке, вылетит исключение. Исправляем:


                                                                        Вы же пишете статью, рассчитанную на аудиторию имеющую определенные профессиональные. А то получается что вы общаетесь с читателем как с воспитанником кружка лепки из пластилина для дошкольников. Или, как выше правильно заметили, просто нужно было растянуть 35-40 строк исходного кода на «годную» статью.

                                                                        ЗЫ Вы бы лучше сконцентрировали внимание на HistoryItem и записи сложных элементов в буфер истории. И рассказали о том, как вы это делаете, какие сложности. Вот это было бы действительно интересно.

                                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                        Самое читаемое