C++복습) vector(동작원리)

벡터

벡터는 STL(Standard Template Library)에서 사용빈도가 높은 컨테이너중 하나이며, 동적배열로 구성되어 있다.

 

 

동적배열

 

동적배열은 변수의 수가 달라짐에 따라 배열의 크기 또한 유동적으로 변화하는 배열을 의미한다. 그렇다면 어떤식으로 배열의 크기가 유동적으로 변화하는 것인가? 다음과 같은 방법으로 동적배열은 작용한다.

 

• 여유분을 두고 메모리를 할당한다.

 

• 메모리가 꽉찬다면, 메모리를 증설한다. 

 

이런 두 방식으로 동적배열이 작동한다고는 하지만 다음과 같은 의문이 생긴다.

Q1)여유분은 얼마만큼이 적당한가?

Q2)증설은 얼마나 해야되나

Q3)기존 데이터를 어떻게 처리할까?

 

벡터의 메모리 할당 원리

 

벡터의 메모리 할당 방식은 size(실제 사용 데이터 개수)와 capacity(여유분을 포함한 용량 개수)로 되어있다.

특히 capacitiy는 컴파일러 마다 그 알고리즘이 다르지만 Visualstudio의 경우 1~4까지는 1씩 증가하고 4부터는 1.5배의 증가를 보인다.(1,2,3,4,6,9,13,19,28......)

그렇다면 1~4처럼 필요한 만큼 1씩 증가하면 메모리 낭비를 줄일수 있을텐데 어째서 일정한 알고리즘으로 증가해야 되는가 하는 의문이 들 수 있다. 

메모리가 가득찬 배열[1 2 3 4 5] 있다고 가정해보면, 이 배열은 증설을 통해서 새로운 데이터를 넣을 준비를 해야된다. 이럴때 더 큰 배열을 준비하고 그 안에 데이터를 복사하는 식으로 이동을 한다. 즉, 필요한 만큼 1씩 증가를 시키면 계속 해서 복사하는 복사비용이 들게 되며, 이러한 복사비용을 줄이기 위해서라도 여유분을 두는편이 좋다.

또한 이사비용을 없애기 위해 데이터를 무한정 늘리기에는 적은수의 메모리를 요구할수도 있기 때문에 일정한 알고리즘으로 capacity를 늘리는 방식으로 작동하게 되는 것이다.

만약 필요한 데이터의 크기를 알고 있다면 capacity를 지정해 줄수 있다.

vector<int>v;
v.reserve(100); //capacity=100

size또한 capacity와 동일하게 크기를 지정해줄수있다. 이경우 capacity와 size가 동일하게 증가한다.

vector<int>v;
v.reszie(100);// ==vector<int>v(100);
// size=100 capacity=100

 

※주의:resize를 하고 push_back을 하면 할당받은 영역이 아닌 다음 영역부터 채워지기 때문에 resize를 했다면 배열과 같이 할당한 배열을 제어해야된다 ex)v[0]=2 v[1]=3