deque vs vector

Во всех книжках встречаю "если не знаете какой контейнер использовать - используйте vector". Мне вот что-то не взлюбился этот vector, я вот deque люблю. Точнее ее реализацию, где она реализована в виде страниц и вектора указателей на эти страницы. В дальнейшем буду рассматривать только деку с такой реализацией.

Преимущества deque перед vector:
1. Меньше overhead. Вектор растет сразу в два раза, а дека - фиксированными страницами. Если храним мегабайт с копейкой, то вектор будет двухмегабайтный, а дека - мегабайт плюс маленький хвостик.
2. Отстуствие копирования старого содержимого на новое место при расширении контейнера.

Недостатки:
1. Отсутствие доступа к содержимому как к линейному массиву.

Инкремент-декремент итераторов у деки по скорости сравнимы с векторными, произвольный доступ к элементам - аналогично.

А вот отсутствие ненужного копирования при realloc-е у деки существенно улучшает performance.

Достоинство вектора - доступ к содержимому как к линейному массиву. То есть можно накопить кучу данных в векторе, а потом передать все содержимое какой-нибудь API-шной функции типа WriteFile или SendData с параметрами (void *buf, size_t size).

Но это является плюсом вектора только в теории. Сравним два варианта:
1. Накапливаем данные в vector, затем за один вызов "сливаем" их в нашу WriteFile(void *buf, size_t size)
2. Накапливаем данные в deque, затем в цикле "сливаем" часть в буфер ограниченного размера, а потом передаем этот буфер нашей WriteFile.

Предполагаем, что изначально мы не знаем сколько элементов придется поместить в контейнер (иначе, естественно, vector::reserve() всех порвёт).

Пусть в результате в контейнер окажутся помещенными N элементов. Ближайшие к N степени двойки назовем 2ⁿ и 2ⁿ⁺¹. То есть 2ⁿ < N <= 2ⁿ⁺¹.

В первом случае на этапе накопления произойдет 1+2+4+8+...+2ⁿ = 2ⁿ⁺¹-1 копирований. Назовем это количество С₁.

Во втором случае будет копирований элементов ровно столько, сколько элементов в контейнере. Происходить все они будут в цикле (когда все они будут копироваться в буфер), а при накоплении данных дек ничего не перекладывает с одного места в другое. Количество копирований C₂=N.

С₁=2ⁿ⁺¹-1 всегда больше С₂=N, кроме двух случаев, которые можно особо не учитывать. А если предположить, что в среднем N где-то посередине межде 2ⁿ и 2ⁿ⁺¹, то второй вариант на 25% быстрее первого.

То есть даже тот факт, что вектор потом можно удобно (без дополнительных копирований) "слить" API-шной функции, не дал вектору преимуществ перед декой.

Исключения: при маленьких N или в случаях, когда N заранее известно - тут вектор выигрывает.