STL 컨테이너

시퀀스 컨테이너 

- 데이터의 저장 /삽입 /삭제

vector

• 동적 배열로, 크기가 가변적
• 요소는 연속된 메모리 블록에 저장 -> 임의 접근이 빠르며(name[index])
• 끝에서의 삽입/삭제가 빠름 (push,pop)
• 시간 복잡도 : 마지막에서의 삽입/삭제,임의 접근 O(1), 중간에서의 삽입/삭제,크기 재할당 O(n)

deque

• 스택과 큐의 기능을 포함 -> 앞뒤 양쪽 끝에서 삽입/삭제 가능(append,pop, appendleft, popleft)
• 메모리 블록이 여러 개로 나뉘어 있을 수 있음
• 시간 복잡도 : 양쪽 끝에서의 삽입/삭제 O(1)

list

• 이중 연결 리스트(앞뒤를 가리키는 포인터를 포함)로 삽입/ 삭제가 빠름
• 비연속적인 메모리에 저장 -> 임의 접근이 느림
• 시간 복잡도 : 삽입/삭제 O(1), 요소 접근O(n)
• 임의 접근 지원 안함

forward_list

• 단일 연결 리스트(뒤를 가리키는 포인터 포함) -> 한 방향으로만 손회
• 메모리와 성능 면에서 이중 연결 리스트 보다 더 가벼움(포인터가 적음)
• list와 같은 비연속적인 메모리에 저장
• 시간 복잡도 : 앞쪽에서의 삽입/삭제 O(1), 중간 뒤에서의 삽입/삭제 O(n) (앞쪽만인 이유는 뒤로 가기위해서는 포인터를 따라가야 하기 때문에

 

연관 컨테이너 

- 키/값 쌍으로 정렬된 데이터 저장, 빠른 검색이 가능(이진 탐색 트리)

set

• 키 값은 따로 존재하지 않음
• 중복 요소 없음 -> 중복된 요소는 자동으로 제거
• 자동 정렬 - 기본적으로 오름차순이지만 기준을 변경할 수 있음
• 시간 복잡도 : 탐색, 삽입, 삭제 O(log n)
• 중복을 허용하는 multiset 이 있음

map

• 키/값을 저장 -> 키를 기준으로 정렬
• 중복 키는 허용하지 않음 -> 중복된 키는 새로운 값으로 대체
• 자동 정렬
• 시간 복잡도 : O(log n)
• 중복을 허용하는 multimap 이 있음

비정렬 연관 컨테이너

-해시 테이블을 기반으로 데이터를 비정렬 상태로 저장하지만 빠른 검색이 가능

• 연관 컨테이너 set,map 이름 앞에 unordered_ 를 붙히면 호출
• 시간 복잡도 : 평균적으로 O(1), 최악의 경우 O(n)(해시 충돌의 경우)
• 정렬되지 않음

컨테이너 어댑터

-기본 컨테이너에 기능을 추가하여 목적에 맞게 사용

stack

• 후입선출
• 내부적으로 데이터를 저장하는 컨테이너(deque를 기본으로 가짐/ vector,list로 변경 가능)
• 임의 접근이나 순회는 지원하지 않음
• 시간 복잡도 : O(1)

queue

• 선입선출
• 시간 복잡도 : O(1)

prioity_queue

• 삽입된 순서와 무관하게 우선순위에 따라 정렬
• 기본으로 가장 큰 값이 큐의 맨 위에 위치(큰 수 가 먼저 출력)
• 힙 구조 사용
• 기본적으로 vector를 사용 deque도 사용할 수는 있음