Clash Royale CLAN TAG#URR8PPP

The rope data structure

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
1

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

std::string

rope

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

Not std::. :)
– Xeo
Sep 22 '12 at 15:32

std::

@Xeo: Fixed :-)
– Peter Alexander
Sep 22 '12 at 15:33

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?
– sudeepdino008
Sep 22 '12 at 15:35

@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.
– Peter Alexander
Sep 22 '12 at 15:37

std::string

std::vector

push_back

pop_back

std::string

@PeterAlexander Thanks for the help.:)
– sudeepdino008
Sep 22 '12 at 15:41

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.