Ну, без дырок совсем не получится. Во-первых, сами структуры могут быть с дырками из-за выравнивания. Потом, не любой тип можно положить куда угодно, опять же, из-за выравнивания. Далее, при удалении будут образовываться дырки, которые не факт что и можно заполнить (без медленного перелопачивания всей структуры).
Евгений Шатунов правильно говорит, что это уже алгоритм аллокатора получается, а не структура данных. Ну а дальше, можно как-то выделять сырую память под ваши элементы, и в соседнем векторе указателей хранить где будет лежать i-ый элемент для быстрого доступа.