C++ STL 컨테이너와 시간 복잡도

STL 컨테이너란

STL(Standard Template Library)은 C++ 표준 라이브러리 중 템플릿으로 만든 컨테이너·반복자·알고리즘 묶음이다. 컨테이너마다 내부 자료구조가 다르므로 어떤 연산을 자주 하느냐로 컨테이너를 고른다. 앞에 계속 삽입하는 문제에 vector를 쓰면 매번 O(n)을 치르게 된다.

분류	컨테이너	내부 구조
순차	`vector`	연속 메모리 동적 배열
순차	`deque`	고정 크기 블록들의 배열
순차	`list`	이중 연결 리스트
연관(정렬)	`set`, `map`, `multiset`, `multimap`	레드-블랙 트리
비정렬 연관	`unordered_set`, `unordered_map`	해시 테이블
어댑터	`stack`, `queue`, `priority_queue`	기본은 `deque`·`deque`·`vector` 위에 얹은 인터페이스

vector

vector는 힙에 연속 메모리를 잡는 동적 배열이다. 객체가 소멸할 때 원소 메모리도 함께 해제되므로 직접 delete할 필요가 없다. 내부에 시작 포인터, 원소 수(size), 확보한 칸 수(capacity)를 들고 있다.

연산	복잡도	이유
`v[i]`, `v.at(i)`	O(1)	시작 주소 + 오프셋 계산
`push_back`, `pop_back`	분할 상환 O(1)	뒤에 칸이 남아 있으면 그냥 쓴다
`insert`, `erase` (중간)	O(n)	뒤 원소를 한 칸씩 밀거나 당긴다
`find` (정렬 안 됨)	O(n)	처음부터 훑는다

capacity가 꽉 찬 상태에서 push_back하면 더 큰 메모리를 새로 잡고 기존 원소를 모두 옮긴다. 이 한 번은 O(n)이다. 그러나 용량을 일정 배수(libstdc++·libc++는 2배, MSVC는 1.5배)로 늘리므로 재할당은 드물게 일어나고, n번 삽입의 총비용이 O(n)으로 묶인다. 그래서 한 번당 분할 상환(amortized) O(1)이라 쓴다.

capacity: 1 → 2 → 4 → 8 → 16 ...
n번 push_back의 복사 횟수 ≤ 1 + 2 + 4 + ... + n < 2n  →  평균 O(1)

크기를 미리 알면 reserve(n)으로 한 번에 잡아 재할당과 복사를 없앤다.
재할당이 일어나면 기존 반복자·포인터·참조가 모두 무효화된다. 순회 중 push_back이 위험한 이유다.

헷갈리는 멤버 함수

함수	함정
`v[i]` vs `v.at(i)`	둘 다 원소의 참조를 돌려준다. `[]`는 범위를 검사하지 않아 벗어나면 정의되지 않은 동작이고, `at`은 검사해서 `std::out_of_range` 예외를 던진다
`pop_back()`	마지막 원소를 지우기만 하고 반환값이 없다(`void`). 값이 필요하면 `back()`으로 먼저 읽는다. 빈 벡터에 부르면 정의되지 않은 동작
`front()`, `back()`	첫·마지막 원소의 참조. 빈 벡터에서는 정의되지 않은 동작이므로 `empty()`로 먼저 확인한다
`size()` vs `capacity()`	들어 있는 원소 수와 재할당 없이 담을 수 있는 칸 수
`reserve(n)` vs `resize(n)`	`reserve`는 `capacity`만 늘리고 원소는 만들지 않는다(`size` 그대로). `resize`는 원소를 실제로 만들거나 지워 `size`를 바꾼다. `reserve` 뒤 `v[i] = x`는 범위 밖 접근이다
`clear()`	원소를 모두 소멸시켜 `size`는 0이 되지만 `capacity`(메모리)는 그대로 남는다
`shrink_to_fit()`	남는 용량을 돌려 달라는 요청이다. 구현이 무시해도 된다
`insert(it, x)`, `erase(it)`	위치를 인덱스가 아니라 반복자로 받는다(`v.begin() + i`). `erase`는 지운 다음 원소의 반복자를 돌려주므로 순회 중 삭제는 `it = v.erase(it)`로 잇는다
`begin()`/`cbegin()`, `rbegin()`	`c`가 붙으면 원소를 고칠 수 없는 상수 반복자, `r`이 붙으면 뒤에서 앞으로 도는 역방향 반복자
`data()`	내부 연속 메모리의 시작 포인터. C API에 배열로 넘길 때 쓴다

deque와 list

deque는 블록 단위로 메모리를 잡아 앞뒤 삽입·삭제가 모두 O(1)이고 임의 접근도 O(1)이다. 다만 원소가 연속되지 않아 캐시 효율은 vector보다 떨어진다. 자세한 구조는 큐와 덱 노트에 있다.
list는 위치(반복자)를 알면 어디서든 삽입·삭제가 O(1)이지만, 그 위치를 찾는 데 O(n)이 들고 노드가 흩어져 있어 실제로는 느린 경우가 많다.

set과 map

set은 중복 없이 늘 정렬된 상태를 유지한다. 이진 탐색 트리로 만들면 정렬된 데이터가 들어올 때 한쪽으로 기울어 O(n)이 되므로, 표준 구현은 스스로 균형을 잡는 레드-블랙 트리를 쓴다. map은 같은 트리에 키-값 쌍을 담는다.

연산	`set`/`map`	`unordered_set`/`unordered_map`
삽입 `insert`	O(log n)	평균 O(1), 최악 O(n)
탐색 `find`, `count`	O(log n)	평균 O(1), 최악 O(n)
삭제 `erase`	O(log n)	평균 O(1)
순회 순서	키 오름차순	순서 없음
범위 질의 `lower_bound`	가능	불가능

std::set<int> s;
s.insert(7);                       // O(log n)
if (s.find(7) != s.end()) { }      // 없으면 end() 반환
if (s.count(7)) { }                // set에서는 0 또는 1
if (s.contains(7)) { }             // C++20

"넣고 나서 있는지 자주 확인"하는 문제라면 set이, 순서가 필요 없으면 unordered_set이 맞다. 정렬 순회나 "k 이상인 첫 원소" 같은 범위 질의가 필요하면 트리 기반을 고른다.

정리

컨테이너는 자주 하는 연산의 복잡도로 고른다. 기본값은 vector다.
vector의 끝 삽입은 배수 증가 덕분에 분할 상환 O(1)이고, 중간 삽입·삭제는 O(n)이다.
재할당은 반복자를 무효화한다. 크기를 알면 reserve를 먼저 부른다.
앞뒤 삽입이 잦으면 deque, 정렬 유지와 범위 질의가 필요하면 set/map, 순서 없는 빠른 조회는 unordered_*를 쓴다.

버그 제보