[C++] STL 컨테이너 정리

이전 글에서 vector와 list, map과 unordered_map의 차이를 각각 정리해보았다.

이번 글에서는 개별 컨테이너의 세부 구현보다는
STL 컨테이너가 전체적으로 어떻게 분류되는지,
그리고 반복자 기준으로 어떤 차이가 있는지 정리해보려고 한다.

---

STL 컨테이너란?

STL 컨테이너는 데이터를 효율적으로 저장, 관리, 조작하기 위한 클래스 템플릿 자료구조이다.

템플릿 기반이므로 컴파일 타임에 타입 검사가 이루어져 타입 안정성이 높고,
반복자를 통해 컨테이너의 원소에 공통된 방식으로 접근할 수 있다.

또한 반복자를 이용하면 algorithm 라이브러리의 함수들과 함께 사용할 수 있다.

STL 컨테이너는 크게 다음과 같이 나눌 수 있다.

• 시퀀스 컨테이너
• 연관 컨테이너
• 컨테이너 어댑터

각 분류는 데이터를 저장하는 방식과 제공하는 인터페이스가 다르다.

---

1. 시퀀스 컨테이너

시퀀스 컨테이너는 데이터를 선형 순서로 저장하는 컨테이너이다.
원소들이 순서를 가지고 저장되며 대체로 삽입된 순서를 기준으로 데이터를 관리한다.

대표적인 시퀀스 컨테이너는 다음과 같다.

• vector
• array
• deque
• list
• forward_list

반복자 기준으로 보면 다음과 같이 나눌 수 있다.

• vector, array, deque : 임의 접근 반복자 지원
• list : 양방향 반복자 지원
• forward_list : 정방향 반복자 지원

vector, array, deque는 it + n 같은 이동이 가능하고,
인덱스를 이용한 빠른 접근도 가능하다.

반면 list는 앞뒤 이동은 가능하지만 임의 접근은 불가능하고,
forward_list는 앞으로만 이동할 수 있다.

---

2. 연관 컨테이너

연관 컨테이너는 key를 기준으로 데이터를 저장하고 탐색하는 컨테이너이다.

연관 컨테이너는 다시 두 가지로 나눌 수 있다.

• 정렬 연관 컨테이너
• 비정렬 연관 컨테이너

---

정렬 연관 컨테이너

정렬 연관 컨테이너는 key를 기준으로 정렬된 상태를 유지한다.

대표적인 컨테이너는 다음과 같다.

• map
• set
• multimap
• multiset

map은 key-value 쌍으로 데이터를 저장하고,
set은 저장하는 값 자체가 key 역할을 한다.

multimap, multiset은 중복 key를 허용하는 버전이다.

정렬 연관 컨테이너는 보통 트리 구조를 사용하며 탐색, 삽입, 삭제가 O(log N)이다.
또한 양방향 반복자를 지원하므로 iterator를 앞뒤로 이동할 수 있다.

---

비정렬 연관 컨테이너

비정렬 연관 컨테이너는 정렬 순서를 유지하지 않고 해시 기반으로 데이터를 저장한다.

대표적인 컨테이너는 다음과 같다.

• unordered_map
• unordered_set
• unordered_multimap
• unordered_multiset

평균적으로 탐색, 삽입, 삭제가 O(1)이지만,
해시 충돌이 많아지면 최악의 경우 O(N)까지 나빠질 수 있다.

비정렬 연관 컨테이너는 정방향 반복자를 지원한다.
따라서 순회는 가능하지만 정렬된 순서나 삽입 순서를 기대하면 안 된다.

---

3. 컨테이너 어댑터

컨테이너 어댑터는 기존 컨테이너를 바탕으로 기능을 제한하여
특정한 형태로 동작하게 만든 컨테이너이다.

대표적인 컨테이너 어댑터는 다음과 같다.

• stack
• queue
• priority_queue

컨테이너 어댑터는 일반적인 반복자를 제공하지 않는다.

즉, 내부 원소를 자유롭게 순회하기보다는
정해진 인터페이스를 통해 원소를 넣고 빼는 방식으로 사용한다.

각 어댑터의 특징은 다음과 같다.

• stack : 후입선출, LIFO
• queue : 선입선출, FIFO
• priority_queue : 우선순위가 높은 원소가 먼저 나옴

기본적으로 stack과 queue는 deque,
priority_queue는 vector를 내부 컨테이너로 사용한다.

---

컨테이너 분류 정리

분류	컨테이너	특징
시퀀스 컨테이너	vector, array, deque, list, forward_list	데이터를 선형 순서로 저장
정렬 연관 컨테이너	map, set, multimap, multiset	key 기준 정렬 유지
비정렬 연관 컨테이너	unordered_map, unordered_set, unordered_multimap, unordered_multiset	해시 기반, 순서 보장 없음
컨테이너 어댑터	stack, queue, priority_queue	제한된 인터페이스 제공

---

반복자 기준 정리

반복자 종류	컨테이너
임의 접근 반복자	vector, array, deque
양방향 반복자	list, map, set, multimap, multiset
정방향 반복자	forward_list, unordered_map, unordered_set, unordered_multimap, unordered_multiset
반복자 없음	stack, queue, priority_queue

반복자 종류에 따라 사용할 수 있는 알고리즘도 달라진다.

예를 들어 std::sort는 임의 접근 반복자가 필요하므로
vector에는 사용할 수 있지만 list에는 사용할 수 없다.

list는 대신 자체 멤버 함수인 list::sort()를 제공한다.

---

컨테이너 선택 기준

컨테이너를 선택할 때는 다음과 같이 생각할 수 있다.

• 빠른 임의 접근과 캐시 효율이 중요하다면 vector
• 고정 크기 배열이 필요하다면 array
• 앞뒤 삽입과 삭제가 필요하다면 deque
• 중간 삽입 / 삭제 위치를 알고 있고 iterator 안정성이 중요하다면 list
• 정렬된 key 기반 탐색이 필요하다면 map / set
• 정렬이 필요 없고 빠른 key 검색이 중요하다면 unordered_map / unordered_set
• LIFO, FIFO, 우선순위 큐 형태의 제한된 인터페이스가 필요하다면 컨테이너 어댑터

---

마무리

이번 글에서는 STL 컨테이너를 세부 구현보다는
분류와 반복자 관점에서 정리해보았다.

이전에 vector, list, map, unordered_map을 따로 정리했지만,
전체 컨테이너를 한 번에 분류해보니
각 컨테이너가 어떤 목적과 인터페이스를 가지는지 더 잘 보였다.

앞으로 컨테이너를 선택할 때는
단순히 익숙한 컨테이너를 사용하는 것이 아니라,
데이터 저장 방식, 반복자 종류, 정렬 필요 여부, 접근 패턴을 함께 고려해서 선택해야겠다.