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

 

컨테이너의 종류는 크게 3가지로 나눌 수 있다.

순차 컨테이너, 연관 컨테이너, 비정렬 컨테이너로 볼 수 있는데 이 안에 포함되는 STL 컨테이너들도 간단히 소개한다.

 

---

순차 컨테이너 ( Sequence Container )

모든 요소를 저장한 순서대로 저장하는 컨테이너이다. 원소를 선형적 순차열(Linear Sequence)에 저장하게 되는데 이로 인해 정렬되지 않는다. 이 위치는 삽입한 시점과 위치에 따라 달라지며 요소의 값과는 독립적이다.

자동적으로 정렬되지 않기 때문에 정렬 알고리즘을 사용하여 수동으로 정렬해야 한다.

STL에 선정의된 순서 컨테이너는 배열(array), 벡터(vector), 데크(deque), 양방향 리스트(list), 단방향 리스트(forward_list) 가 있다.

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

[STL] 벡터(Vector)와 리스트(List)의 장단점과 차이점

 

---

 

연관 컨테이너(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)