Rope, Gap buffer, Piece table

[vak]

Набрёл на полезные структуры данных, которые не встретишь в учебниках.

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

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

Comments

[ex0_planet]

Еще докину

* Timer wheel :: раз два
* Skip list
* Interval map

[lxe]

Skip list популяризовал (канонизировав в Java CC) Doug Lea.

Интервальное отображение, кажется, идиоматический велосипед.

[ex0_planet]

Велосипед, да, причём эталонный. Я про него узнал из каких-то дискуссий про тестовые задачи на собеседованиях -- его любят давать чтобы кандидаты пообламывались.

[kondybas]

Скиплист прикольная штука, я в конце девяностіх делал реализацию для двунаправленного обхода с неуникальніми єлементами. В памяти он оч.ок, но на диске его реализовівать... так себе удовольствие.

[lxe]

А память все равно свопится на диск.)
Для локальности доступа, да, есть другие структуры.

[lxe]

И тогда уж, к списку с пропусками, — его генерализация вектором предикатов:
https://github.com/Microsoft/Adaptable

[lxe]

Vantage point tree — сбалансированное бинарное дерево для поиска по близости в многомерном метрическом пространстве.

http://pnylab.com/pny/papers/vptree/main.html
http://pnylab.com/pny/papers/vptree/vptree.pdf

(Есть еще вариант с делением плоскими медианными сечениями, но я забыл аббревиатуру.)

[spamsink]

std::rope была в ранних вариантах STL, но в стандарт не вошла, к сожалению. Я ею однажды для чего-то пользовался много лет назад.