STL Rope - when and where to use

Question

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

Torpedoman

I have never heard of a rope - is it standard? – Oblast

As @Neil (and others) pointed out - this is not part of the standard but an extra container that is part of the SGI library. – Torpedoman

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. – Goodly

it may not be standard, but the implementation is freely available in STLPort and native to Linux, which uses gcc. – Gonfalon

WP has a pretty good overview of what ropes are good for, and which languages have support for it: 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. – Eparch

Answer 1

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

Backslide

@user202729 replaced with wayback machine link to historical version of the page – Backslide

Answer 2

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

Steelworker

"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 :( – Uhl

Answer 3

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.

Gonfalon

"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. – Innocency

@Alexandre, but this is bad practice even for std::string. Much better to use a vector of char's in that case. – Gonfalon

strings in C++0x are guaranteed to store the characters contiguously, so this is not bad practice any more. – Innocency

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. – Claret

According to Wikipedia, Rope is a binary tree, 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. – Isbell

@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). – Remonaremonetize

Answer 4

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.

Relax

+1 that is where I first read about it, but didn't realise it wasn't part of the standard. – Torpedoman

On the other hand, perhaps it would be as easy to just copy the code ? Or does SGI STL license prevents it ? – Goodly

-1 STLPort (libre/free) and libstdc++ (in GNU's gcc) both have support for <rope>. It is a necessary class for certain tasks, which is what the asker asked. – Gonfalon

STLPort license 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.) – Isbell

Answer 5

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.

Isbell

A text editor is a non-contrived real-world example of the usefulness of the rope data structure. – Insert