Старый поток, но он появился на столе сотрудника в качестве первого результата поиска для запроса Google.
Существует одна альтернатива использованию дека, который стоит рассмотреть:
std::vector<T> foo;
for (int i = 0; i < 100000; ++i)
foo.push_back(T());
std::reverse( foo.begin(), foo.end() );
Вы по-прежнему используете вектор, который значительно более развит, чем deque для производительности. Кроме того, свопы (которые используются в обратном порядке) довольно эффективны. С другой стороны, сложность, хотя и линейная, увеличивается на 50%.
Как всегда, измерьте, прежде чем решать, что делать.