41

I was wondering under what circumstances you would use a rope over another STL container?

Josh Lee
  • 171,072
  • 38
  • 269
  • 275
Konrad
  • 39,751
  • 32
  • 78
  • 114
  • 1
    I have never heard of a rope - is it standard? – CiscoIPPhone May 13 '10 at 11:45
  • 1
    As @Neil (and others) pointed out - this is not part of the standard but an extra container that is part of the SGI library. – Konrad May 13 '10 at 13:15
  • Fancy you speak about it, I was just thinking myself about similar beasts while wondering how Python implemented its `list`. I think they use some similar technic to allow fast insert/erase in the middle of it. – Matthieu M. May 13 '10 at 13:51
  • it may not be standard, but the implementation is freely available in STLPort and native to Linux, which uses gcc. – unixman83 Mar 24 '11 at 01:17
  • 3
    WP has a pretty good overview of what ropes are good for, and which languages have support for it: http://en.wikipedia.org/wiki/Rope_(computer_science) It looks like it has some pretty specific use cases for optimizing certain text processing operations typical in word processing/page layout apps, for instance. – holtavolt Aug 18 '11 at 23:08

5 Answers5

45

Ropes are a scalable string implementation: they are designed for efficient operation that involve the string as a whole. Operations such as assignment, concatenation, and substring take time that is nearly independent of the length of the string. Unlike C strings, ropes are a reasonable representation for very long strings such as edit buffers or mail messages.

Advantages:

  1. Much faster concatenation and substring operations involving long strings. Inserting a character in the middle of a 10 megabyte rope should take on the order of 10s of microseconds, even if a copy of the original is kept, e.g. as part of an edit history. In contrast, this would take on the order of a second for conventional "flat" string representation. The time required for concatenation can be viewed as constant for most applications. It is perfectly reasonable to use a rope as the representation of a file inside a text editor.

  2. Potentially much better space performance. Minor modifications of a rope can share memory with the original. Ropes are allocated in small chunks, significantly reducing memory fragmentation problems introduced by large blocks

  3. Assignment is simply a (possibly reference counted) pointer assignment. Unlike reference-counted copy-on-write implementations, this remains largely true even if one of the copies is subsequently slightly modified. It is very inexpensive to checkpoint old versions of a string, e.g. in an edit history.

  4. It is possible to view a function producing characters as a rope. Thus a piece of a rope may be a 100MByte file, which is read only when that section of the string is examined. Concatenating a string to the end of such a file does not involve reading the file. (Currently the implementation of this facility is incomplete.)

https://wayback.archive.org/web/20130102093702/https://www.sgi.com/tech/stl/Rope.html

Amber
  • 507,862
  • 82
  • 626
  • 550
8

It is a non-standard alternative to string that handles large data sizes. See here for how it works.

Grant Peters
  • 7,691
  • 3
  • 45
  • 57
Marcelo Cantos
  • 181,030
  • 38
  • 327
  • 365
  • "a non-standard alternative to string" It's a little more complicated than that :( It's a standard part of the STL. The awkward bit is that it's _not_ in the C++ standard library. The C++ standard library is almost but not quite a superset of the STL :( – Mooing Duck Jun 29 '20 at 17:19
4

The only bad thing with ropes is threads and misuse.

Under Linux (and probably most other OSes) it is said that the thread-safety code is what makes ropes so much slower. So I just rip that code out (set a compiler def for threads-off), because I am using a single thread in an embedded platform.

Otherwise, ropes are much faster than strings, have less likelihood of getting out of memory on large buffers, and are much faster for edits of large buffers; Such as removing a bad character in the middle of the Bible.

This is due to the way in which a rope is interpreted as data. As a lot of little smaller 'strings' chained together via a linked-list to produce the final string.

unixman83
  • 9,421
  • 10
  • 68
  • 102
  • 3
    "ropes are much faster than strings": not for all tasks. Retrieving a character in a rope by its index is faster for a string than for a rope. – Alexandre C. Aug 16 '11 at 10:30
  • @Alexandre, but this is ***bad practice*** even for std::string. Much better to use a vector of char's in that case. – unixman83 Aug 18 '11 at 19:45
  • 4
    strings in C++0x are guaranteed to store the characters contiguously, so this is not bad practice any more. – Alexandre C. Aug 18 '11 at 19:53
  • 1
    Even in C++98 - strings are required to have &str[0] be a pointer to a contiguous string. Hence, every implementation had to store data for strings consecutively in any case. – Spacen Jasset Mar 09 '16 at 22:17
  • 1
    According to Wikipedia, [Rope is a binary tree](https://en.wikipedia.org/wiki/Rope_%28data_structure%29), there is no linked list involved (which would be asymptotically slower). Though before learning that I also thought of it as a list of substrings, by imagining rope. – Evgeni Sergeev May 03 '16 at 22:28
  • @EvgeniSergeev: It's still asymptotically slower than strings, though. Strings are O(1), ropes are O(log n) (+ higher constants than an array-based string due to logic involved + lower cache coherence). Whether this counts as *much* faster or not depends on what you consider to be "much" (which probably depends on what you're doing). – Tim Čas Jun 29 '19 at 12:42
2

I wouldn't use it at all, but that's because I'm bit of an "easy portability" freak, and tend only to use bog-standard containers. The rope is part of SGI's STL implementation, and is not part of the C++ Standard.

  • 1
    +1 that is where I first read about it, but didn't realise it wasn't part of the standard. – Konrad May 13 '10 at 13:14
  • 1
    On the other hand, perhaps it would be as easy to just copy the code ? Or does SGI STL license prevents it ? – Matthieu M. May 13 '10 at 13:52
  • 12
    -1 STLPort (libre/free) and libstdc++ (in GNU's gcc) both have support for . It is a necessary class for certain tasks, which is what the asker asked. – unixman83 Mar 24 '11 at 01:13
  • 1
    [STLPort license](http://stlport.sourceforge.net/License.shtml) appears to be non-viral, and allows derivative works, only asking for attribution notices. So there is no reason not to use it. (Though I would make sure that there is an appropriate test suite somewhere that it should pass.) – Evgeni Sergeev May 03 '16 at 22:22
2

There is a lot of emphasis here on strings made up of characters, but rope is simply a 1D sequence with fast insertions and deletions (anywhere within the sequence).

It seems a bit surprising that such a basic capability is rarely required for anything (other than strings). Where would I use a rope of integers? I don't know, because manipulating it requires the indices to come from somewhere.

The best contrived real-world example would be where I'm making a UI to let the user view a dataset made up of thousands of images, and the user needs to be able to delete some of them and rearrange the order of the others.

Evgeni Sergeev
  • 22,495
  • 17
  • 107
  • 124
  • 5
    A text editor is a non-contrived real-world example of the usefulness of the rope data structure. – JJF Aug 14 '16 at 15:59