Роман Панов — Дерево смещений: работаем с динамически изменяемыми сегментированными массивами

Ближайшая конференция — C++ Russia 2025, 20—21 марта, Москва + online. Подробности и билеты: https://jrg.su/9Sszhd
— —
Скачать презентацию с сайта C++ Russia — https://jrg.su/aCyBLQ

Спикер рассказал про задачу, которую решал, и проблему, с которой столкнулся.

Есть большой список, например, история сообщений чата. Есть окно просмотра (viewport), в которое попадает лишь малая часть списка. Нужно рисовать только видимую часть — то, что попадает во viewport. Рисовать требуется часто, 30 раз в секунду, то есть нужно уметь быстро находить видимые элементы. Более того, сообщения могут редактироваться, а следовательно, менять свой размер и удаляться. Хуже того, есть анимация — сообщения плавно перемещаются по списку. Например, после удаления сообщения «хвост» плавно заполняет образовавшееся пространство. Другими словами, надо быть готовыми к тому, что геометрия списка меняется каждый кадр.

Он описал несколько «наивных» решений с использованием стандартных контейнеров. Объясню, почему они неэффективны. Представил эффективное решение с помощью так называемого дерева смещений (не путать с деревом отрезков — это другая структура данных).

Будет интересно тем, кто интересуется алгоритмами визуализации больших списков данных. Покажу реализацию дерева смещений на C++, как с помощью шаблонов сделать реализацию универсальной и настраиваемой.

Видео Роман Панов — Дерево смещений: работаем с динамически изменяемыми сегментированными массивами канала C++ Russia — Конференция по разработке на Cpp