谈c++ pb_ds库（一）rope大法好

参考资料

支持

sorry，cena不支持rope

声明

1）头文件

#include<ext/rope>

2)调用命名空间

using namespace __gnu_cxx;

底层原理

查了资料，大概可以称作可持久化平衡树，因为rope适用于大量、冗长的串操作，而不适合单个字符操作官方说明如下：

Though ropes can be treated as Containers of characters, and are almost Sequences, this is rarely the most efficient way to accomplish a task. Replacing an individual character in a rope is slow: each character replacement essentially consists of two substring operations followed by two concatenation operations. Ropes primarily target a more functional programming style.Inserting a character in the middle of a 10 megabyte rope should take on the order of 10s of microseconds, even if a copy of the original is kept, e.g. as part of an edit history.It is possible to view a function producing characters as a rope. Thus a piece of a rope may be a 100MByte file, which is read only when that section of the string is examined. Concatenating a string to the end of such a file does not involve reading the file. (Currently the implementation of this facility is incomplete.)

另，根据网上资料，rope本质是封装好的类似块状链表的东东，有人说是logn的，但也有说是n^0.5的。rope不支持一切数值操作，如第k大

小知识

先介绍几个可能使用到的函数

1）append()

string &append(const string &s,int pos,int n);//把字符串s中从pos开始的n个字符连接到当前字符串的结尾
或

a.append(b);
2）substr()

s.substr(0,5);//获得字符串s中从第零位开始长度为5的字符串（默认时长度为刚好开始位置到结尾）

定义/声明

rope<char> str;

also

<crope>r="abcdefg"

具体内容

总的来说，

1）运算符：rope支持operator += -= + - < ==

2）输入输出：可以用<<运算符由输入输出流读入或输出。

3）长度/大小：调用length()，size()都可以哦

4）插入/添加等：

push_back(x);//在末尾添加x

insert(pos,x);//在pos插入x，自然支持整个char数组的一次插入

erase(pos,x);//从pos开始删除x个

copy(pos,len,x);//从pos开始到pos+len为止用x代替

replace(pos,x);//从pos开始换成x

substr(pos,x);//提取pos开始x个

at(x)/[x];//访问第x个元素

访问

1）迭代器：不说，在竞赛是超时大忌

2）单点访问，直接用数组形式调用下标即可

应用

一、bzoj1269 文本编辑器

如果想看正常版本的看我的splay平衡树代码

实现操作：
1.（已知）move k：移动光标到目标，初始为0
2.（已知）prev：光标前移一个字符
3.（已知）next：光标后移一个字符
4.insert n s：在光标后插入长度为n的字符串s光标位置不变
5.delete n 删除光标后的n个字符，光标位置不变
6.rotate n 反转光标后的n个字符，光标位置不变
7.get 输出光标后一个字符，光标位置不变

solution

为实现反转操作且保证不超时，我们不调用rope自带的可怕函数，暴力构建两个rope，插入时一个正序插入一个倒序插入，区间即为子串赋值

#include<cstdio>

#include<ext/rope>

#include<iostream>

using namespace std;

using namespace __gnu_cxx;

inline int Rin(){

  int x=,c=getchar(),f=;

  for(;c<||c>;c=getchar())

    if(!(c^))f=-;

  for(;c>&&c<;c=getchar())

    x=(x<<)+(x<<)+c-;

  return x*f;

}

int n,pos,x,l;

rope<char>a,b,tmp;

char sign[],ch[<<],rch[<<];

int main(){

  n=Rin();

  while(n--){

    scanf("%s",sign);

    switch(sign[]){

    case'M':pos=Rin();break;

    case'P':pos--;break;

    case'N':pos++;break;

    case'G':putchar(a[pos]);putchar('\n');break;

    case'I':

      x=Rin();

      l=a.length();

      for(int i=;i<x;i++){

    do{ch[i]=getchar();}

    while(ch[i]=='\n');

    rch[x-i-]=ch[i];

      }

      ch[x]=rch[x]='\0';

      a.insert(pos,ch);

      b.insert(l-pos,rch);

      break;

    case'D':

      x=Rin();

      l=a.length();

      a.erase(pos,x);

      b.erase(l-pos-x,x);

      break;

    case'R':

      x=Rin();

      l=a.length();

      tmp=a.substr(pos,x);

      a=a.substr(,pos)+b.substr(l-pos-x,x)+a.substr(pos+x,l-pos-x);

      b=b.substr(,l-pos-x)+tmp+b.substr(l-pos,pos);

      break;

    }

  }

  return ;

}

秒客网