Vector Capacity를 1.5배씩 늘려주는 이유

C++의 vector는 다양한 연산들이 존재한다 (아래 포스팅 참조)

2jinishappy.tistory.com/67

[STL] vector 생성자, 함수 및 iterator 사용법

정적 array와 비교되는 vector의 가장 큰 장점은 stl 라이브러리 내에서 자동으로 크기를 조절해주고, element들의 추가 및 삭제가 굉장히 용이하다. 또한 다양한 멤버함수들을 제공해줘서 vector를 이용한 다양한 연산을 할 수 있다.

우리는 vector의 자동 크기 조절에 대해 주목해보자

만약 정적 Array를 선언한다면, 배열을 선언할 때 크기를 지정해주어야 한다. 또한 배열의 크기에 들어갈 keyword에는 변수는 들어갈 수 없고 오직 상수만 들어갈 수 있다.

#include <stdio.h>
#define SIZE 10
int main() {
	int k = 10;
	int arr[10];	//상수 크기 배열 선언
	int arr1[k];	//배열의 크기를 변수로 선언할 수 X
	int arr2[SIZE];	//기호상수는 가능
    
    	int* arr3 = (int*)malloc(sizeof(int) * k);	//변수로 배열 크기 설정 가능

	arr = (int*)realloc(arr,sizeof(int) * k * 2);	//배열의 크기 변경 가능
}

위의 코드와 같이, 값이 변할 가능성이 있는 변수로는 배열의 크기를 설정할 수 없다. 그래서 배열의 크기가 가변적이라면(공간이 너무 남거나 부족할 경우) 우리는 malloc 및 realloc 함수를 이용하여 동적 할당된 배열을 사용한다

malloc 및 realloc 함수를 사용하면 배열의 크기를 필요할 때 변경할 수 있다 🤗 또한 이는 vector의 최대 크기를 조정하는데 사용된다 ❗❗

vector에는 size()와 capacity()라는 비슷해보이지만 전혀 다른 두 가지 메서드가 존재한다.

출처: Microsoft https://docs.microsoft.com/ko-kr/cpp/standard-library/vector-class?view=msvc-160#size

size는 현재 벡터 배열 내에 몇 개의 element가 존재하는가를 나타내고
capacity는 현재 벡터 배열에서 재할당 없이 몇 개의 element를 담을 수 있는가

를 나타낸다 

만약 현재 vector의 capacity가 8이고, size가 6이라는건 현재 vector에는 6개의 element가 들어있고, 8개까지 담을 수 있다는 뜻이다.

그렇다면 벡터의 원소가 8개를 넘어가면? (겉으로 보기에는) 아무 일도 일어나지 않는다. 사용자의 입장에서는.

하지만 벡터 내부에서는 capacity의 재할당이 이루어진다 😱 아래의 코드에서는 원소 10000개를 삽입할 때, vector의 capacity가 언제 바뀌는지 테스트해보았다.

#include <iostream>
#include <vector>
using namespace std;
int main() {
	vector<int> v = { 0 };
	int pre=v.capacity(), cur;
	printf("primitive capacity: %d\n", pre);
	for (int i = 0; i < 10000; i++) {
		v.push_back(0);
		cur = v.capacity();
		if (cur != pre)
			printf("new capacity: %d\n", cur);
		pre = cur;
	}
	return 0;
}

초반에는 vector의 capacity가 천천히 (3 ➡ 4 ➡ 6 ➡ 9) 증가하다가, 후반에는 크게 증가한다(711 ➡ 1066 ➡ 1599)

단순히 생각하면, '정적 array의 공간 낭비를 막기 위해 동적 할당을 쓰는데, 벡터의 size가 증가할 때만 capacity를 증가시키면 안 되는 걸까?'라고 생각할 수 있다. 특히, 후반에 vector의 capacity가 8092에서 12138로 증가할 때 element를 8093개만 push한다면 나머지의 공간은 쓰이지 않게 된다.

하지만 capacity를 증가시킬 때(realloc을 시행할 때)의 시간복잡도를 고려해야 한다.

만약 element를 push할 때 마다 증가시킨다면? n개의 element를 push할 때 마다 realloc을 시행하므로(realloc 시 new array의 크기만큼의 시간복잡도가 걸린다고 가정하면), 총 시간은 O(n²)이므로 average time은 O(n)이 된다.

기본적인 array 및 list의 insert 연산에 O(1)이 소모된다는 걸 보면, capacity를 매번 늘려주는 것은 엄청난 손해이다.

따라서 stl vector에서는 후반부터 약 1.5배의 증가율로 capacity를 증가시킨다. 이러한 경우에는 array의 size가 n이 될 때 까지 log1.5 (n)회 realloc을 시행하게 되고, 평균적인 push 수행 시간은 약 O(1) 이다(계산 생략 ^^).

이것이 vector의 capacity를 매 push마다 늘려주지 않고, size와 동일해질 때 마다 1.5배 씩 주는 이유이다. 이는 stack 및 다른 자료구조의 구현에도 유사하게 적용된다

🙂