C ++, самый быстрый STL-контейнер для рекурсивного выполнения {delete [begin], insert [end] и суммирования всего содержимого массива}

Question

У меня есть некоторый код и массив, в котором на каждой итерации я удаляю первый элемент, добавляю элемент в конце, а затем суммирую содержимое массива.Естественно, массив остается того же размера.Я пытался использовать и вектор, и список, но оба выглядят довольно медленно.

int length = 400;

vector <int> v_int(length, z);
list <int>   l_int(length, z);

for(int q=0; q < x; q++)
{
    int sum =0;

    if(y)                       //if using vector
    {      
        v_int.erase(v_int.begin());    //takes `length` amount of time to shift memory
        v_int.push_back(z);   
        for(int w=0; w < v_int.size(); w++)
            sum += v_int[w];
    }      
    else                        //if using list
    {
        l_int.pop_front();             //constant time
        l_int.push_back(z);
        list<int>::iterator it;
        for ( it=l_int.begin() ; it != l_int.end(); it++ ) //seems to take much  
            sum += *it;                                    //longer than vector does
    }
}

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

Есть ли лучший контейнер для использования здесь?или другой способ решения проблемы?

Answer 1

Почему бы не сохранить текущую сумму с sum -= l_int.front(); sum += z?

Кроме того, структура данных, которую вы ищете для этой производительности удаления / вставки, представляет собой queue

Answer 2

Эффективное добавление и удаление конечных элементов в контейнере - это то, для чего была создана deque .

Если вы просто вставляете на одном конце и удаляете на другом, тогда вы можете использовать очередь