я пытаюсь сделатьверевка структура данных. Это'это тип двоичного дерева, то есть рекурсивная структура данных.

Назначение веревки состоит в том, что расщепление и конкатенация должны бытьбыстро, что значитВы избегаете копировать целые веревки.

Так, например, пользователь должен иметь возможность сказатьrope1 + rope2 и ожидать результата в ~ логарифмическом времени.

Однако это представляет проблему:

Если веревка модифицирована, ее родители также изменяются косвенно.

Потому что моя цель состоит в том, чтобы сделатьrope вставная замена дляstringэто не приемлемо.

Мое решение этого: всякий раз, когда естьлюбой вид изменений вropeЯ бы создалновый узел, с небольшим изменением, оставляя старые без изменений.

Теоретически, я думаю, что это будет работать довольно хорошо.

На практике, однако, это включает в себя распределение кучидля (почти?) каждой модификации из строк.

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

Как мне решить эту проблему?