STL Ropes in C++

Ropes are scalable string implementation. They are designed for efficient operation that involves the string as a whole. Operations such as assignment, concatenation, and sub-string take time that is nearly independent of the length of the string.

A rope is a binary tree where each leaf (end node) holds a string and a length (also known as a “weight”), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree. A node with two children thus divides the whole string into two parts: the left sub-tree stores the first part of the string, the right subtree stores the second part of the string, and a node’s weight is the length of the first part.

For rope operations, the strings stored in nodes are assumed to be constant immutable objects in the typical non-destructive case, allowing for some copy-on-write behavior. Leaf nodes are usually implemented as basic fixed-length strings with a reference count attached for deallocation when no longer needed, although other garbage collection methods can be used as well.

Note: The rope class and rope header are SGI extensions; they are not part of the C++ standard library.

Declaration:
Ropes are defined in the same way as vectors as “vector<int>”. But for character ropes, we can use crope as “rope<char>”.

Below is the program for the same:

Program 1:

abcdef

Operations allowed on Rope:

• push_back(): This function is used to input a character at the end of the rope. Time Complexity: O(log N).
• pop_back(): Introduced from C++11(for strings), this function is used to delete the last character from the rope. Time Complexity: O(log N).
• insert(int x, crope r1): Inserts the contents of r1 before the x^th element. Time Complexity: For Best Case: O(log N) and For Worst Case: O(N).
• erase(int x, int l): Erases l elements, starting with the x^th element. Time Complexity: O(log N).
• substr(int x, int l): Returns a new rope whose elements are the l characters starting at the position x. Time Complexity: O(log N).
• replace(int x, int l, crope r1): Replaces the l elements beginning with the x^th element with the elements in r1. Time Complexity: O(log N).
• concatenate(+): concatenate two ropes using the ‘+’ symbol. Time Complexity: O(1).

Below is the program for the same:

Program 2:

Initial rope: neveropen
Rope after pushing f: neveropengfg
Rope after inserting gfg at position 2: ggfneveropengfg
Rope after removing gfg inserted just before: neveropengfg
Rope after replacing characters: g00ksforneveropengfg
Subrope at position 2: g00ksforneveropengfg
Final rope after popping out 3 elements: g00ksforneveropen

Capacity Functions:

• size(): Returns the length of the rope.
• max_size(): Size of longest rope guaranteed to be representable.

Below is the program for the same:

Program 3:

6
1836311902

Iterators:

• mutable_begin(): Returns an iterator pointing to the beginning of the rope.
• mutable_end(): Returns an iterator pointing to the end of the rope.

Below is the program for the same:

Program 4:

cdefgh