[C++] STL 컨테이너 선택 가이드

개요

C++에서는 데이터를 효율적으로 저장하고 조작할 수 있도록 설계된 도구 모음인 STL (Standard Template Library)을 제공하고 있다. STL에는 vector, list, map ... 등 많은 요소들이 포함되어있다. 각자 어떤 상황에 유용하게 쓰이는지 알아보자 !

 

---

1. 컨테이너 종류

① 순차 컨테이너

vector, deque, list 

• 원소를 순차적으로 저장하며 크기가 동적으로 조절됨
• vector : 연속된 메모리 할당으로 빠른 인덱스 접근
• deque : 앞뒤에서 삽입 / 삭제가 효율적
• list : 이중 연결 리스트 구조로 삽입 / 삭제에 최적화

---

② 연관 컨테이너

set, map, multiset, multimap

• 키를 기준으로 정렬된 상태로 저장
• 내부적으로 이진검색트리(Red-Black Tree) 기반으로 동작
• 대표 사례 : 정렬된 데이터 저장, 키 기반 검색
• set / map : 중복 불허
• multiset / multimap : 중복 허용

---

③ 비순서 연관 컨테이너

unordered_set, unordered_map, unordered_multiset, unordered_multimap

• 해시 기반으로 저장하며, 빠른 검색을 지원
• 해시 값 충돌시 성능 저하
• 대표 사례 : 빠른 검색이 필요한 경우

---

④ 컨테이너 어댑터

stack, queue, priority_queue

• 내부적으로 다른 컨테이너(vector, deque, list)를 기반으로 동작
• 대표 사례 : LIFO(stack) / FIFO(queue) 데이터 관리

---

2. 컨테이너 선택 가이드

• 데이터가 순차적으로 추가/삭제된다면 vector
• 양쪽 끝에서 삽입/삭제가 빈번하면 deque
• 노드 단위로 삽입/삭제가 많다면 list
• 키 기반 검색이나 정렬이 필요하다면 map이나 set
• 검색 속도가 가장 중요하다면 unordered_map이나 unordered_set

 

 

---

3. 삽입 / 삭제 / 검색 시간 복잡도

컨테이너	삽입(끝)	삽입(임의)	삭제(끝)	삭제(임의)	검색
vector	O(1)	O(n)	O(1)	O(n)	O(n)
deque	O(1)	O(n)	O(1)	O(n)	O(n)
list	O(1)	O(1)	O(1)	O(1)	O(n)
set	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
map	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
unordered_set	O(1)*	O(1)*	O(1)*	O(1)*	O(1)*
unordered_map	O(1)*	O(1)*	O(1)*	O(1)*	O(1)*

 

*은 평균 시간 복잡도를 의미하며, 해시 충돌이 발생할 경우 최악의 시간 복잡도는 O(n)이다.

---

느낀 점

 

STL에는 다양한 자료구조가 포함되어 있지만, 용도를 명확히 알지 못해 주로 vector만 사용했다. 이로 인해 중복을 허용하지 않아야 하는 상황에서도 vector를 사용해 erase와 unique를 어쩔 수 없이 조합해야 했다. 하지만, 만약 set을 사용했다면 훨씬 간단하게 구현할 수 있었을 것이다.

프로그래밍을 하다 보면 "이런 기능은 없을까?"라는 생각이 들 때가 있는데, 찾아보면 놀랍게도 이미 제공되는 경우가 많았다. 방금 언급한 set이 바로 그런 예시 중 하나이다. STL은 알고리즘 문제를 해결할 때 매우 유용하게 활용할 수 있을 것 같다.