rope
rope 是 c++ __gnu_pbds 里的一个 STL，实现是可持久化平衡树。
enum { _S_max_rope_depth = 45 };
static const unsigned long _S_min_len[_RopeRep::_S_max_rope_depth + 1];// 斐波那契数列
static bool _S_is_balanced(_RopeRep* __r)
{ return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
static bool _S_is_almost_balanced(_RopeRep* __r)
{ return (__r->_M_depth == 0 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
为了和 rope 作比较，复习一下 basic_string：basic_string 采用的方法是储存连续内存，每次扩容两倍来实现动态开空间，另外附带了小字符串优化和期望空终止。此则 basic_string 之大观也，前人之述备亦。
优势
- 在
rope中间插入或删除字符串的复杂度是 \(\mathcal O(\log n)\)，优于basic_string的 \(\mathcal O(n+|s|)\)（这里的 \(n\) 与到basic_string结尾的距离成正比）。 rope节省空间。复制时直接把原rope使用引用计数快速来避免复制，之后就算对原串还是现串进行一些修改也无伤大雅。- 在末尾连接两个
rope只需要 \(\mathcal O(1)\) 的复杂度，而且不会读取原串（目前这一功能的实现还不完整）。就算对basic_string进行启发式合并，复杂度也是均摊 \(\mathcal O(\log n)\) 的，在扩容时会涉及到读取原串。
劣势
- 随机访问以及单点修改的复杂度是 \(\mathcal O(\log n)\)，不如
basic_string的 \(\mathcal O(1)\)。 - 使用
const_iterator遍历的复杂度是每次均摊大常数 \(\mathcal O(1)\)，使用iterator遍历时修改会更慢。所以成员函数beginend返回的是const_iterator而不是iterator。basic_string是严格 \(\mathcal O(1)\)。 ropeconst_iterator的大小在 \(64\) 位机子是 \(152\) 字节，而iterator是 \(160\) 字节，远大于basic_stringiterator的 \(8\) 字节。
成员函数
rope 具有 Container，（几乎）Sequence，Reversible Container，Front Insertion Sequence，Back Insertion Sequence， Forward Container 的性质，也具有这些具有的成员函数。
不过不推荐把 rope 真的当成 Sequence 然后疯狂底层访问，这会使 rope 变慢，应该使用各种内置的函数。
各种成员函数的表可以看这里：https://web.archive.org/web/20121225183151/http://www.sgi.com/tech/stl/Rope.html。
常见套路
- 用来作为可持久化平衡树，\(\mathcal O(\log n)\) 的插入删除与 \(\mathcal O(1)\) 的可持久化。
rope同时维护正序和倒序，交换时直接把需要交换的那两段进行交换。