ищу контейнер доступ по индексу o(log n) вставка в произвольном месте o(log n)

[Nik]

Вектор классная штука, но при вставке/удалении из середины тормозит.
Вроде на поверхности лежит решение - в одном векторе хранить указатели на вектора куски общих данных, и при вставке в середину переносить нужно будет только элементы этого небольшого куска. Конечно это немного замедлит доступ по индексу, но это устраивает.
Не хочется изобретать велосипед, известно ли кому-нибудь готовое решение?

[alexman]

QList не устроит?

[alexman]

From Qt Assistant:
QList<T> is one of Qt's generic container classes. It stores a list of values and provides fast index-based access as well as fast insertions and removals.

[Nik]

Забавно, получается QList совсем не то же что std::list погляжу реализацию... Покрайней мере на тестах он оказался быстрее QVector в 5 раз. Однако вставка в 100 отдельных векторов все равно быстрее на 2 порядка.

Код:

QBENCHMARK {
        qsrand(0);
        for (int i = 0; 1000000 != i; ++i)
        {
            qint64 data = qint64(qrand()*65535);
            QVector<qint64>::iterator itr = qLowerBound(vect.begin(), vect.end(), data, qLess<qint64>());
            vect.insert(itr, data);
        }
    }
//отработало за 2273251 msecs

    QBENCHMARK {
        qsrand(0);
        for (int i = 0; 1000000 != i; ++i)
        {
            qint64 data = qint64(qrand()*65535);
            QList<qint64>::iterator itr = qLowerBound(list.begin(), list.end(), data, qLess<qint64>());
            list.insert(itr, data);
        }
    }
//отработало за 456601 msecs

QBENCHMARK {
        qsrand(0);
        for (int i=0; 100 != i; ++i)
        {
            vect_of_vect.push_back(new QVector<qint64>());
        }
        for (int i=0; vect_of_vect.size() != i; ++i)
        {
            for (int j = 0; 10000 != j; ++j)
            {
                qint64 data = qint64(qrand()*65535);
                QVector<qint64>::iterator itr = qLowerBound(vect_of_vect[i]->begin(), vect_of_vect[i]->end(), data, qLess<qint64>());
                vect_of_vect[i]->insert(itr, data);
            }
        }
    }
//однако отработало за 9052 msecs 

[alexman]

Так если вы будите вставлять элемент в середину (чтобы порядок элементов сохранился), то это займет время!

[Nik]

Так если вы будите вставлять элемент в середину (чтобы порядок элементов сохранился), то это займет время!

да, но не такое большое, просто если после очередной вставки данный кусок контейнера полностью заполнен (например до 10000 элементов) - разделить его на два заполненных на половину (сохраняя упорядоченность естественно, сначала элементы первого вектора, затем второго и т.д.). Поэтому я и пробовал вставку в 100 векторов по 10000 элементов и сравнивал с одним вектором в 1000000.

[Igors]

да, но не такое большое, просто если после очередной вставки данный кусок контейнера полностью заполнен (например до 10000 элементов) - разделить его на два заполненных на половину (сохраняя упорядоченность естественно, сначала элементы первого вектора, затем второго и т.д.). Поэтому я и пробовал вставку в 100 векторов по 10000 элементов и сравнивал с одним вектором в 1000000.

А как Вы спрыгнете на нужный блок по индексу если могут быть не полностью заполненные блоки?

[Nik]

А как Вы спрыгнете на нужный блок по индексу если могут быть не полностью заполненные блоки?

Ну у каждого блока ведь хранится его размер - если индекс больше размера блока, переходим к следующему а из индекса этот размер вычитаем, конечно выборка поэтому будет уже не o(1), а примерно o(log n), но это устраивает.

[Igors]

Ну у каждого блока ведь хранится его размер - если индекс больше размера блока, переходим к следующему а из индекса этот размер вычитаем, конечно выборка поэтому будет уже не o(1), а примерно o(log n), но это устраивает.

Хмм... не уверен что устроит. Обычно обращения по индексу очень часты. А у Вас получается надо последовательно перебрать половину блоков (N/2) чтобы добраться до элемента.

Когда-то (давно) пытались понять как СУБД строит индекс - очень похоже на то что Вы хотите. Контейнер конечно был бы интересный но совсем не простой. Если не очень надо - то просто QList. Или свой контейнер но с добавлением только в конец - там все намного проще. И/или с "заполнением дырок".   

Не хочется изобретать велосипед, известно ли кому-нибудь готовое решение?

Готовые решения охотно предлагаются для простых случаев. А если, как у Вас, хоть что-то нетривиально - критика велосипедов быстро умолкает 

[Nik]

Когда-то (давно) пытались понять как СУБД строит индекс - очень похоже на то что Вы хотите. Контейнер конечно был бы интересный но совсем не простой.

Да практически для этих целей контейнер такой и ищется. Индексировать БООЛЬШОЙ контейнер с данными по разным полям. Чтож, жаль что готового нету конечно... еще немного поищу и буду делать велосипед наверно )

[kamre]

Индексировать БООЛЬШОЙ контейнер с данными по разным полям. Чтож, жаль что готового нету конечно...

Может быть boost::multi_index подойдет?