[C++] vector의 reserve()로 push_back() 시간을 줄이자!

문제 인식

C++ STL의 vector는 push_back()을 통해 배열의 원소를 계속 늘릴 수 있다. 그러나, vector가 처음 선언될 때 예약되어 있던 '용량'을 초과해버리면, 그보다 더 '큰' (2배 정도) 용량의 메모리를 할당한 후 기존의 원소를 모두 복사하고, 기존의 메모리는 해제하는 작업을 거친다.

 

즉, 이 작업에는 할당 -> 복사 -> 해제의 비용이 들어간다.

 

이 작업의 시간 복잡도는 O(1)로 알려져있으나 이는 엄연히 Amotized Analysis 즉, 분할 상환 분석법을 통해 구해진 시간 복잡도일 뿐이며, 최악의 경우 O(N)까지 시간 복잡도가 커질 수 있다.

 

한 마디로, 재할당이 많이 일어나면 일어날 수록 성능이 매우 떨어진다는 의미이다.

실제로 BOJ 문제에서 이로 인해 시간 초과가 발생하기도 한다.

 

문제 해결

만약, 우리가 '아, 이 정도의 크기를 준비해놓으면 되겠구나!'하는 것이 감이 잡힌다면, 그 정도의 용량(capacity)을 미리 확보(예약)해놓으면 재할당을 하지 않아도 된다!

* capacity != size
* vector의 capacity() : 확보해놓은 용량 return
* vector의 size() : 사용하고 있는 공간 return

 

해결 방법으로 reserve() 함수와 resize() 함수가 있는데, 두 함수의 차이는 용량 확보 후 그 공간을 초기화를 하느냐 하지 않느냐의 차이이다.

 

• reserve(N) : N의 용량을 미리 확보해놓음.
• resize(N, number = 0) : N의 용량을 미리 확보해놓고 나머지 공간을 두 번째 매개변수의 값으로 채움. 두 번째 매개변수가 없으면 0

 

예시

• reserve()

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{ 10, 20 };

    cout << v.size() << endl; // 2
    cout << v.capacity() << endl; // 2

    v.reserve(100);
    cout << v.size() << endl; // 2
    cout << v.capacity(); // 100

    return 0;
}

 

• resize()

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{ 10, 20 };

    cout << v.size() << endl; // 2
    cout << v.capacity() << endl; // 2

    v.resize(100);
    cout << v.size() << endl; // 100
    cout << v.capacity(); // 100

    return 0;
}