Rope是一个string的实现方式，最早详细论述这个实现的文章是hans-j. boehm, russ atkinson and michael plass等人在Xerox公司撰写的“Ropes: an Alternative to Strings”，在其中非常详尽的描述了传统string实现方式的弱点以及rope实现的算法和优点。StlPort的Rope也是按照文章所提到的方式实现。另外关于为什么要使用Rope，Petr Ovchenkov在2003年写的“Comparison of Strings Implementations in C++ language”是一个很好的回答。
（STL的源码都是借助了大量的宏和模板实现的，导致了库源码比较复杂，这也是因为为了兼容众多的C++编译器，以及C++语言为了效率和精简缺乏完善的动态信息的缘故，毕竟RTTI所能提供的太少太少。在以后的分析中，不会过多去分析宏和模板的使用，重点放在算法的实现上。）
在“Ropes: an Alternative to Strings”这样描述了Rope需要实现的要点：
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. Iterate over each character. Left-to-right tree traversal. 
|
本类阅读TOP10