STL 컨테이너

1. 시퀀스 컨테이너

• 가장 일반적인 형태의 컨테이너.
• 특별한 제약, 규칙 없이 데이터를 선형으로 저장함.
• 입력한 순서대로 저장하기 때문에 데이터의 검색에는 불리함
• vector, deque, list, forward_list

 

 

2. 연관 컨테이너

• 일정한 규칙에 따라 자료를 조직화하여 저장, 관리하는 컨테이너.
• 자료를 정렬하여 저장하기 때문에 데이터의 검색에 유리함.
• 많은 양의 자료나 검색 속도가 중요한 경우에 사용.
• set, map, unordered_set, unordered_map

 

 

3. 컨테이너 어댑터

• 간결함과 명료성을 위해 시퀀스나 연관 컨테이너에서 인터페이스를 제한하여 변형시킨것.
• 반복자를 지원하지 않는다.
• stack, queue, priority_queue

---

구분	Container	시간복잡도			특징
		Random Access	찾기	삽입/삭제
Sequence Containers	vector	O(1)	O(n)	중간 O(n) 맨 뒤 amortized O(1)	1. 각 요소를 메모리 상 연속적으로 저장한다. 2. 메모리를 동적으로 할당하여 크기를 조절할 수 있다. 3. 요소의 삽입/삭제마다 배열의 크기를 파악하고 동적으로 변경하는데 이 때 O(n)의 비용이 소모된다. 하지만 이 비용은 전체 작업에 고르게 분산되므로 amortized O(1)의 시간 복잡도를 갖게된다.
	deque	O(1)	O(n)	중간 O(n) 앞/뒤 amortized O(1)	1. double-ended queue 2. 메모리의 동적 할당, 삽입/삭제에 대한 시간 복잡도는 vector와 동일하다. 3. vector와 다르게 여러 배열들이 다른 메모리 블록에 분산되어 존재한다. 이러한 점 때문에 메모리를 효율적으로 사용할 수 있지만 임의 접근에서 vector보다 오버헤드가 발생할 수 있다. 4. 배열 끝에서의 작업이 주로 수행되거나 임의 접근이 많이 필요한 경우 vector, 양쪽 끝에서 혹은 배열 중간에서의 작업이 필요한 경우 deque를 사용한다.
	list	X	O(n)	O(1)	1. double linked list 구조. 2. 연속적인 메모리 공간을 사용하지 않고 각 노드가 동적으로 할당되어 연결되어 있다. 3. 어느 위치에서든 상수시간에 삽입과 삭제가 가능하다. 4. 순차적인 접근이 주로 이루어지거나 삽입/삭제가 빈번한 상황에서 사용한다.
	forward_list	X	O(n)	O(1)	1. single linked list 구조. 2. list와 다르게 역방향 접근이 불가능하지만 더 적은 메모리 공간을 차지한다.
Associative Containers	set	X	O(logN)	O(logN)	1. red-black tree 구조를 사용하여 항상 정렬된 상태를 유지하고 시간 복잡도를 보증한다. 2. 데이터 자체를 Key로 사용하며 Key의 중복은 허용하지 않는다. 3. Key의 중복을 허용하는 multi_set도 존재한다.
	map	X	O(logN)	O(logN)	1. 요소들을 Key-value 쌍을 이루어 관리한다. 2. 나머지는 set과 동일하다. 3. Key의 중복을 허용하는 multi_map도 존재한다.
	unordered_set	X	O(1)	O(1)	1. 배열과 체이닝 방식을 사용한 해시테이블 구조를 사용한다. ※ 해시 함수를 사용하여 도출한 해시값으로 특정 버킷(행)에 접근이 가능하다. 이때 각 버킷이 하나 이상의 값을 갖도록 연결 리스트로 구현하는 것이 체이닝. 2. 데이터가 많아질 경우 해시 충돌로 시간 복잡도가 O(n)까지 증가할 수 있다. 3. 데이터가 적고 빠른 성능을 원할때 사용하는 것이 바람직하다.
	unordered_map	X	O(1)	O(1)	1. 요소들을 Key-value 쌍을 이루어 관리한다. 2. 나머지는 unordered_set과 동일하다.
Container Adaptors	stack	X	X	amortized O(1)	1. First In Last Out 2. 스택의 삽입과 삭제는 top에서만 이루어진다. 3. 요소에 대한 접근은 top에서만 이루어진다. 임의 접근이나 탐색 연산은 stack에서 고려하지 않는다. 4. 기본적으론 deque 컨테이너를 기반으로 한다.
	queue	X	X	amortized O(1)	1. First In First Out 2. 큐의 삽입은 front, 삭제는 rear에서만 작동할 수 있다. 3. 요소에 대한 접근은 front와 rear에서만 이루어진다. 임의 접근이나 탐색 연산은 queue에서 고려하지 않는다. 4. 기본적으론 deque 컨테이너를 기반으로 한다.
	priority_queue (Heap)	X	X	O(logN)	1. 가장 크거나 작은 값에 접근할 수 있는 컨테이너. 2. 힙(heap)구조를 사용한다. ※ 힙: 완전 이진 트리 구조, 모든 노드에 대해서 부모 노드가 자식 노드보다 크거나 작다. 삽입과 삭제 연산에서 힙을 정렬하는데 O(logN)의 시간 복잡도를 갖는다. 3. 우선순위가 가장 높은 요소에만 접근할 수 있도록 설계되어 있어서 임의 접근이나 탐색은 지원하지 않는다. 4. 기본적으로 vector 컨테이너를 기반으로 한다.