STL 컨테이너 개요

STL 컨테이너를 나누는 기준

STL 컨테이너는 "어떻게 저장하고, 어떻게 찾는가" 관점으로 나눕니다.

분류	대표 컨테이너	핵심 특징
시퀀스 컨테이너	vector, list, deque	삽입 순서 중심, 선형 구조
정렬 연관 컨테이너	map, set, multimap, multiset	키 기준 자동 정렬, 트리 기반
해시 연관 컨테이너	unordered_map, unordered_set	해시 기반, 평균 O(1) 검색
컨테이너 어댑터	stack, queue, priority_queue	기존 컨테이너를 제한된 인터페이스로 포장

---

시퀀스 컨테이너

공통점

• 데이터가 "줄 세우기" 형태로 저장됩니다.
• 원칙적으로 삽입 순서를 유지하며, 순회가 직관적입니다.

대표 컨테이너 차이

컨테이너	장점	약점	잘 맞는 상황
vector	연속 메모리, 캐시 친화적, 끝 삽입 빠름	중간 삽입/삭제 느림	대부분 기본 선택
list	중간 삽입/삭제 O(1)	랜덤 접근 불가, 캐시 비효율	중간 노드 조작이 잦을 때
deque	앞/뒤 삽입 모두 빠름	내부 구조 복잡, vector보다 단순하지 않음	앞뒤 push/pop가 모두 많은 큐형 작업

기억할 점

• "시퀀스 = 무조건 빠름"이 아니라, 접근 패턴에 따라 유불리가 갈립니다.
• 게임 코드에서는 기본적으로 vector를 먼저 고려하고, 요구사항이 바뀌면 다른 컨테이너를 선택합니다.

---

연관 컨테이너

정렬 연관 컨테이너 (map, set)

• 내부적으로 균형 트리(보통 레드-블랙 트리) 기반
• 삽입/삭제/검색: O(log N)
• 항상 키 순서가 정렬되어 있어 범위 질의와 순서 기반 순회에 유리

해시 연관 컨테이너 (unordered_map, unordered_set)

• 해시 테이블 기반
• 삽입/삭제/검색: 평균 O(1), 최악 O(N)
• 정렬 순서는 보장하지 않지만, 빠른 조회에 강함

map vs unordered_map 선택 기준

• 키 순서가 필요하다 -> map
• 순서보다 조회 속도가 중요하다 -> unordered_map
• 해시 충돌/리해시 비용도 실전에서 고려해야 함

---

시퀀스 vs 연관 컨테이너 시각 비교

[ 시퀀스 컨테이너 ]                    [ 연관 컨테이너 ]
  삽입 순서 중심                         키 기준 자동 배치

  vector: [A][B][C][D]                  map (정렬 트리):
  list:   A→B→C→D                             10
                                               /  \
                                              5    15
                                             / \   / \
                                            3  8 12 20

  인덱스/순회 중심                         키 검색/정렬 중심

---

실무 선택 가이드

1. "순서대로 저장 + 빠른 순회"가 핵심이면 vector
2. "키로 찾기"가 핵심이면 map/unordered_map
3. "정렬된 키 순회"가 필요하면 map
4. "최대한 빠른 조회"가 필요하면 unordered_map
5. 중간 삽입/삭제가 매우 많고 랜덤 접근이 불필요하면 list

체크 질문 (스스로 답해보기)

• 왜 vector가 기본 선택으로 자주 권장될까?
• map과 unordered_map의 차이를 정렬/복잡도 관점에서 설명할 수 있는가?
• list가 중간 삽입은 빠른데 실무에서 자주 기본값이 아닌 이유는?

---