std::vector 란?

 

C++에서는 다양한 데이터 컨테이너가 있는데, 그 중 vector는 단연코 가장 많이 쓰이는 데이터 타입이다.

 

 

Vector 란?

vector는 연속된 동적 메모리 공간이다. 때문에 vector의 사이즈가 유동적으로 변할 수 있다.

연속된 메모리 공간은 heap에 생성되고, C++의 모든 오브젝트는 stack에서 시작되기 때문에 vector 오브젝트는 stack에 존재한다.

이 때 이 vector 객체를 까보면 pointer, size, capacity로 나뉘어져 있다.

pointer는 heap 영역 내의 연속된 메모리 공간의 첫번쨰를 가리키고,
size는 이 공간의 size를 말한다.

capacity는 이 메모리 영역이 어디까지 할당할 수 있냐를 의미한다. 

이 때, capacity가 다 찬 vector는 새로 재할당이 필요하다. 이런 재할당이 필요한 경우가 memory fragmentation(메모리 단편화)이다.   

메모리 단편화란?

힙 공간 안에는 여러가지 다른 오브젝트들 또한 할당이 되어 있다.
힙 안에서는 각 오브젝트들이 연속적으로 할당되지 않고 불규칙적으로 군데군데 적재되어 있는 상태이다.
그러면 새로운 값을 넣으려고 할 때 연속적으로 할당되어 있는 vector의 메모리 공간 뒤에 빈 공간이 아닌 다른 오브젝트가 점유하고 있는 메모리 공간이 있을 수도 있다. 그 경우에 push_back이 불가하고, 새로 재할당하여 요소 하나하나를 카피해야 하는 것이다.  

이를 해소하기 위해 vector를 선언한 후, reserve(10) 함수를 이용하여 인자로 들어간 10개의 공간을 쓸 수 있는 곳으로 벡터를 재할당한다. 즉, reserve란 해당 숫자만큼 쓰기 위해 데이터 공간을 미리 제공해놓는 함수이다.

 

vector를 쓰는 이유는 performance이기 때문에 vector의 시간을 많이 잡아먹을 수 있는 capacity-reallocation-reserve는 자세히 알고 있는 것이 좋다.

 

push_back과 push_front의 시간 복잡도?

push_back은 대부분 O(1)이다. -> 연속된 공간에 새로운 공간을 만들어 넣어주면 끝난다. 하지만 재할당이 일어날 경우 시간복잡도가 훨씬 커진다.

push_front는 O(N)이다. -> vector는 첫번째 공간을 가리키는 포인터를 가지고 있는데, 이 첫번째 공간은 고정되어 있기 때문에 임의로 바꿀 수 없다. 그렇기 때문에 가장 앞에 값을 추가하려면 지금 저장되어 있는 모든 데이터를 하나씩 뒤로 옮겨야 한다.

 

이와 마찬가지로 pop_back과 pop_front의 시간복잡도도 마찬가지로 O(1)과 O(N)이다.

 

vector를 사용할 때 new, malloc과 같이 할당/할당 해제 키워드를 쓰면 안되는 이유?

가장 큰 이유는 memory leak 때문이다.

memory leak이란 오브젝트를 힙에 생성했을 때 오브젝트를 사용한 뒤 해제하지 않으면 생긴다.
heap 상에서는 메모리가 좀비처럼 적재되어 있다. new/malloc을 사용한다면 메모리 해제를 까먹어서 메모리 릭이 생길 수 있기 때문에 사용하지 않는 것이 좋다.
vector에서 메모리 릭이 발생하지 않는 이유는 vector는 stack에 먼저 선언이 되고, vector 내의 포인터가 힙의 메모리 주소를 가리키는 것이기 때문이다.

기본적으로 vector는 STL이기 때문에 제공해주는 함수를 써서 쓸 필요가 크게 없다.

 

emplace_back과 push_back의 차이

push_back은 파라미터로 넘겨진 lvalue 레퍼런스가 복사되어 vector의 끝에 할당되거나, (C++11 이상) rvalue 레퍼런스가 아예 vector의 끝으로 옮겨지는 방식으로 작동을 한다.

emplace_back는 기본적으로 rvalue를 받는다. 이 때 lvalue 복사, rvalue move 등은 push_back과 같 지만 emplace_back은 한 가지 기능이 더 있다. 바로 파라미터에 어떠한 object의 생성자를 넣게 되면 해당 객체가 vector 내에서 바로 생성이 되는 것이다.

 

vector를 써야할 때와 쓰지 않아야 할 때?

vector는 값에 접근하거나, 가장 끝에 데이터를 추가/삭제하는 경우에 performance가 좋기 때문에 끝이 아닌 다른 위치에 데이터를 삽입삭제하는 경우가 많을 때에는 vector를 사용하지 않고 list 등 다른 컨테이너를 사용하는 것이 바람직하다.