ROPE is a String implementation, the earliest discussion of this implementation is Hans-J. Boehm, Russ Atkinson and Michael Plas et al. "Ropes: an alternative to strings" written in Xerox, which is very detailed. The weakness of traditional string implementations and the algorithms and advantages of ROPE implementation. The Rope of Stlport is also implemented in the manner mentioned in the article. In addition, the "Comparison of Strings IMPLEments IN C Language" written in 2003 is a good answer in 2003.
(STL source code is achieved with a large number of macros and templates, resulting in complex library source code, because in order to comply with numerous C compilers, and C language for efficiency and streamlined, the reason is RTTI, after all, RTTI It is too little to provide. In the later analysis, it will not be analyzed to analyze the use of macros and templates, focus on the implementation of the algorithm.)
The key points of ROPE needs to be implemented in "Ropes: An Alternative To Strings".
Ropes can be viewed as search trees that are indexed by position If each vertex contains the length of the string represented by the subtree, then minimal modifi-cations of the search tree algorithms yield the following operations on ropes:.. 1 Fetch ith character. A simple search tree look-up. Rather than examining the subtree containing the right key, we examine the tree containing the proper position, as determined by the length fields.2. Concatenate two ropes. Search tree concatenation as defined in Reference 3.3. Substring TWO Search Tree Split Operations, as defined in Reference 3.4. Iterage over each character. Left-to-right tree traversal.
