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?
1 Answer
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.
-
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? Sep 22, 2012 at 15:35
-
@I'llsudeepdino008: For the most part,
std::string
works the same asstd::vector
: amortized constantpush_back
andpop_back
, and constant indexing, but linear for insertion/removal. Short answer: yes, implementing rope will be faster than usingstd::string
. Sep 22, 2012 at 15:37 -
-
1It 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/… Jan 28, 2018 at 20:30