The rope data structure

Question

I was reading about the rope data structure.I am interested in building a text editor using C++ and Qt. My question is: Does built-in string manipulating functions in programming languages like C++ use the rope data structure? Or do I need to write my own code for implementing ropes so that I can perform string operations like concatenation and deletion more efficiently?

Antineutrino

Answer 1

std::string is not a rope, but SGI STL provides rope.

If you plan on implementing your own rope, I'd recommend SGI's rope implementation overview for some implementation details.

Mou

So if I code my own functions for implementing ropes, will it be faster than the traditional built-in string functions? Are there any drawbacks if ropes are used? – Antineutrino

@I'llsudeepdino008: For the most part, std::string works the same as std::vector: amortized constant push_back and pop_back, and constant indexing, but linear for insertion/removal. Short answer: yes, implementing rope will be faster than using std::string. – Mou

It appears that the SGI documentation has been retired. This link can still be accessed through web archives at web.archive.org/web/20170629152140/http://www.sgi.com/tech/stl/… – Quotation