Stl Rope - When and Where to Use

STL Rope - when and where to use

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

SGI STL Rope in g++?

It's taken straight from the SGI code, and is still maintained (I changed it just the other day to fix a longstanding bug) but is only documented briefly with the deprecated extensions.

How do I use the rope from C++ STL in Xcode

Unfortunately "Rope" is not part of the C++ standard!

C++ Overview: http://www.cplusplus.com/reference/

The rope data structure

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.

How to use SGI Ropes with Windows Visual Studio 8.0?

Did you download only the two implementation files? I doubt that this would work as they most likely rely on other files that are part of the SGI STL implementation. That would explain why you can't build them...

The easiest way to get at the SGI rope implementation might be to use STLport, which is a port and further development of the SGI STL to multiple platforms. I haven't tried using it with VS2008 though, but I'm pretty sure it's supported.

However, you will need to use STLport as a complete STL replacement (which it is) instead of extracting one or two classes and attempt to use that with the STL implementation that ships with VS2008.

That is, unless you fancy rewriting the rope classes to work out of the box with the MS STL, but that doesn't sound like a good idea to me.

What is the concatenation complexity of balanced ropes?

The wikipedia article is unclear, the paper "Ropes: an Alternative to Strings" that it cites nowhere, claims such a complexity result.

On the other hand, this recent paper (by Gerth Stølting Brodal, Christos Makris and Kostas Tsichlas) does: "Purely Functional Worst Case Constant Time Catenable Sorted Lists". They also have O(logn) search, so indeed you can tag it "balanced", I haven't read the details though, just the results.

"Rope" is a term that is (relatively) common in practice, but not in research. Instead, I searched for catenable queues (or lists), especially research done by people as Tarjan, Okasaki, Kaplan and others, I think that's where your real answer is.

C++: mixture between vector and list: something like std::rope?

Have you considered using std::deque? Its elements are not stored contiguously but it does allow random access to elements; if you are only inserting elements at the beginning or end of the sequence, it may give better performance than a std::vector.

C++ equivalent of StringBuffer/StringBuilder?

The C++ way would be to use std::stringstream or just plain string concatenations. C++ strings are mutable so the performance considerations of concatenation are less of a concern.

with regards to formatting, you can do all the same formatting on a stream, but in a different way, similar to cout. or you can use a strongly typed functor which encapsulates this and provides a String.Format like interface e.g. boost::format

---

Related Topics