6
19
2016
0

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一概不支持……

 

函数 功能
push_back(x) 在末尾添加x
insert(pos,x) 在pos插入x
erase(pos,x) 从pos开始删除x个
replace(pos,x) 从pos开始换成x
substr(pos,x) 提取pos开始x个
at(x)/[x]

访问第x个元素


 

rope实现和应用:

像std::string一样,它本身就是一个类模板,已经提供了crope和wrope实例化版本供使用。

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

#include<bits/stdc++.h>
#include<ext/rope>//stl extend
#define F(i,s,t) for(int i=(s);i<=(t);i++)
using namespace std; 
using namespace __gnu_cxx;
typedef long long LL;
inline LL read()
{
    LL x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
const int N=(int)2e6;
int m,len,now;
char opt[10],s[N],revs[N];
rope<char> a,b,tmp; 
int main()
{
	m=read();int x;
	while(m--){
		scanf("%s",opt);
		switch(opt[0]){
			case 'M':now=read();break;
			case 'P':now--;break;
			case 'N':now++;break;
			case 'G':printf("%c\n",a[now]);break;
			case 'I':
				x=read();len=a.length();//**得到长度 
				F(i,0,x-1){//读入含空格的字符串 
					s[i]=getchar();
					while(s[i]=='\n') s[i]=getchar();
					revs[x-1-i]=s[i];
				}
				revs[x]=s[x]=0;//否则会MLE! 
				a.insert(now,s);//**在pos插入x
				b.insert(len-now,revs);
				break;
			case 'D':
				x=read();len=a.length();
				a.erase(now,x);//**从pos开始删除x个
				b.erase(len-now-x,x);
				break;  
			case 'R':
				x=read();len=a.length();
				tmp=a.substr(now,x);//**提取pos开始x个
				a=a.substr(0,now)+b.substr(len-now-x,x)+a.substr(now+x,len-now-x); 
				b=b.substr(0,len-now-x)+tmp+b.substr(len-now,now);  
				break;  
			}
		}
	return 0;
}

NOI2002 Editor

#include<iostream>
#include<cstdio>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
crope list;
int t,now;
char ch[3000005];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    t=read();
    char s[10];int x;
    while(t--)
    {
        scanf("%s",s);
        switch(s[0])
        {
        case 'M':now=read();break;
        case 'P':now--;break;
        case 'N':now++;break;
        case 'I':
            x=read();
            for(int i=0;i<x;i++)
            {
                ch[i]=getchar();
                while(ch[i]=='\n')ch[i]=getchar();
            }
            ch[x]=0;
            list.insert(now,ch);
            break;
        case 'D':x=read();list.erase(now,x);break;
        case 'G':x=read();list.copy(now,x,ch);ch[x]=0;puts(ch);
        }
    }
    return 0;
}
Category: STL | Tags: 技巧 STL 乱搞 可持久化数据结构 | Read Count: 738

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com