std :: vector vs std :: insert

Question

비교적 작은 크기 (5 ~ 20 개 요소)의 정렬 된 std::vector이 있습니다. 데이터가 연속적이므로 std::vector을 사용 했으므로 캐시 때문에 속도가 있습니다. 특정 시점에서이 vector에서 요소를 제거해야합니다.

나는 다음과 같은 두 가지 옵션 중에서이 값을 제거하는 가장 빠른 방법입니다.

1. 0으로 그 요소를 설정하고 재정렬 sort 호출이 복잡성을 갖지만 요소는 동일한 캐시 라인에있다.
2. 1 개 (모든 지우개를 조사해야 함) 이후에 모든 요소를 ​​복사 (또는 누가 아는 지 memcpy)하겠습니까? erase으로 전화하십시오.

어느 것이 더 빠릅니까?

나는 동일한 접근법이 벡터의 최대 용량에 부딪치지 않고 새로운 요소를 삽입하는 것에 대해 생각할 수 있다고 생각한다.

감사

AFG

Answer 1

당신이 요소의 순서 상관하지 않는 경우, 당신은 마지막으로 요소를 교체 할 수 있습니다. 당신이 순서에 대해 신경 경우의 다음 두 번째 옵션을

void Remove(std::vector<Object *> &vec, iterator i) { 
    vec[i] = vec.back(); 
    vec.erase(vec.end()-1); 
} 

:

void Remove(std::vector<Object> &vec, iterator i) { 
    iterator last = vec.end()-1; 
    if (i != last) 
     std::swap(*i, *last); 
    vec.erase(last); 
} 

당신은 당신이 포인터를 가지고, 당신은 스왑이 필요하지 않을 수 있습니다 의미합니다 경우 0으로 요소를 설정 언급 erase()를 사용하면이를 보존하고 최소한의 작업을 수행 할 수 있습니다. 그것은 거의 확실하게 재결합보다 빠를 것입니다.