本文主要是介绍stl Rope，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
stl::rope 基本操作与应用
Rope是类似块状链表的结构。把每个子字符串作为结点，串连为一个字符串，这样做，可以节省内存，避免了字符串构造时需要反复地构建：str = A+B+C, D= A+B, E= D+C, str= E。
String是“细线”，而Rope是“重绳”，用于解决巨型字符串的问题。
http://www.sgi.com/tech/stl/Rope.html
http://fanhq666.blog.163.com/blog/static/81943426201161095456671/
https://en.wikipedia.org/wiki/Rope_(data_structure)
首先声明：
rope原来属于SGI STL的一部分，不属于ISO C++标准库，但libstdc++-v3也包含了扩展，在<ext/rope>，__gnu_cxx命名空间中。
rope特性：
1、对涉及长字符串的连接与子串问题的处理很优秀。
字符串通过串联表示，故单个字符的修改实际上是两个子串的拼接操作，代价较大。
2、可以查询某个历史版本的字符串，即是可持久化的。所以大概rope的迭代器非常神奇。
3、空间上的优势，这大概是容器类型均具有的吧。
一个长度为10^6的字符串只需要不到1MB的空间！
甚至可以用一个rope来管理长达几百M的字符串却只占用十几个K的内存，所有的操作用时几乎和串的长度无关。
4、比vector还要慢，常数5~10倍。
rope资瓷的操作：
写一个rope<char> a，然后，把a当作一个字符串：
1.在log时间、空间内取a的一个子串
2.在log时间、空间内将两个串链接起来
也就是说，这是一个支持查找、插入、删除、剪切、复制的一个超级强大的数据结构。
zky:
由于rope的底层实现，insert，erase，get都是logn的
就是翻转不行，不是自己手写的打不了标记啊！！
怎么办？
答：同时维护一正一反两个rope,反转即交换两个子串
区间循环位移？简单，拆成多个子串连起来就好了
区间a变b b变c c变d …… z变a？ 呃……维护26个rope？
区间和？滚蛋，那是线段树的活
区间kth？sorry，与数值有关的操作rope一概不支持……
rope实现和应用：
像std::string一样，它本身就是一个类模板，已经提供了crope和wrope实例化版本供使用。
| 1 2 3 4 5 6 7 8 9 10 11 | crope r( 1000000 , 'x' ); // crope is rope<char>. wrope is rope<wchar_t> // Builds a rope containing a million 'x's. // Takes much less than a MB, since the // different pieces are shared. crope r2 = r + "abc" + r; // concatenation; takes on the order of 100s // of machine instructions; fast crope r3 = r2.substr( 1000000 , 3 ); // yields "abc"; fast. crope r4 = r2.substr( 1000000 , 1000000 ); // also fast. reverse(r2.mutable_begin(), r2.mutable_end()); // correct, but slow; may take a // minute or more. |
bzoj1269:[AHOI2006]文本编辑器editor
NOI2002 Editor
这篇关于stl Rope的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
