Проблема с реализацией структуры данных веревки в C ++

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

Если у измененного узла refcount 1 (никто другой на него не ссылается), вам не нужно его дублировать.

Практическая проблема с этим - полезно отделить мутацию от операций без мутации:

    char& rope::operator[] (std::string::pos)

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

Этот подход был опробован для ранних реализаций std::string (где строка эквивалентна одноузловой веревке) iirc, и он потерял популярность; частично из-за проблемы мутации, а частично из-за того, что COW и требуемый реф-счет становятся все более дорогостоящими, если вам приходится беспокоиться о многопоточности.

Как вы говорите, у веревки возникает дополнительная проблема, если ваш узел содержит два независимых типа состояния: свою собственную строку и ссылки на его дочерние узлы (поскольку это приводит к тому, что мутации ссылки refcount / child будут распространяться вверх по дереву).

Если вместо этого символы хранятся только в конечных узлах, и вы делаете полную копию нелистовых узлов (так что каждая веревка имеет свою собственную «структуру каталогов»), вы все равно избегаете копирования символов, а пересчитанное общее состояние намного проще.

Получится ли это конкатенация логарифмического времени, которую вы хотите? Возможно нет:

• вам нужно скопировать все узлы, не являющиеся листами (и добавить новый корень), и их количество - это количество листьев
• вы также должны увеличивать количество ссылок на листах, что является линейным

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

Без этого, однако, вы получите быстрые конкатенации, но произвольные обращения к символам могут (непредсказуемо) вырождаться до логарифмического времени, если им придется распространять операцию COW вверх по дереву.

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

Однако на практике это включает выделение кучи (почти?) Для каждой модификации строк.

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

У Андрея Александреску есть отличный пример распределителя памяти малых блоков в своей книге «Современный дизайн C ++».