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

Question

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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