Минимальная структура данных процессора и памяти для редактирования текста?

Question

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

Моя основная идея состоит в том, чтобы реализовать структуру типа веревочных / связанных списков, которая фрагментирует заметки во время редактирования, чтобы избежать перераспределения накладных расходов, если контейнер заполнен, и избежать выделения ненужного пространства, например, с динамически растущими векторами.

Однако слишком частое фрагментирование заметок неизбежно приведет к дополнительным затратам, поэтому во второй части моей реализации планируется преобразовать структуру веревки, используемую при редактировании заметки, в последовательную структуру данных для хранения и быстрого чтения.

Таким образом, в основном объекты хранятся и считываются из последовательной структуры данных, но при редактировании они копируются в фрагментированную структуру данных, а когда редактирование завершается, объект конвертируется обратно.

Это хорошая идея? Если нет, то рекомендации приветствуются. В любом случае, кто-нибудь знает о некоторых подобных реализациях с открытым исходным кодом, из которых я могу поучиться?

Answer 1

Что касается открытого исходного кода, всегда есть emacs:-). Но я подозреваю, что вы ищете что-то немного проще.

Здесь нет ни одного правильного ответа. Традиционная реализация, которую я видел, использует один очень большой буфер (std::vector<char> сегодня), разделен на три логических блока: текст перед курсором, свободное место и текст после курсора. При таком решении перемещение курсора влечет за собой смещение текста, по которому перемещается курсор, но вставка и удаление текста в курсоре не требует каких-либо сдвигов.

Я не уверен, что традиционный подход сегодня оправдан (хотя, может быть, на встроенной машине). Я бы начал с использованияstd::vector<char> очень наивным способом, и только меняя это, я получал данные профилирования из типичных сеансов редактирования. Я бы обернул его, однако, в Buffer класс, предоставляя только нужный мне интерфейс, чтобы упростить будущую миграцию на другую стратегию.

Answer 2

Это зависит от объема текста, который вы планируете редактировать. Предложенный предыдущий ответ std::vector<char> который работает до предела.

Вы просили предложения: я узнал у Scintilla тонну, особенно связанную с ней, при реализации редактора Wiki.