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