알 수없는 크기의 std :: vector를 채우는 가장 빠른 방법

Question

데이터 배열이 길어졌습니다 (n 엔티티). 이 배열의 모든 객체에는 몇 가지 값이 있습니다 (객체에 대해 m 값이라고 가정 해 봅시다). 난 N *미터 유효한 오브젝트가 어떤 경우

myType* A; 

// reading the array of objects 
std::vector<anotherType> targetArray; 
int i, j, k = 0; 
for (i = 0; i < n; i++) 
    for (j = 0; j < m; j++) 
    { 
     if (check((A[i].fields[j])) 
     { 
      // creating and adding the object to targetArray 
      targetArray[k] = someGenerator(A[i].fields[j]); 
      k++; 
     } 
    } 

일부 (N *m)/10 이하의 경우 : I과 같은주기를 갖는다.
질문은 어떻게 targetArray에 대한 메모리를 할당합니까?

targetArray.reserve(n*m);
// Do work
targetArray.shrink_to_fit();

1. 은 생성 객체없이 요소를 계산하고, 내가 필요로하는 다음과 같은 많은 메모리를 할당하고 사이클을 한 번 더 함께 할 것입니다.

2. 새 개체가 생성되는 모든 반복마다 배열의 크기를 조정하십시오.

나는 각각의 방법에서 거대한 전술적 실수를 본다. 그것을하는 또 다른 방법이 있습니까?

Answer 1

여기서 뭘하는지 조기에 최적화라고합니다. 기본적으로 std::vector은 새 개체를 저장하기 위해 메모리가 부족하여 메모리 사용 공간을 기하 급수적으로 늘립니다. 예를 들어, 첫 번째 push_back은 2 개의 요소를 할당합니다. 세 번째 push_back은 크기를 두 배로 늘릴 것입니다. push_back을 붙잡고 코드 작동을 얻으십시오.

위의 방법으로 설계에서 병목 현상이 발생한 경우에만 메모리 할당 최적화에 대해 생각해보십시오. 그럴 경우 최선의 방법은 여러 유효한 객체에 대한 좋은 근사값을 산출하고 벡터에 reserve()을 호출하는 것입니다. 첫 번째 접근 방식과 비슷한 점이 있습니다. 벡터 축소를 원하지 않기 때문에 구현에 맞게 축소해야합니다. swap을 사용해야합니다.

모든 단계에서 배열 크기를 조정하는 것은 좋지 않으며 열심히 시도하지 않는 한 std::vector은 실제로 그렇게하지 않습니다.

개체 목록을 통해 추가주기를 수행하면 도움이되지만 쉽게 CPU주기를 낭비하고 CPU 캐시를 부 풀릴 수 있으므로 문제가 될 수 있습니다.

Answer 2

일반적인 방법은 targetArray.push_back()을 사용하는 것입니다. 이렇게하면 필요할 때 메모리를 재 할당하고 데이터를 두 번 통과하지 않아도됩니다. 벡터를 더 효율적으로 사용할 수 있도록 메모리를 재 할당하는 시스템이 있습니다. 벡터가 커짐에 따라 재 할당을 줄입니다.

그러나 check() 함수가 매우 빠르면 데이터를 두 번 이동하여 필요한 메모리 양을 결정하고 벡터를 올바른 크기로 만드는 것이 더 좋습니다. 프로파일 링이 실제로 필요하다고 결정한 경우에만 이것을 수행합니다.