**표준 시퀀스 컨테이너
- 반개 구간
[begin, end)- 시작은 언제나 같지만, 끝은 정해져 있지 않음 - 동적 배열을 기반으로 하는 컨테이너
- 인덱스를 통해 임의 접근이 가능하다 = 탐색 속도 빠름
- 삽입 시 앞에서부터 삽입 할 수 없다(맨 끝 추가만 가능)
- 중간 삽입, 삭제 시 원소 개수 만큼의 선형적 시간 복잡도 발생
- 원소를 삭제해도 존재했던 공간(메모리)은 남아있음
- 맨 끝에 삽입, 삭제 시에는 상수 시간 복잡도가 발생한다.
- 할당된 메모리의 크기보다 더 많은 원소 삽입시 동적 배열 재할당과 원소 복사가 일어난다.
- 노드를 기반으로 하는 컨테이너
- 앞/뒤 노드의 삽입 삭제가 가능하다(상수 시간 복잡도)
- 비연속적인 공간에 나열된 노드들을 연속된 것처럼 나열. 따라서 임의 접근이 불가능하다
- 탐색과 순회가 반드시 순서대로 진행되기 때문에 선형 시간 복잡도가 걸린다.
++,--연산자만 오버로딩 되어있음- 한정된 메모리 공간을 사용하는 것이 아니기 때문에 데이터 저장이 유연하다
- 대량의 데이터 저장시에 vector보다 메모리 부담이 적음
- vector의 한 종류의 컨테이너이며 동적 배열 기반이다.
- 임의 접근이 가능하다.
- chunk1 형태의 데이터 저장이 진행됨
- vector와 list가 혼합된 형태
- vector와 비교했을 때 8배 가까이 되는 메모리 용량을 요구한다
**표준 연관 컨테이너
- 레드 블랙 트리(Red Black Tree) 기반으로 이루어져 있음
- map의 원소들은 각 key와 value로 한 쌍을 이룬다.
- 각 원소들을 삽입 시에 key값에 따라 자동 정렬된다.
- 삽입 삭제 시 마다 정렬을 하기 때문에 삽입, 삭제가 불리하다.
- 연관 컨테이너 중 유일하게 대괄호 연산자가 오버로딩 되어있다. 임의 접근이 가능
- 리소스 탐색용으로 많이 쓰이며, 중복 key값은 허용하지 않는다.
mult-map
- map과 동일하나 중복 key값을 허용하기 때문에 대괄호 연산자를 사용 할 수 없다.
set
- map과 달리 원소 한 쌍이 아닌 하나의 key만 갖는다.
- 삽입 시 key값 기준 정렬이 일어난다.
- 중복 key값을 허용하지 않는다.
multi_set
- set과 동일하나 중복 key값을 허용한다.
Footnotes
-
메모리 구성 단위, 데이터 블럭 ↩