[C++ 자료구조] 벡터의 동적할당 시 메모리 확장 방식

벡터는 push_back같이 메모리 공간이 더 필요할 때, 해당 공간만큼만 늘리지 않습니다. 예를들어 vector<int> v가있다고 했을 때, 메모리를 차지하는 첫 공간은 0byte입니다. 하지만 필요하면 1byte -> 2bytes-> 4bytes->8bytes->16bytes이렇게 제곱으로 늘어납니다. 왜냐하면 공간이 필요할 때 마다 현재 차지하고 있는 공간의 두배를 할당해버리기 때문이죠.

 

다음 두 코드를 비교해 봅시다.

//첫번째 케이스
vector<int> v;
for(int i = 0 ; i< 100000; i++)
{
	v.push_back(0);
}

//두번째 케이스
vector<int> v(100000,0);

 

두번째 케이스는 int가 4bytes이고 100000번 할당하니 그냥 4*100000 bytes만 필요로합니다.

하지만 첫번째 케이스에서는 필요할때마다 벡터의 공간을 늘려주는 방식이니 최악의 경우 두배로 메모리 공간이 필요할 수 있습니다. 

 

왜 굳이 벡터가 제곱 형식으로 메모리를 할당하냐면, 재할당 횟수를 최소화하여 속도 효율성을 끌어 올리기 위함인 것 같습니다. 즉 두배로 늘리면 한 동안 여유 공간이 생기기 때문이죠.

 

하지만 2차원 이상의 배열은 약간 조심해야합니다. 다음의 코드를 봅시다.

vector<vector<int>> v(100000,vector<int>(3,0));

12bytes*100000이 할당되어야할 것 같지만, 벡터의 특성상 동적으로 메모리를 관리하기 때문에, 벡터내부에서 메모리를 더 크게 잡아먹는 부분이 있는 것 같습니다. visual studio 디버그에서 추적해보니 22Mb나 잡아먹습니다. 

 

따라서 2차원 이상의 배열은 메모리 소모가 심하니, 

vector<int>v (300000);

for(int i = 0 ; i< 100000; i++)
{
	for(int j = 0 ; j < 3; j++)
    {
    	cout << v[3*i+j];
    }
}

 

이런식으로 1차원 배열을 2차원처럼 생각해서 쓸 수 있는 방법이 있겠습니다.