몇 개의 삽입 작업을 수행 할 때 어떤 stl 컨테이너를 사용해야합니까?

Question

정확한 숫자를 모르지만 최선을 다할 것입니다. 나는 처음부터 채워진 10000 엘리먼트 deque를 가지고있다. 각 요소를 스캔하고 20 개 요소마다 새 요소를 삽입해야합니다. 인서트는 현재 위치에서 일어나고 아마도 한 요소 뒤로 이루어집니다.

위치를 기억할 필요가 없지만 임의 액세스가 필요하지 않습니다. 빨리 삽입하고 싶습니다. deque와 vector는 삽입물에 대해 지불해야하는 비용이 많이 듭니까? 내가 목록을 써야 할까?

내 다른 옵션은 두번째 deque 목록을 가지고 있으며, 내가 삽입 할 필요가 없다면 각 요소를 다른 deque 목록에 삽입하는 것입니다. 이것은 성능 집약적 인 응용 프로그램으로서 빠를 필요가 있습니다. 하지만 나는 포인터를 많이 사용하고 있습니다 (각 요소는 포인터입니다) 나를 괴롭 히고 있지만 주위에 방법이 없습니다 그래서 L1 캐시가 항상 놓칠 것이라고 가정해야합니까?

Answer 1

나는이 경우 std::vector, 시작 싶지만은 대량 돌연변이의 두 번째 std::vector, reserve() 적절하게 다음 swap() 벡터를 사용합니다.

업데이트

그것은이 일반적인 형태 걸릴 것 :

Borealid 좋은 점, 측정이 제기

std:vector<t_object*> source; // << source already holds 10000 elements 

std:vector<t_object*> tmp; 

// to minimize reallocations and frees to 1 and 1, if possible. 
// if you do not swap or have to grow more, reserving can really work against you. 
tmp.reserve(aMeaningfulReserveValue); 

while (performingMassMutation) { 
    // "i scan through each element and lets every 20 elements" 
    for (twentyElements) 
    tmp.push_back(source[readPos++]); 

    // "every 20 elements i'll need to insert an new element" 
    tmp.push_back(newElement); 
} 

// approximately 500 iterations later… 

source.swap(tmp); 

- 실행이 극적으로 당신의 표준 라이브러리 구현에 따라 달라집니다를, 데이터를 크기, 복사 복잡성 등이 있습니다. 컬렉션 원시 포인터 용

는 내 구성이 크기는 질량 vector 돌연변이는 상기 push_backstd::list 삽입보다 7 배 더 빨랐다. push_back은 vector의 범위 삽입보다 빠릅니다.

Emile이 아래에서 지적한 것처럼 std::vector::swap()은 요소를 이동하거나 다시 할당 할 필요가 없습니다. 즉, 내부자를 교환 할 수 있습니다 (할당자가 동일한 유형 인 경우).

Answer 2

먼저 모든 성능 질문에 대한 대답은 "벤치마킹"입니다. 항상. 당신은 메모리 오버 헤드에 대한 상관 없어, 당신은 랜덤 액세스가 필요하지 않습니다,하지만 당신은 일정 시간의 삽입을하는 것에 대한 관리를 할 경우 지금 ...

는 list 아마 당신을위한 권리입니다.

std::vector은 용량이 충분할 때 끝에 일정한 시간의 삽입 을 갖습니다. 용량이 초과되면 선형 시간 복사가 필요합니다. deque은 이산 할당을 연결하고 전체 복사본을 피하고 정면에서 일정 시간 삽입을 수행하기 때문에 더 좋습니다. 무작위 삽입 (20 개 요소마다)은 항상 선형 시간입니다.

캐시 지역에 관해서는 vector은 얻을 수있는만큼 좋으며 (연속 메모리), 검색보다는 삽입에 관심이 있다고합니다. 내 경험에 따르면, 그 때 당신은 덤프를 통해 스캔으로 캐시가 얼마나 뜨거워 지는지 상관하지 않기 때문에 list의 가난한 행동은별로 중요하지 않습니다.

Answer 3

목록은 자주 컬렉션의 중간에 요소를 삽입하거나 자주 제거하려는 경우에 유용합니다. 그러나 목록은 읽기가 느립니다.

컬렉션의 끝에 요소를 추가하거나 제거하려는 경우 벡터는 매우 빠르게 읽고 매우 빠르지 만 가운데에 요소를 삽입하면 매우 느립니다. 원하는 위치 다음에 오는 모든 요소를 ​​한 위치 씩 이동시켜야하므로 새 요소를위한 공간을 마련해야하기 때문입니다.

Deques는 기본적으로 벡터로 사용할 수있는 이중 연결 목록입니다.

컬렉션의 중간에 요소를 삽입 할 필요가없는 경우 (순서는 신경 쓰지 않음) 벡터를 사용하는 것이 좋습니다. 벡터에 처음 도입 될 요소의 수를 대략적으로 계산할 수있는 경우 처음부터 필요한 메모리를 할당하려면 std::vector::reserve을 사용해야합니다. reserve에 전달하는 값은 근사치 일 필요는 없습니다. 필요 이상으로 작 으면 벡터는 필요할 때 자동으로 크기가 조절됩니다.

Answer 4

두 가지 방법이 있습니다. 목록은 항상 임의의 위치 삽입을위한 옵션이지만 모든 요소를 ​​개별적으로 할당하면 성능에 영향을 미칩니다. deque에 현재 위치를 삽입하는 다른 옵션은 좋지 않습니다. 삽입 할 때마다 선형 시간을 지불해야하기 때문입니다. 어쩌면 새로운 양 큐잉에 삽입하는 당신의 아이디어는 여기에서 최고입니다 - 당신은 두 배의 메모리를 지불하지만, 반면에 항상 두 번째 양 끝의 끝에 삽입하거나 한 요소를 삽입하는 것입니다 - 이것은 모두 일정한 상각 시간을줍니다 , 그리고 여전히 당신은 컨테이너의 좋은 캐싱을 가지고있다.

Answer 5

당신은 vector 및 deque 당신을 위해 확실히하지, 중간에 빠른 삽입이 필요하지만, 랜덤 액세스에 대해 걱정하지 않는 경우 : 사람들을 위해, 때마다 당신이 뭔가를 삽입, 그 하나는 끝 사이의 모든 요소를 움직여야 해. 붙박이 콘테이너의, list는 거의 확실히 당신의 최선의 방법이다. 그러나 시나리오의 데이터 구조는 VList 일 가능성이 높으므로 더 나은 캐시 위치를 제공하기 때문에 C++ 표준 라이브러리에서는 제공하지 않습니다. Wikipedia 페이지는 C++ 구현으로 링크되지만, 인터페이스에서의 빠른 뷰에서는 완전히 STL과 호환되지 않는 것처럼 보입니다. 이것이 당신에게 문제가되는지 나는 모른다.

물론 결국 최적의 솔루션인지를 확인하는 유일한 방법은 성능을 측정하는 것입니다.

Answer 6

std::vector/deque ::insert 등의 복사 횟수는 삽입 위치와 컨테이너 끝 사이의 요소 수 (공간을 만들기 위해 이동해야하는 요소 수)에 비례합니다. std::vector의 최악의 경우는 O(N) - 컨테이너 앞쪽에 넣을 때입니다. M 요소를 삽입하는 경우 최악의 경우는 O(M*N)이며 그다지 좋지 않습니다.

컨테이너 용량을 초과하면 재 할당이 발생할 수 있습니다. 충분한 공간이 ::reserve 'd 앞에 있는지 확인하여 재 할당을 방지 할 수 있습니다.

다른 제안 사항 - 두 번째 컨테이너로 복사하면 O(N)의 복잡성을 달성하기 위해 항상 구성 할 수 있지만 두 개의 컨테이너를 일시적으로 저장하는 대신에 더 편리 할 수 ​​있습니다.

std::list을 사용하면 삽입 포인터 O(1)을 삽입 할 수 있지만 추가 메모리 오버 헤드 (목록 포인터 등 저장) 및 메모리 위치 감소 (목록 노드가 연속적으로 할당되지 않음)가 발생합니다. pool'd 메모리 할당자를 사용하여 메모리 위치를 향상시킬 수 있습니다 (Boost pools?).

전반적으로 "가장 빠른"접근 방식을 실제로 분류하려면 벤치 마크해야합니다.

희망이 도움이됩니다.