Гибрид массива и списка

[T42]

Вопрос по структурам данных. Кто нибудь знает или может быть видел где нибудь структуру, позволяющую реализовать массив элементов, с возможностью быстрой вставки (добавления) и удаления элемента в любом месте массива и с возможностью быстрого доступа по индексу за время О(log2(n)), или быстрее? Естественно, структура должна быть самобалансирующейся за такое же время или быстрее.

[*PB*]

может быть видел где нибудь структуру, позволяющую реализовать массив элементов, с возможностью быстрой вставки (добавления) и удаления элемента в любом месте массива

Не знаю это ли имелось в виду.
Код на PureBasic

Structure MyList
  List MyList.l()
EndStructure

Dim MyArray.MyList(10)

Создается массив структур и в каждом элементе массива будет динамически связанный список, размер которого ограничен лишь доступным объемом оперативной памяти.

[T42]

Нет, имелось ввиду, структура не как тип данных, а как некоторая модель хранения и организации. В любом случае, вопрос уже решен. Решение находится в области деревьев с неявными индексами (ключами).

[_Ч_]

мапина? std::map<int, object>?

[T42]

Не совсем. В std::map реализовано красно-черное дерево с фиксированными ключами. В найденном решении ключи динамические, что позволяет использовать их в качестве индексов. Если интересно, схожее решение описано в статье про неявное декартово дерево: http://e-maxx.ru/algo/treap.