[STL] 컨테이너의 분류와 종류(순차 컨테이너, 연관 컨테이너, 비정렬 컨테이너)

컨테이너의 종류는 크게 3가지로 나눌 수 있다. 순차 컨테이너, 연관 컨테이너, 비정렬 컨테이너로 볼 수 있는데 이 안에 포함되는 STL 컨테이너들도 간단히 소개한다.

 

---

순차 컨테이너 ( Sequence Container )

모든 요소를 저장한 순서대로 저장하는 컨테이너이다. 원소를 선형적 순차열(Linear Sequence)에 저장하는데 이 때문에 인해 정렬되지 않는다. 이 위치는 삽입한 시점과 위치에 따라 달라지며 요소의 값과는 독립적이다. 자동적으로 정렬되지 않기 때문에 정렬 알고리즘을 사용하여 수동으로 정렬해야 한다. STL에 선정의된 순서 컨테이너는 배열(array), 벡터(vector), 데크(deque), 양방향 리스트(list), 단방향 리스트(forward_list) 가 있다.

 

• Array : 고정 길이 배열, 원소 갯수의 추가 또는 삭제가 불가능하며 최초 설정한 갯수를 변경할 수 없다.
• Vector : 가변 길이 배열, 원소의 갯수가 부족할 시 자동적으로 늘어난다. 가장 뒤에만 데이터를 삽입/삭제할 수 있다.
• Deque : 가변 길이 배열, 원소의 갯수가 부족할 시 자동적으로 늘어난다. 가장 앞과 뒤에 데이터를 삽입/삭제할 수 있다.
• List : 양방향 연결리스트, 데이터를 연결하는 포인터가 2개 있어 앞, 뒤 이동이 자유로운 리스트, 어떠한 곳에서든 데이터의 삽입/삭제가 가능하지만 해당 위치를 찾는 것은 별도의 시간이 필요하다.
• Forward_list : 단방향 연결리스트, 데이터를 연결하는 포인터가 1개만 있어 앞으로만 이동할 수 있다. 상대적으로 가볍지만 뒤로 갈 수 없어 지나쳤다면 다시 처음부터 탐색해야 한다. 어떠한 곳에서든 데이터의 삽입/삭제가 가능하지만 해당 위치를 찾는 것은 별도의 시간이 필요하다.

 

벡터(vector)
벡터는 동적배열을 만드는 연산을 수행한다. 따라서 연속적인 메모리를 확보한다. 자신의 요소를 내부의 동적 배열 ( dynamic array )로 복사한다. 임의 접근 연산자를 제공([])하기 때문에 어떠한 값에 접근하든 상수시간이 소요된다.

동적 배열이기 때문에 배열의 중간에 새로 추가하거나 삭제하면 많은 값이 이동해야하기 때문에 오랜 시간이 걸린다. 중간에 추가하는 것이 오버헤드가 크기 때문에 보통 뒷부분에 추가한다.( push_back ) 크기의 확장과 축소가 자유롭지만 재할당 비용은 크다.

장점 : 임의접근을 상수시간에 가능하다. 따라서 읽기에 매우 강하다.
단점 : 중간에 값을 추가/제거하는 비용이 크다재할당 비용이 크다.


리스트(list)
리스트는 요소들을 양방향 연결리스트의 형태로 관리한다.(Doubly Linked List) 리스트 객체는 앵커라 불리는 포인터 2개를 제공하는데 이는 head와 tail을 가리킨다. 새로운 요소를 삽입하기 위해서는 이 포인터(앵커)를 조작한다.

리스트는 임의 접근을 제공하지 않는다. ( n번째 요소에 접근하기 위해서 노드들을 거쳐야 하기 때문 ) 특정 위치에 추가/삭제가 자유롭다. ( 특정 위치를 찾는 시간은 제외 ) 재할당 연산이 없다. 연속적인 메모리가 아니기 때문에 메모리가 제공되는 한 무한히 추가할 수 있다.

장점 : 임의의 위치에 요소를 추가하는 것이 자유롭다 ( 찾아가는 시간 제외 ) 따라서 쓰기에 매우 강하다.
단점 : 임의 접근이 불가능하기 때문에 선형 탐색하여 위치를 찾는다원소간의 연결을 위해 추가적인 메모리를 소모한다. ( 다음 노드의 포인터 메모리 )


벡터와 리스트 차이
두 컨테이너의 가장 큰 차이는 각 컨테이너의 장점과 단점으로 볼 수 있다. 리스트의 장점은 벡터의 단점이고 리스트의 단점은 벡터의 장점이다. 벡터는 특정 위치에 접근하는 것이 상수시간에 가능하지만 중간에 데이터를 삽입하는 것이 오버헤드가 크지만 리스트는 데이터를 중간에 삽입하는 것에 오버헤드가 크지 않지만 해당 위치를 탐색하는데 시간이 오래 걸린다.

데이터의 추가, 제거가 잦다면 리스트가, 새로운 데이터의 추가, 삭제보다 기존 데이터의 수정 및 탐색이 많다면 배열이 더 유리하다. 다만, 순차적으로 모든 데이터를 탐색해야하는 상황이 많은 경우에는 큰 차이가 나지 않을 수 있다.

---

 

연관 컨테이너(Associate Container)

요소의 위치가 자신의 값과 특정 정렬 기준에 따라 정해지는 컨테이너이다. 자동적으로 정렬되기 때문에 삽입 순서는 중요하지 않다. 대체로 균형 이진 트리 또는 해쉬 함수를 사용하여 구현되어 있어 탐색에 유리하다. STL에 선정의된 연관 컨테이너는 set, multiset, map, multimap 이 있다.

 

• Set : Value 자체가 키가 되는 컨테이너, 중복을 허용하지 않기 때문에 모든 원소가 유일하다.
• Multiset : Set의 중복 허용 버전
• Map : Key와 Value를 가지는 컨테이너, Key를 사용하여 정렬, 탐색한다. [] 오퍼레이터를 이용하여 특정 위치에 직접 접근이 가능하며 insert를 사용해 해당 위치에 데이터 추가도 가능하다. Set과 동일하게 중복 키를 허용하지 않는다.
• Multimap : Map의 중복 허용 버전이지만 [] 오퍼레이터를 지원하지 않으며 중간 삽입이 불가능하다.

 

---

 

비정렬 연관 컨테이너(Unordered Associate Container)

요소의 위치가 중요하지 않은 비정렬 컨테이너이며 특정 요소가 이 컨테이너 안에 있는지만 중요하게 본다. 삽입 순서도, 요소의 값도 위치에 영향을 주지 않으며 컨테이너가 존재하는 동안 위치가 변할 수 있다. STL에 선정의된 비정렬 컨테이너는 unordered_set, unordered_multiset, unordered_map, unordered_multimap 이 있다. 대체로 해시 테이블로 구현되며 정의할 때 해시 함수도 함께 입력한다.

 

• unordered_set : Value 자체가 키가 되는 컨테이너, 중복을 허용하지 않기 때문에 모든 원소가 유일하다.
• unordered_multiset : Set의 중복 허용 버전
• unordered_map : Key와 Value를 가지는 컨테이너, Key를 사용하여 정렬, 탐색한다.
• unordered_multimap : Map의 중복 허용 버전

 

02.04.04. 비정렬 연관 컨테이너(Unordered Associative Containers)