Обязательно линейная структура, по типу вектора. Две основные операции: добавить и удалить. Удаление элемента возможно из любого места, но на деле память под вектором не перераспределяется, а просто освобождаемый участок помечается как «свободен». При добавлении элемента автоматически выбирается либо первая дырка, либо конец вектора (при отсутствии дырок). Наверное хорошо бы опционально при достижении определенного критического процента дырок опять сшивать вектор воедино.
Интересует название такого типа - даже если написать его самому. Пока в голову приходит только романтичное holed_vector.
