[Modern C++] STL 자료구조

C++ 표준 라이브러리(std)에서 제공하는 주요 자료구조(Container)들은 크게 Sequence Container(순차 컨테이너), Associative Container(연관 컨테이너), Unordered Container(비순서 연관 컨테이너), Container Adapter(컨테이너 어댑터)로 나눌 수 있습니다.

---

1. Sequence Container (순차 컨테이너)

요소를 특정 순서로 저장하는 컨테이너입니다.

컨테이너	설명	특징
std::vector	동적 크기 배열	- 빠른 임의 접근(O(1)) - 끝에서 추가/삭제 O(1), 중간 삽입/삭제 O(n)
std::deque	양쪽 끝에서 삽입/삭제 가능한 동적 배열	- 앞뒤에서 O(1) 삽입/삭제 - 랜덤 접근 가능(O(1))
std::list	이중 연결 리스트	- 중간 삽입/삭제 O(1) - 랜덤 접근 불가 (O(n))
std::forward_list	단일 연결 리스트	- std::list보다 메모리 절약 - 단방향 순회 가능
std::array	고정 크기 배열	- 크기가 고정된 std::vector 대체 - O(1) 임의 접근
std::span (C++20)	배열 뷰(소유권 없음)	- 원본 데이터를 수정하지 않고 참조 가능

---

2. Associative Container (연관 컨테이너)

자동 정렬된 키-값 데이터를 저장하는 컨테이너입니다.

컨테이너	설명	특징
std::set	중복 없는 정렬된 집합	- 삽입/삭제/탐색 O(log n)
std::multiset	중복 허용 정렬된 집합	- std::set과 같지만 중복 허용
std::map	키-값 쌍 저장, 정렬된 연관 배열	- 키 기반 탐색 O(log n)
std::multimap	중복 허용 정렬된 맵	- std::map과 같지만 키 중복 허용

• 내부적으로 Red-Black Tree(레드-블랙 트리) 기반으로 동작하여 자동 정렬이 유지됩니다.

---

3. Unordered Container (비순서 연관 컨테이너)

해시 기반의 연관 컨테이너로 정렬되지 않지만 평균적으로 탐색/삽입/삭제가 O(1) 입니다.

컨테이너	설명	특징
std::unordered_set	중복 없는 해시 기반 집합	- std::set과 같지만 해시 사용
std::unordered_multiset	중복 허용 해시 기반 집합	- std::multiset과 같지만 해시 사용
std::unordered_map	해시 기반 키-값 저장소	- std::map보다 빠름 (평균 O(1))
std::unordered_multimap	중복 허용 해시 기반 맵	- std::multimap과 같지만 해시 사용

• 내부적으로 **Hash Table(해시 테이블)**을 사용합니다.

---

4. Container Adapter (컨테이너 어댑터)

기존 컨테이너(vector, deque, list)를 기반으로 동작하며, 특정 동작을 제한하여 활용할 수 있는 컨테이너입니다.

컨테이너	설명	기본 컨테이너
std::stack	LIFO(Last-In, First-Out) 스택	std::deque (기본값)
std::queue	FIFO(First-In, First-Out) 큐	std::deque (기본값)
std::priority_queue	우선순위 큐 (최대 힙)	std::vector (기본값)

• std::stack과 std::queue는 list 또는 vector 기반으로도 사용할 수 있습니다.
• std::priority_queue는 내부적으로 힙(Heap) 자료구조를 사용하여 최댓값 또는 최솟값을 빠르게 찾을 수 있습니다.

---

요약

• 배열 기반: vector, deque, array, span
• 연결 리스트 기반: list, forward_list
• 정렬된 연관 컨테이너: set, map, multiset, multimap
• 해시 기반 연관 컨테이너: unordered_set, unordered_map, unordered_multiset, unordered_multimap
• 어댑터: stack, queue, priority_queue

어떤 자료구조를 사용할지 선택할 때는 삽입/삭제/탐색의 시간 복잡도, 메모리 사용량, 정렬 여부 등을 고려해야 합니다. 🚀