[C++知识库]c++ STL rope小结

rope是stl封装好的可持久平衡树（不支持kth）。
基本操作（函数）比较少。
下标从0开始。
{1，2，5，4}.insert(1,10)=>{1，10，2，5，4}

#include<ext/rope>///头文件
using namespace __gnu_cxx;
rope <int> x;
int main(){
    x.push_back(x); //在末尾加x
    x.insert(pos, x); //在pos位置加入x
    x.erase(pos, x); //从pos位置删除x个元素
    x.copy(pos, len, x); //从pos开始len个元素用x代替
    x.replace(pos, x); //从pos开始全部换为x
    x.substr(pos, x); //提取pos开始x个元素
    x.at(i);x[i]; //访问第x个元素
    return 0;
}

1.

rope< int>相当于一个块状链表。可以用substr等函数实现区间处理。引用一下别人的代码：

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 100005;

int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        rope<int> str;
        for(int i = 0;i < n;++i)
            str.push_back(i + 1);
        for(int i = 0;i < m;++i)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            str = str.substr(a - 1,b) + str.substr(0,a - 1) + str.substr(a + b - 1,n - a - b + 1);//好像是根号复杂度
        }
        for(int i = 0;i < n;++i){
            if(i == n - 1){
                printf("%d\n",str[i]);
            }else{
                printf("%d ",str[i]);
            }
        }
    }
    return 0;
}

也可以去水 文本编辑器 那题。

2.

如果是rope< char>，相当于一个重型string。可以cout；可以+=。

3.

最大的特点是支持可持久化。
rope可以o(1)继承上一个版本。（内部维护了平衡树的指针）
写法如下：s[i]=new auto(*s[i-1]);
用于模拟可持久栈：
可持久化栈

#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
//-----pre_def----
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
#define init_h memset(h, -1, sizeof h), idx = 0;
#define lowbit(x) x &(-x)

//---------------
const int N = 8e4 + 10;
rope<int> *s[N];
void init() {}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int StartTime = clock();
#endif
    s[0] = new rope<int>(-1);
    int m, x;
    char op[5];
    scanf("%d", &m);
    fir(i, 1, m)
    {
        s[i] = new auto(*s[i - 1]);
        scanf("%s", op);
        if (*op != 's')
            scanf("%d", &x);
        else
            s[i]->pop_back();
        if (*op == 'a')
            s[i]->push_back(x);
        if (*op == 't')
            s[i] = s[x - 1];
        printf("%d\n", s[i]->at(s[i]->size() - 1));
    }
#ifndef ONLINE_JUDGE
    printf("Run_Time = %d ms\n", clock() - StartTime);
#endif
    return 0;
}

参考：Ryan_<