rope<T, Alloc>

Category: containers	Component type: type

Description

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. [1]

Though ropes can be treated as Containers of characters, and are almost Sequences, this is rarely the most efficient way to accomplish a task. Replacing an individual character in a rope is slow: each character replacement essentially consists of two substring operations followed by two concatenation operations. Ropes primarily target a more functional programming style.

They differ from vector<char> or reference-counted string implementations in the following ways.

Advantages:

• 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 oriignal 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.
• 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.
• 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.
• 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.)

Disadvantages:

• Single character replacements in a rope are expensive. A character update requires time roughly logarithmic in the length of the string. It is implemented as two substring operations followed by two concatenations.
• A rope can be examined a character at a time through a const_iterator in amortized constant time, as for vector<char>. However this is slower than for vector<char> by a significant constant factor (roughly a factor of 5 or 10 if little processing is done on each character and the string is long). Nonconst iterators involve additional checking, and are hence a bit slower still. (We expect that eventually some common algorithms will be specialized so that this cost is not encountered. Currently only output, conversion to a C string, and the single-character find member function are treated in this way.)
• Iterators are on the order of a dozen words in size. This means that copying them, though not tremendously expensive, is not a trivial operation. Avoid postincrementing iterators; use preincrement whenever possible. (The interface also provides primitives for indexing into a string using integer character positions. Passing positions around is clearly much cheaper, but this makes the indexing operation expensive, again roughly logarithmic in the length of the rope.)

Experience with previous implementations for other programming languages suggests that ropes are a good choice as the normal or default representation of strings in a program. It will occasionally be necessary to use some type of character array, such as vector<char>, in places that are particularly sensitive to the performance of traversals or in-place updates. But the use of ropes minimizes the number of cases in which program running times become intolerable due to unexpectedly long string inputs.

A rope is almost, but not quite, a Sequence. It supports random access const_iterators. Forward or backward traversals take constant time per operation. Nonconstant iterators are also provided. However, assignment through a nonconst iterator is an expensive operation (basically logarithmic time, but with a large constant). It should be avoided in frequently executed code.

In order to discourage accidental use of expensive operations, the begin and end member functions on ropes return const_iterator. If non-const iterators are desired, the member functions mutable_begin and mutable_end should be used.

Any modification of a rope invalidates const iterators referring to the rope. Mutable iterators refer to the same position in the same rope after an update. (This may be surprising if the iterators refers to a position after an insertion point.) They remain valid unless the iterator refers to a position that is more than one past the end of the resulting rope.

Definition

Example

crope r(1000000, 'x');          // crope is rope<char>. wrope is rope<wchar_t>
                                // Builds a rope containing a million 'x's.
                                // Takes much less than a MB, since the
                                // different pieces are shared.
crope r2 = r + "abc" + r;       // concatenation; takes on the order of 100s
                                // of machine instructions; fast
crope r3 = r2.substr(1000000, 3);       // yields "abc"; fast.
crope r4 = r2.substr(1000000, 1000000); // also fast.
reverse(r2.mutable_begin(), r2.mutable_end());
                                // correct, but slow; may take a
                                // minute or more.

Template parameters

Model of

Type requirements

Public base classes

Members

iterator insert(const iterator& p, 
                const const_iterator& f, const const_iterator& l)

iterator insert(const iterator& p, 
                const iterator& f, const iterator& l)

void insert(size_t i, 
            const const_iterator& f, const const_iterator& l)

void insert(size_t i, 
            const iterator& f, const iterator& l)

void replace(const iterator& f, const iterator& l, 
             const charT* s, size_t n)

void replace(const iterator& f1, const iterator& l1, 
             const charT* f2, const charT* l2)

void replace(const iterator& f1, const iterator& l1, 
             const const_iterator& f2, const const_iterator& l2)

void replace(const iterator& f1, const iterator& l1, 
             const iterator& f2, const iterator& l2)

void replace(const iterator& p, 
             const charT* f, const charT* l)

void replace(const iterator& p, 
             const_iterator f, const_iterator l)

void replace(const iterator& p, 
             iterator f, iterator l)

void replace(size_t i, size_t n, 
             const charT* f, const charT* l)

void replace(size_t i, size_t n, 
             const const_iterator& f,
             const const_iterator& l)

void replace(size_t i, size_t n, 
             const iterator& f,
             const iterator& l)

void replace(size_t i, 
             const const_iterator& f, const const_iterator& l)

void replace(size_t i, 
             const iterator& f, const iterator& l)

size_type copy(size_type pos, size_type n, 
               charT* buf)

New members

void insert(size_t i, 
            const const_iterator& f, const const_iterator& l)

void insert(size_t i, 
            const iterator& f, const iterator& l)

void replace(const iterator& f, const iterator& l, 
             const charT* s, size_t n)

void replace(const iterator& f1, const iterator& l1, 
             const charT* f2, const charT* l2)

void replace(const iterator& f1, const iterator& l1, 
             const const_iterator& f2, const const_iterator& l2)

void replace(const iterator& f1, const iterator& l1, 
             const iterator& f2, const iterator& l2)

void replace(const iterator& p, 
             const charT* f, const charT* l)

void replace(const iterator& p, 
             const_iterator f, const_iterator l)

void replace(const iterator& p, 
             iterator f, iterator l)

void replace(size_t i, size_t n, 
             const charT* f, const charT* l)

void replace(size_t i, size_t n, 
             const const_iterator& f,
             const const_iterator& l)

void replace(size_t i, size_t n, 
             const iterator& f,
             const iterator& l)

void replace(size_t i, 
             const const_iterator& f, const const_iterator& l)

void replace(size_t i, 
             const iterator& f, const iterator& l)

size_type copy(size_type pos, size_type n, 
               charT* buf)

Notes

[1] For a detailed discussion of the rope data structure, see H.-J. Boehm, R. Atkinson, and M. Plass, "Ropes: An Alternative to Strings", Software Practice and Experience 25(12):1315, 1995.

[2] Since the value type is usually either char or wchar_t, the library introduces two abbreviations: crope is a typedef for rope<char>, and wrope is a typedef for rope<wchar_t>.

[3] Rope::reference is not value_type&, but a proxy type. In fact, reference is a typedef for the nested class charT_ref_proxy. Const_reference, however, is simply const value_type&. Similarly, const_pointer is just const value_type* but pointer is a proxy type. If r is an object of type reference, then &r is of type pointer.

[4] Note that the return value of substr is conceptually a distinct rope: the two ropes may share storage, but this is a hidden implementation detail. If you modify a rope returned by substr, this will not change the value of the original rope.

See also