Я думаю, что реализация самого вектора не обязана быть такой, чтобы выделять один длинный буфер на все элементы.
Можно сделать свой гибрид, скажем, список векторов фиксированной длины. Т.е. выделение (и уничтожение) памяти будет происходить сегментами. Главное, хорошо подобрать размер сегмента.