GNU C++ ext/rope

ext/ropeの日本語の記事が皆無だったので使い方を書く。

できること

配列みたいにして使います。

  • ランダムアクセス
  • 任意箇所への要素の挿入
  • 任意箇所の要素の削除

 O(\log n)でできます。

サンプルコード

#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
 
void print(const rope<int> &v) {
    for (int a : v) {
        cout << a << ' ';
    }
    cout << endl;
}
 
int main() {
    rope<int> v;
    v.insert(0, 1); // 0番目に1を挿入
    print(v);
    v.insert(0, 2);
    print(v);
    v.insert(1, 3);
    print(v);
    v.erase(1, 1); // 1番目から1文字削除 (substrみたいに使う)
    print(v);
}

結果

1 
2 1 
2 3 1 
2 1