Hello, guys! I decided to study template metaprogramming in C++, so I started with a simple task (it's a classic dynamic programming problem in Russia). And I got the following solution as a result.

It's compiled pretty fast if N·M ≤ 30 and works, for example, when N = 5 and M = 100 (but it can't be used to calculate answers for a bigger values, because the depth of instantiation doesn't exceed 900 in GNU C++). This solution works correctly, but I have several questions. As you can see, the template metaFor is instantiated for all values m, mask and cur_mask. But this argument cur_mask is just a simple loop counter. Is there any way to exclude it from arguments of the template without losing the ability to use it for iterating? If it could be done, this program would be able to calculate answers for much bigger N and M. And how can I speed up the above solution?

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 :)