vak: (Default)
Serge Vakulenko ([personal profile] vak) wrote2024-03-30 12:07 am

Rope, Gap buffer, Piece table

Набрёл на полезные структуры данных, которые не встретишь в учебниках.
  • Строп - хранит длинную строку в виде дерева, состоящего из небольших подстрок.
  • Буферное окно - динамический массив, позволяющий эффективную вставку и удаление элемента в некоторой области.
  • Таблица фрагментов - представление текстового документа, редактируемого в текстовом редакторе.

Редактор Руднева, а точнее RAND Editor, лежащий в его основе, построен как раз на таблице фрагментов. Был бы интересный челлендж: вытащить из тех исходников реализацию таблицы фрагментов и переписать на современный Си++ или Rust.


Post a comment in response:

This account has disabled anonymous posting.
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting

If you are unable to use this captcha for any reason, please contact us by email at support@dreamwidth.org