Я недавно сделал своё маленькое изобретение: структуру с произвольным доступом, скромно названную IgushArray, которая как массив имеет быструю константную операцию доступа, но операция вставки/удаления занимает всего лишь O (N^1/2). Структура может рассматриваться как “быстрый массив” или “массив с быстрой операцией вставки”.

Подробное описание можно найти здесь http://igushev.ru/papers/igusharray/

Прошу любые комментарии или отзывы (особенно если вы где-то это примените)!