Всем привет! Не буду долгих предисловий тут писать, поэтому сразу к делу. Читая книгу Мейерса "Эффективное использование STL", я вдруг наткнулся на упоминание о наличии в некоторых версиях STL структуры данных rope. Если кратко, то эта структура данных позволяет быстро вырезать/вставлять куски массива в произвольные позиции, аналогично декартовому дереву по неявному ключу (с аналогичной сложностью — подробности смотрите в статье на вики). Она иногда используется для обработки сверхдлинных строк.

Как выяснилось, rope действительно реализована в некоторых версиях STL, например в SGI STL. Сразу замечу, что это наиболее полная документация по классу rope, которую мне удалось найти в сети. А теперь давайте разыщем rope в GNU C++. Поскольку кто-то ранее находил расширенную версию красно-черных деревьев в GNU, я подумал, почему бы и rope где-нибудь не заваляться. Для тестинга я взял вот эту задачу, в которой у меня уже была сдана дерамида по неявному ключу. После недолгого гугления получилось следующее решение:

#include <iostream>
#include <cstdio>
#include <ext/rope> //заголовочный файл с rope
using namespace std;
using namespace __gnu_cxx; //пространство имен, в котором находится класс rope и все, что с ним связано
int main()
{
    ios_base::sync_with_stdio(false);
    rope <int> v; //используем как самый обычный stl контейнер
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        v.push_back(i);
    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;
}

Оно без всяких проблем зашло и уложилось в секунду, что в 2 раза медленнее варианта с рукописным декартовым деревом, но при этом с чуть более оптимальным расходом памяти. Полную документацию по всем методам можно найти по вышеприведенной ссылке на SGI STL. Судя по всему, в GNU полностью аналогичная реализация. Visual C++ как унылое го... не поддерживает rope.

Что касается применения, то есть несколько особенностей. Из документации SGI STL следует, что класс rope плохо дружит с изменениями отдельных элементов последовательности (поэтому методы begin() и end() возвращают const_iterator. Чтобы получить обычный итератор, необходимо вызывать mutable_begin() и mutable_end() соответственно.). Также нельзя просто взять и присвоить значение i-ому элементу последовательности (см. код ниже для подробностей). Но насколько это "плохо", я не знаю. По идее за классический логарифм от числа элементов. В то же время конкатенация (операция +=) вообще работает за O(1) (не считая затрат на создание объекта справа, конечно).

Особенности индексирования можно увидеть в этом коде: http://pastebin.com/U8rG1tfu. Поскольку разработчики очень не хотят, чтобы мы меняли отдельные элементы контейнера, оператор [ ] возвращает ссылку на константу, но специальный метод все же есть. Данный код работает столько же, сколько и предыдущий. И да, забыл упомянуть, что все итераторы RandomAccess, что не может не радовать.

Если кто захочет потестировать контейнер на более серьезных задачах, расскажите в комментариях. По моему ощущению, у нас теперь есть быстрый массив с логарифмическим временем выполнения всех операций и как обычно большой константой :)

UPD: сдал еще задачу. Здесь мало запросов, но последовательность подлиннее. Зашло тоже без проблем. Еще наткнулся на такую особенность, что erase может принимать только 1 индекс типа size_t (хотя метода с такой сигнатурой нет). И я не очень понимаю, что он делает в этом случае. Из-за этого можно случайно набажить, когда нужно удалять 1 элемент.