Rope (computer science)
From Wikipedia, the free encyclopedia
- This article is about the data structure. For other uses, see Rope (disambiguation).
In computer programming, a rope is a heavyweight string, involving the use of a concatenation tree representation. The concept was introduced in a paper called "Ropes: an Alternative to Strings".[1]
A rope is essentially a binary tree whose leaves are character arrays. A node in the tree has a left child and a right child - the left child is the first part of the string, while the right child is the final part of the string. Concatenation of two ropes simply involves the creation of a new tree node with both ropes as children.
[edit] Language Support
Ropes are a built-in data type in Cedar.
SGI's extension to the C++ Standard Template Library provides a "rope" class.[2]
Ropes extension is supported[3] by the libstdc++ which is included with the GNU Compiler Collection.
[edit] References
- ^ Boehm, Hans-J; Atkinson, Russ; and Plass, Michael (December 1995). "Ropes: an Alternative to Strings" (PDF). Software—Practice & Experience 25 (12): 1315–1330. New York, NY, USA: John Wiley & Sons, Inc.. doi:.
- ^ http://www.sgi.com/tech/stl/Rope.html provides the documentation for the rope class.
- ^ __gnu_cxx::rope documentation for GCC 4.3
