Vector vs deque

Добрый день.Необходима следующая реализация:
vector<******> val(5)//Длина в принципе фиксированнаяwhile(очень много раз){    for (int i=val.size()-1; i>0; --i) //сдвигаем элементы на один    {        val[i]=val[i-1];    }    val[0]=somefunc(val);    someuse(val);}
Подумалось, что можно заменить данный код следующим:
deque<******> dal(5)//Длина в принципе фиксированнаяwhile(очень много раз){    dal.pop_back();    dal.push_front(somefunc(dal));;    someuse(val);}
если само добавление в начало отрабатывает быстро, то очень долгим оказывается работа [] в deque. Поэтому последний код оказался значительно хуже. В разы хуже.Далее появилась версия использовать следующий подход:
vector<******> val(5)//Длина в принципе фиксированнаяwhile(очень много раз){    copy(val.rbegin()+1,val.rend(),val.rbegin());    val[0]=somefunc(val);    someuse(val);}
Который оказался хуже первого варианта где-то в 2 раза.Может кто-нибудь подскажет, почему deque, который по идее должен работать быстрее,так как не требует копирования всех элементов и который имеет констаннтное время доступа по [] требует значительно больше времени.Заранее благодарен.
5 ответов

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


А кто тебе гарантировал, что время исполнения operator[] у deque будет таким же, как и у vector? В документации сказано, что оно константно.
Никто. Собственно в этой константе и хочется разобраться. У меня по прикидке разница в десятки раз по скорости.
Я бы тебе рекомендовал использовать queue... Очередь больше подходит для твоих целей. 
Не подходит, нужен random access к элементам.В качестве примера, вот такой вот бессмысленный код:
#include <ctime>#include <iostream>#include <vector>#include <deque>using namespace std;void assignSome(****** val, ******&a){    a=val;}int main() {    long length = 10000000;    vector<******> val(5);    deque<******> dal(5);    ****** a;    clock_t start=clock();    for (long iter = 0; iter<length; ++iter) {        for (int i=val.size()-1; i>0; --i) {            val[i]=val[i-1];        }        val[0]=0;        for (size_t i=0; i<val.size(); ++i) {            assignSome(val[i],a);        }    }    std::cout<<"vector:"<<clock()-start<<endl;    start=clock();    for (long iter = 0; iter<length; ++iter) {        copy(val.rbegin()+1,val.rend(),val.rbegin());        val[0]=0;        for (size_t i=0; i<val.size(); ++i) {            assignSome(val[i],a);        }    }    std::cout<<"vector2:"<<clock()-start<<endl;    start = clock();    for (long iter = 0; iter<length; ++iter) {        dal.pop_back();        dal.push_front(0);        for (size_t i=0; i<dal.size(); ++i) {            assignSome(dal[i],a);        }    }    std::cout<<"deque:"<<clock()-start<<endl;    return 0;}
На выходе получается следующееvector:93vector2:235deque:672Почему vector2 и deque ведут себя настолько плохо?


ожет кто-нибудь подскажет, почему deque, который по идее должен работать быстрее,так как не требует копирования всех элементов и который имеет констаннтное время доступа по [] требует значительно больше времени.
в общем дек, это массив буферов фиксированого размера, сначала вычисляется индекс буфера, потом индекс внутри буфера, в общем уровень косвенности выше, куча вычислений, а вектор - просто массив элементов...Добавлено @ 19:44вот здесь
        for (size_t i=0; i<dal.size(); ++i) {            assignSome(dal[i],a);        }
случайный доступ совсем не нужен, можно использовать банальный std::copy, какой алгоритм нужно реализовать?


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


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