item14 : Use reserve to avoid unnecessary reallocations.

STL의 사용에 있어 장점으로 다가오는 점 한가지는

c style의 배열과 달리 크기를 동적으로 할당함으로써 생산성을 높일 수 있고

메모리 사용에 있어 안정성을 높일 수 있다는 점 입니다

(물론 배열과 달리 여러가지 멤버함수와 알고리즘을 사용할 수 있는 장점도 있습니다.)

하지만 이러한 편리성을 지나치게 맹신한체 STL의 기본 동작들을 간과 한다면

불필요한 시간, 공간의 낭비를 초래하게됩니다.

이번장은 이러한 문제를 방지하기 위한 장입니다.

제목과 같이 "불필요한 재할당을 방지하기 위해 resever를 사용하자"입니다.

STL은 기본적으로 할당된 공간이 가득차면 재할당에 있어 다음 전략을 취하고 있습니다.

1. container의 capacity가 모두 찬 상태에서 새로운 공간이 요구되면( 새로운 원소를 삽입한다면)

container의 현재의 capacity보다 더 큰 공간의 메모리를 확보합니다.

C98에서는 두배의 공간을 확보하는것으로 보이나 C11부터는 50%씩 증가하는것으로 변경되었습니다.

실제로 디버깅해보면 내부에서 grow_to 함수에서 50%만을 증가시킴을 알 수 있습니다.

2.  old memory에 존재하는 원소들을 새로 할당된 공간에 copy constructor를 통해 복사합니다.

3. old memory의 객체(원소)의 소멸자를 호출하여 제거합니다.

4. old memory를 deallcation합니다.

이러한 과정은 다음 예제에서 확인할 수 있습니다.

--

--

위의 예제의 결과는 다음과 같습니다.

이 예제는 item3에서도 비슷하게 다루었습니다만,

어쨋든 출력결과를 보면 어렵지 않게 그 과정을 헤아릴 수 있습니다.

이 과정이 위의 순서인 1,2,3을 잘 따르고 있다는 점이죠.

또 내부적으로 deallocation역시 이루어지고 있습니다.

맨 마지막 결과 3줄은 vector에 최종 할당된 원소 세개가 소멸자가 호출되었기 때문에 출력된것입니다.

(vector가 선언된 scope, 그러니까 main함수가 끝났으므로 vector가 소멸되어 객체들의 소멸자가 호출 됨)

추가적으로 reallocation에 따른 reference, pointer, iterator의 invalidation까지 발생하게 됩니다.

이러한 낭비들을 방지하기 위해 stl에서는 vector, string, deque에 reserve member function을 지원합니다.

더 자세한 설명을 위해 우선 용어 정리를 하겠습니다.

1. size

현재 container가 소유하고 있는 객체의 갯수.

2. capacity

현재 container에 할당 하능한 객체의 갯수

즉 size=capacity라면 꽉 찬 상태이며

size < capacity라면 capacity-size만큼 객체를 더 삽입할 수 있는 상태.

3. resize

강제로 container의 capacity크기를 변경하는 함수.

(1) resize < size

size-resize크기만큼 객체를 삭제하고 (소멸자 호출)

capacity = resize가 됨.

(2) size < resize < capacity

resize-size만큼 의 객체를 기본생성자를 통해 container를 체움.

(3) capacity < resize

resize만큼의 새로운 메모리 공간을 확보 한뒤 이 새로운 공간에 객체들을 복사한 뒤 

이전의 메모리공간 할당을 해제함.

4. reserve

reserve크기만큼의 객체 공간을 할당.

(엄밀히는 sizeof(object)*reserve))

이때 reserve > size라면 아무런 동작을 하지 않음.

실제로 reserve를 통해 공간을 확보하고 객체를 넣게 되면 

capacity크기까지 도달 하기전엔 reallocation이 발생하지 않아 다음과 같은 결과를 볼 수 있게 됩니다.

이렇듯 reserve를 통해 reallocation의 횟수를 줄여 시간이득과 invlidation방지 두가지를 노릴 수 있게 됩니다.