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(); 来保存运行总和？总和+=z？

此外，您正在寻找具有删除/插入性能的数据结构是队列

Answer 2

deque 的目的是在容器中高效地添加和删除结束元素。

如果您只是在一端插入并在另一端删除，那么您可以使用 队列