STL container choice

컨테이너는 Big-O보다 메모리 배치, 검색 경로, 무효화 규칙까지 같이 고른다

std::vector가 기본값인 이유는 단순해서가 아니라 연속 메모리와 순회 지역성이 강하기 때문이다. 요구가 달라지면 양끝 조작, 정렬된 키, 해시 조회, 제한된 인터페이스를 따로 판단한다.

순회·임의 접근 연속 메모리와 캐시 지역성이 중요하면 vector부터 본다.
정렬된 키 순서와 lower_bound가 의미 있으면 map/set 계열이다.
평균 빠른 조회 순서가 필요 없고 해시 품질을 관리할 수 있어야 한다.
제한된 인터페이스 stack, queue, priority_queue는 내부 컨테이너를 숨긴다.
sequence vector, deque, list는 삽입 위치와 무효화 규칙이 다르다.
ordered 트리 기반 컨테이너는 비교자 일관성이 깨지면 전체 계약이 흔들린다.
unordered 평균 O(1)은 bucket, load factor, 입력 분포를 같이 봐야 한다.
adaptor top, front, pop 같은 제한 API가 의도 표현을 돕는다.
기본값 특별한 이유가 없으면 vector의 단순성과 locality가 출발점이다.
변경 비용 중간 삽입·삭제가 잦으면 이동 비용과 iterator 안정성을 비교한다.
검색 계약 정렬 순서, hash/equal, comparator가 API 계약의 일부다.
숨은 비용 재할당, 노드 할당, rehash, cache miss가 Big-O 밖의 병목이다.

먼저 “무엇을 자주 하는가”를 묻고, 그 다음 숨은 비용을 확인한다

access -> update -> search -> order -> invalidation
1

연속 메모리와 인덱스 접근

임의 접근 O(1), 끝 삽입 amortized O(1), 중간 삽입 O(n)이면 먼저 이쪽을 본다.

vector array
2

앞과 뒤를 모두 자주 조작

양끝 push/pop은 강하지만 전체가 하나의 연속 배열은 아니다. 포인터 안정성도 vector와 다르다.

deque
3

위치를 이미 알고 중간 변경

iterator가 이미 있으면 삽입/삭제가 강하다. 찾기부터 해야 하면 탐색 O(n)이 먼저 온다.

list forward_list
4

정렬된 키와 범위 조회

키 순서 순회, lower_bound, 범위 삭제가 API 일부라면 트리 기반 컨테이너가 맞다.

map set
5

순서 없는 평균 빠른 검색

평균 O(1)을 기대하지만 해시 품질, load factor, rehash, 최악 O(n)을 같이 확인한다.

unordered_map unordered_set
6

인터페이스를 제한해 의도를 드러냄

전체 컨테이너를 공개하지 않는다. priority_queue는 FIFO/LIFO가 아니라 heap adaptor다.

stack queue priority_queue

같은 O 표기라도 locality, order, invalidation에서 실제 선택이 갈린다

access mutation hidden cost
vector 연속 메모리 · O(1) 접근 끝 삽입 amortized O(1) 정렬 후 binary search 재할당 시 참조 무효화
deque random access · 비연속 블록 앞/뒤 삽입·삭제 O(1) 기본 검색 O(n) 블록 구조와 무효화 규칙 확인
list / forward_list 임의 접근 없음 iterator 위치 삽입·삭제 강함 찾기부터 하면 O(n) 노드 할당과 캐시 miss 비용
map / set 키 순서가 구조의 일부 삽입·삭제 O(log n) 검색 O(log n) 비교자 일관성 유지
unordered_map / unordered_set 순서 보장 없음 평균 삽입·삭제 O(1) 평균 검색 O(1), 최악 O(n) bucket 메모리와 해시 품질
stack / queue / priority_queue 내부 컨테이너를 감싼다 규칙에 맞는 입출력만 허용 priority_queue는 heap 기반 컨테이너 제약 확인