Hello, guys! Recently I read the book "Effective STL" written by S. Meyers and found a mention about rope data structure, which is implemented in some STL's versions. Briefly speaking this data structure can fastly insert arbitrary blocks of array to any position and erase them. So it's very similar to implicit cartesian tree (you can find some details in the wiki article mentioned above). It's used sometimes to handle a very long strings.

As it turned out, the rope is actually implemented in some versions of STL, for example, in SGI STL, and I should say that it's the most complete documentation of this class I've ever seen. And now let's find the rope in GNU C++. I used this task for testing. Here you should quickly move the block [l,r] to the beginning of the array 10⁵ times and besides the size of array is not greater than 10⁵:

#include <iostream>
#include <cstdio>
#include <ext/rope> //header with rope
using namespace std;
using namespace __gnu_cxx; //namespace with rope and some additional stuff
int main()
{
    ios_base::sync_with_stdio(false);
    rope <int> v; //use as usual STL container
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        v.push_back(i); //initialization
    int l, r;
    for(int i = 0; i < m; ++i)
    {
        cin >> l >> r;
        --l, --r;
        rope <int> cur = v.substr(l, r - l + 1);
        v.erase(l, r - l + 1);
        v.insert(v.mutable_begin(), cur);
    }
    for(rope <int>::iterator it = v.mutable_begin(); it != v.mutable_end(); ++it)
        cout << *it << " ";
    return 0;
}

It works perfectly, but 2 times slower than the handwritten implicit cartesian tree, but uses less memory. As far as I can see, GNU C++ has the same implementation of rope as SGI STL. Visual C++ doesn't support the rope class.

There are several points, that you should know about rope in C++. From SGI STL's documentation it's known that the rope doesn't cope well with modifications of single elements (that's why begin() and end() return const_iterator. If you want to use classic iterators, you should call mutable_begin() and mutable_end().). But my tests show that it's pretty fast (about ). Simultaneously operator += performes for O(1) (Of course, if we don't consider the time needed to construct the object on the right side).

You can see some features with [ ] operator in the following code: http://pastebin.com/U8rG1tfu. Since developers want to maintain the rope in permanent state, the operator [ ] returns const reference, but there is a special method to overcome it. This solution works with the same speed. Futhermore, I forgot to mention that all iterators are RandomAccess.

If you test this container, please, tell about your experience in comments. In my opinion, we got a pretty fast array with complexity for all operations :)