Vector
- 배열 기반 연결 리스트로 구현되어 있음
- capacity를 넘어서 원소를 삽입하면 다른 연속된 메모리 공간을 할당하고 메모리를 옮긴다.
- 앞쪽의 삽입 삭제가 최대 O(N)으로 느리다.
- 인덱스 접근이 가능하다.
assign : 재할당
resize : 기존 공간은 그대로 두고 초과분만 할당
reserve : 캐퍼시티 할당
list
- 노드 기반 연결 리스트
- 삽입 삭제가 O(1)로 빠르다.
- 한번에 중간 접근이 불가능하다.
map
- 데이터가 키-값 으로 이루어져 있다.
- 키 기준 레드 블랙 트리로 구현되어 있음
- AVL 트리보다 균형 조건이 느슨해서 탐색이 조금 길지만 삽입/삭제 성능이 좋다.
AVL보다 복구 동작 횟수도 안정적이다. - 삽입/삭제시 정렬이 이루어져서 시작 복잡도가 O(logN)이다.
- 순회하면 정렬된 순서로 순회한다.
- 없는 값에 접근하면 자동으로 값을 생성한다.
따라서 그냥 찾으려면 find 를 사용해야 한다. - 동일한 키를 저장할 수 없다.
unordered map
- 해시테이블로 구현돼있다.
- 해시테이블의 버킷의 숫자는 소수일 때 테이블을 효율적으로 사용할 수 있다.
모듈러 연산에서 항상 나머지가 나오기 때문에 어느정도 고르게 할당하게 된다. - 2의 거듭제곱을 버킷의 숫자로 하게 되면 해시값이 버켓을 결정하는 데 사용하는 비트 수가 줄어들기 때문에 중복값이 많이 나오게 된다.
- 내부적으로 정렬되어 있지 않다.
- 없는 값에 접근하면 자동으로 값을 생성한다.
set
- 키로만 이루어진 map
- 레드 블랙 트리로 구현돼 있음.
- 원소들은 오름차순으로 정렬돼있음
- 존재하는 값을 넣으면 무시됨
- 탐색, 삽입, 삭제 O(log N)
- 원소 수정 불가능
multimap
- 중복 키를 허용하는 map
- 레드 블랙 트리 기반 구현
- 원하는 키의 모든 값을 범위를 찾는 기능이 있음
operator[]는 정의돼 있지 않음
deque
- 양쪽에서 삽입 삭제가 가능함.
- 세그먼트 배열을 사용함. (벡터처럼 단일 연속은 아님)
- 각 세그먼트 블록 포인터를 (map 이라고 하는)배열에 저장함.
- 이 배열을 이용해서 랜덤 엑세스 가능
queue
- FIFO 방식
- 템플릿 어댑터 (인터페이스를 맞춰주는 디자인 패턴)
- push_back 과 push_front를 지원하는 내부 컨테이너를 설정 가능함.
priority_queue
- 힙 기반 구현.
- 인덱스 기반 정렬을 하기 때문에 내부 컨테이너는 배열 기반 컨테이너만 설정 가능.
- 디폴트 설정은 최대 힙, 정렬 기준을 바꿀 수 있음.
- 정렬함수는 람다 또는 함수 객체를 사용 가능.
stack
forward_list(단방향 연결 리스트)
- 단방향이니까 삽입 삭제가 빠르지만 뒤로 돌아가지 못함.
array
- 컴파일 타임에 크기가 정해지는 배열.
- 깊은 복사가 구현돼 있다.
valarray
- 벡터간의 사칙 연산이 정의돼 있음.
- 컴파일러에 따라 자동 SIMD 연산 가능.
- 배열 기반.
iterator
- STL 컨테이너를 순회하기 위한 객체
- 포인터처럼 동작하지만 컨테이너에 따라 동작 방식이 다르다.
- 컨테이너에 따라 다르지만 ++ -- 기능은 동일하게 존재한다.
- end() 는 마지막 원소의 다음을 가리킨다. (자료구조의 더미 노드같은 개념)
- insert나 erase를 잘못 쓰면 이터레이터가 무효화 될 수 있다.
make_heap
- make_heap
- push_heap
- pop_heap
median of three
- 퀵 소팅을 할 때 피벗을 설정하는 방법.
- 맨 앞, 중간, 마지막의 원소끼리만 먼저 정렬 한 뒤 퀵 소팅을 한다.
- 해당 과정을 정렬이 끝날 때까지 반복한다.
