C++，最快的 STL 容器，用于递归执行 { 删除 [开始]、插入 [结束] 和对整个数组内容求和}

Question

我有一些代码和一个数组，每次迭代我都会删除第一个元素，在末尾添加一个元素，然后对数组的内容求和。自然地，数组保持相同的大小。我试过同时使用 vector 和列表，但两者看起来都很慢。

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
    }
}

问题是删除 vector 的第一个元素需要将每个其他元素向下移动，乘以 vector 的大小，每次迭代所花费的时间。使用链表可以避免这种情况(恒定时间删除元素)，并且不应牺牲任何时间对数组求和(数组的线性时间遍历)，除了在我的程序中它似乎比对内容求和花费更长的时间vector 确实如此(至少长 1 个数量级)。

这里有更好的容器可以使用吗？还是解决问题的不同方法？

Answer 1

为什么不用 sum -= l_int.front(); 来保持运行总和？总和 += z?

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