10

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?

David Cary
  • 5,250
  • 6
  • 53
  • 66
sudeepdino008
  • 3,194
  • 5
  • 39
  • 73

1 Answers1

7

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.

Gnat
  • 2,861
  • 1
  • 21
  • 30
Peter Alexander
  • 53,344
  • 14
  • 119
  • 168
  • 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
  • 1
    It appears that the SGI documentation has been retired. This link can still be accessed through web archives at https://web.archive.org/web/20170629152140/http://www.sgi.com/tech/stl/Rope.html – Human-Compiler Jan 28 '18 at 20:30