C++, 재사용을위한 가장 빠른 STL 컨테이너 {delete [begin], insert [end] 및 전체 배열 내용 합계}

Question

각 코드에서 반복되는 첫 번째 요소를 삭제하고 끝에 요소를 추가하는 배열이 있습니다. 그런 다음 배열의 내용을 합산하십시오. 당연히 배열은 같은 크기를 유지합니다. 나는 vector와 list 모두를 사용하려고 시도했지만, 둘 다 꽤 느린 것처럼 보인다.

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

효율적 추가 및 컨테이너의 마지막 요소의 삭제는 deque을 위해 만들어진 것입니다.

당신이 한 말에 삽입 한 다음이 queue

Answer 2

누계를 sum -= l_int.front(); sum += z으로 유지하지 않으시겠습니까?

또한 당신이 삭제로 찾고있는 데이터 구조/삽입 성능이 queue