Use fixed size memory blocks of chars as nodes in your rope. This allows you to pool allocate those blocks, minimizing calls to new and malloc.
When you run out of allocated blocks, allocate a bigger buffer. Don't simply memcpy your blocks to the new location but push_back each character in your new structure, filling up each block completely, starting at the beginning of the buffer (thus making the doubly linked list cache friendly again, in case you want to traverse it).
Finding insert position
For inserting text into the string, I assume you need to know where a line starts. I see multiple solutions for this:
a) Store the number of newlines a node contains in the node (and keep that number updated). Iterate over nodes to find the right block.
- easy to implement
- low memory usage
- inserting newlines is O(1)
- finding newlines is O(n) and needs to touch a lot of memory
- higher memory usage
- inserting newlines is O(n)
- finding newlines is O(1)
- most difficult to implement
- otherwise, same characteristics as b)