Добрый день.
Необходима следующая реализация:

Подумалось, что можно заменить данный код следующим:

если само добавление в начало отрабатывает быстро, то очень долгим оказывается работа [] в deque. Поэтому последний код оказался значительно хуже. В разы хуже.
Далее появилась версия использовать следующий подход:

Который оказался хуже первого варианта где-то в 2 раза.
Может кто-нибудь подскажет, почему deque, который по идее должен работать быстрее,так как не требует копирования всех элементов и который имеет констаннтное время доступа по [] требует значительно больше времени.
Заранее благодарен.

А кто тебе гарантировал, что время исполнения operator[] у deque будет таким же, как и у vector? В документации сказано, что оно константно.
Я бы тебе рекомендовал использовать queue... Очередь больше подходит для твоих целей.

Никто. Собственно в этой константе и хочется разобраться. У меня по прикидке разница в десятки раз по скорости.



Не подходит, нужен random access к элементам.

В качестве примера, вот такой вот бессмысленный код:


На выходе получается следующее
vector:93
vector2:235
deque:672

Почему vector2 и deque ведут себя настолько плохо?

Это сообщение отредактировал(а) kokorins - 22.8.2008, 16:51

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

Добавлено @ 19:44
вот здесь

случайный доступ совсем не нужен, можно использовать банальный std::copy, какой алгоритм нужно реализовать?


Это сообщение отредактировал(а) Lazin - 22.8.2008, 19:45

ну если уж использовать вектор, то сдвигать никакого смысла нету
раз количество элементов константно, то можно просто представить вектор в виде циклического буфера, доступ, к которому будет в виде val[(i+shift)%val.size()], тогда операция pop_back/push_front будет простым перезаписыванием элемента и увеличением shift

Иногда, когда требуется отдавать куда-то именно последовательность чисел, можно воспользоваться модификацией варианта, описанного maxim1000: выделить памяти, например, в 2 раза больше, чем нужно, и новое число - дописывание в конец, а когда дойдём до конца - перезапись. Т.е. здесь перезапись для массива из N элементов делается в N раз реже. Оформляется это в виде класса, инкапсулирующего все тонкости реализации.