Какой лучший способ хранить текст для текстового процессора?
Обычный способ — хранить символы в строке, но поскольку при написании текста пользователь часто удаляет или добавляет символы в середине текста, возможно, лучше использовать std::list<char> Чтобы содержать символы, то добавление символов в середине списка не является дорогостоящей операцией.
Решение
Следующая статья суммирует структуры данных, используемые в текстовых процессорах: http://www.cs.unm.edu/~crowley/papers/sds.pdf
Структуры данных для текстовых последовательностей.
Чарльз Кроули, Университет Нью-Мексико, 1998Структура данных, используемая для поддержания последовательности символов, является
важная часть текстового редактора. Эта статья исследует и оценивает
диапазон возможных структур данных для текстовых последовательностей. ADT
рассматривается интерфейс к текстовой последовательности компонента текстового редактора.
Шесть общих структур данных последовательности (массив, пробел, список, указатели строк,
буферы фиксированного размера и таблицы деталей), а затем общие
модель структуры данных последовательности, которая охватывает все шесть структур
представлена. Метод штучных таблиц объясняется подробно и его
преимущества представлены. Пространство проектирования последовательностей структур данных
рассматривается и несколько вариантов из перечисленных выше
представил. Эти структуры данных последовательности сравниваются экспериментально
и оценивается на основе ряда критериев. Экспериментальный
сравнение выполняется путем реализации каждой структуры данных в редактировании
симулятор и тестирование его с использованием синтетической нагрузки многих тысяч
редактирует. Мы также сообщаем об экспериментах на чувствительность результатов
к изменениям параметров, используемых для генерации синтетического редактирования
нагрузки.
Другие решения
Первая обработка текста делает гораздо больше, чем манипуляции со строками. Вам понадобится расширенная текстовая структура данных. Если вам нужна нумерация страниц, вам также понадобятся некоторые метаданные, такие как настройка страницы. Проведите исследование Word, у вас будет ответ.
В части расширенного текста ваша структура данных должна сохранять две вещи: символы и атрибуты. Другими словами, у вас должен быть какой-то язык разметки. HTML / DOM — это выбор. Но в большинстве случаев это излишне из-за сложности.
Существует множество структур данных, способных обрабатывать символьную часть: веревка, буфер разрыва и таблица фигур. Но ни один из них не обеспечивает поддержку атрибутов напрямую. Вы должны построить это самостоятельно.
AbiWord ранее использовал Piece Table на основе списка, но теперь теперь использует Piece Table на основе дерева. Перейти на вики-страницу AbiWord вы найдете больше.
OpenOffice используют по-другому. По сути, он хранит список абзаца, а внутри абзаца — строку (или другую более эффективную структуру данных) и список атрибутов. Я предпочитаю этот способ, потому что Paragraph — достаточно маленькая единица для редактирования, это намного проще, чем таблица фигур на основе дерева.
SGI STL имеет класс Rope, вы можете проверить его:
http://www.sgi.com/tech/stl/Rope.html
С помощью std::list<char> потребует примерно в девять раз больше памяти на символ, чем при использовании std::string, Это, вероятно, не очень хороший компромисс. Мое первое желание было бы использовать std::vector<std::string>где каждый string Объект содержит текст абзаца. Вставки и удаления внутри абзаца будут достаточно быстрыми.