STL Sequence Container 벡터(Vector), 리스트(List), 덱(Deque)

컨테이너의 여러 종류 중 데이터를 선형적으로 저장하는 시퀀스 컨테이너 벡터, 리스트, 덱에 대해 살펴보자

벡터(Vector)

배열과 마찬가지로 연속적인 메모리 공간을 사용한다. 따라서 iterator뿐만 아니라 인덱스로 접근이 가능하기 인덱스를 통한 랜덤 액세스가 빠르다.

또한 배열과 다르게 동적으로 확장이나 축소가 가능하기 때문에 배열에 비해 가변적인 특성을 가지고 있다.

벡터는 뒤에서 데이터를 삽입/삭제 할 때만 효율적이다. push_back(), pop_back() 함수를 사용하며 맨 뒤에서 삽입하거나 삭제하면 그 이후 더 이상 할 일이 없기 때문이다.

그러나 맨 앞이나 중간에서 삽입/삭제가 이루어지면 기존 원소들의 이동이 필요하기 때문에 비효율적이다. 그래서 push_front(), pop_front() 함수가 존재하지 않는다. 중간에서 삽입 삭제가 빈번하게 이루어진다면 벡터보단 리스트를 사용하는게 적합할 것이다.

동적으로 컨테이너의 크기가 늘어나거나 줄어든다는 점은 벡터의 장점이지만 확장시에 재할당 비용이 크기 때문에 벡터의 크기를 어느정도 지정해놓고 사용하는 것이 좋다. 재할당 시 컨테이너가 차지하고 있는 메모리 영역의 모든 데이터를 새 메모리에 복사하고 기존 메모리에 저장된 내용은 소멸시키고 해제한다.

reserve 함수를 통해 대략적으로 필요한 정도의 메모리를 할당받아 전체적인 재할당은 피하는 것이 좋다. reserve함수를 사용하지 않으면 capacity의 2배 만큼 재할당 되기 때문에 그만큼 비용이 커지게 된다. 

리스트(List)

STL에서 리스트는 Doubly Linked List 구조이다.

인덱스 접근이 불가능하기 때문에 원하는 원소를 찾으려면 탐색을 해야 한다.

탐색은 제일 앞에서 시작하거나 제일 뒤에서 시작할 수 있다.

리스트는 삽입 삭제가 빠르다는 장점이 있다. 맨 앞, 뒤의 위치를 가지고 있으므로 바로 삽입 삭제가 가능하며 기존 데이터를 밀거나 당길 필요가 없다. 

컨테이너의 크기가 100일 때 55번째에 데이터를 삽입하거나 삭제하길 원한다면 55번째라는 위치를 찾기위해 탐색하는 과정이 필요하긴 하지만(Worst case엔 O(n)) 위치를 찾았을 때 포인터만 이어주면 되므로 삽입 삭제가 빠르다고 볼 수 있다.

덱(Double Ended Que)

이름에서 알 수 있듯이 큐와 비슷한 특징을 가지고 있다. 큐는 앞에서 삭제, 뒤에서 삽입이 가능한 선입선출 구조이지만 덱은 앞, 뒤에서 삽입 삭제가 가능하다는 장점이 있다. 따라서 맨 앞, 뒤에서 삽입 삭제가 빠르다.

iterator를 통해 어떤 방향으로도 참조할 수 있다.

벡터와 달리 모든 원소가 연속적인 메모리 공간을 차지하고 있다고 보장할 수 없다.  벡터는 capacity가 꽉 찼을 때 새로운 메모리 공간을 할당 받아 컨테이너 전체가 복사되어 연속적인 메모리 공간임을 보장 받지만 덱은 여러 개의 메모리 블록을 사용하여 메모리 상에서 잘 나눠져 보관된다. 그리고 그 메모리 위치를 잘 기억하고 있기 때문에 사용자는 마치 연속된 메모리 공간처럼 원소에 쉽게 접근할 수 있다. 벡터에 비해 조금 더 복잡할 수 있지만 벡터보다 메모리 공간을 효율적으로 사용한다고 볼 수 있다.