[Effective STL] 14. vector reserve

항목 14. reserve는 필요 없이 메모리가 재할당되는 것을 막아준다

 

 

 

vector와 string의 메모리 증가

• 아래의 네 단계 동작을 통해 재할당(realloc)이 진행된다.(할당-복사-소멸-해제)
  1. 컨테이너의 현재 용량의 몇 배가 되는 메모리 블록을 새로 할당한다.(대부분 2배)
  2. 컨테이너가 원래 가지고 있던 메모리에 저장된 모든 요소 데이터(객체)를 새 메모리에 복사한다.
  3. 원래 메모리에 저장된 모든 객체를 소멸(destroy) 시킨다.
  4. 원래의 메모리를 해제(dealloc)한다.
• 상당한 비용이 든다.
• 매 단계마다 반복자, 포인터, 참조자가 무효화된다.

 

 

 

STL에서 헷깔리는 네 가지 함수

• size()
  • 현재 컨테이너에 들어 있는 요소의 갯수를 알려준다.
  • 메모리 총 갯수가 아니다.
• capacity()
  • 현재 컨테이너에 할당된 메모리에 담을 수 있는 총 요소 갯수
  • 총 요소 갯수이지, 남은 공간 갯수가 아니다.
• resize(size_t)
  
  • 강제로 컨테이너 요소의 개수를 n개로 만든다.
  • 호출 후 size()를 호출하면 n이 리턴된다.
  • n이 현재의 요소 수보다 작으면 컨테이너 끝 쪽에 있는 요소는 모두 소멸된다.
  • 반대의 경우, 기본 생성자로 생성된 빈 요소가 컨테이너 끝에 추가된다.
  • n이 현재 할당된 메모리보다 크면 재할당 후 기본 생성 요소를 추가한다.
• reserve(size_t)
  • 컨테이너의 메모리를 최소 n개로 맞춘다.
  • n이 현재 할당된 메모리보다 크면 재할당이 일어난다.
  • 작으면 아무 일도 일어나지 않는다.

 

 

 

reserve를 사용하여 재할당을 줄이자

// reserve를 사용하지 않은 경우
{
    vector<int> v;
    for(int i = 1 ; i <= 1000 ; ++i)
    {
        v.push_back(i); // 최소 2번, 최대 1000번의 재할당이 발생
    }
}

// reserve를 사용하여 수정
{
    vector<int> v;
    v.reserve(1000);
    for(int i = 1; i <= 1000 ; ++i)
    {
        v.push_back(i); // 재할당이 한번도 발생하지 않는다.
    }
}

 

• size와 capacity의 관계를 생각해보면, 요소 삽입시 vector나 string에서 재할당이 일어나는 시기가 언제인지 충분히 예측할 수 있다.
  • 즉, 반복자, 포인터, 참조자가 언제 무효화되는지 예측 가능하다.

string s;
...
if(s.size() < s.capacity())
{
    s.push_back('x'); // 재할당이 일어나지 않는다.
}
// 그러므로 위 코드는 반복자, 포인터, 참조자 무효화가 발생하지 않는다.
// 헌데, push_back 대신 insert 를 사용하여 문자열 중간에 문자를 삽입하려 한다면?
// 재할당은 일어나지 않지만, 반복자, 포인터, 참조자 무효화는 발생한다.

 

 

 

정리

• reserve를 써서 불필요한 재할당을 피하는 방법
  1. 컨테이너에 저장되는 요소의 개수를 얼추 파악하고 있다면, reserve 한다.
  2. 필요한 최대량을 미리 reserve 한 후, 나중에 데이터를 모두 넣고 남은 용량을 잘라낸다.(항목 17 참조)