[C++] STL(Standard Template Library)

STL

C++에서 제공하는 표준 라이브러리로, 데이터를 효율적으로 저장하고 조작할 수 있도록 설계된 도구 모음

STL의 주요 특징

• 일관성 : 다양한 컨테이너에 동일한 문법으로 접근 가능(반복자, 알고리즘 덕분)
• 효율성 : 최적화된 자료구조와 알고리즘 제공
• 유연성 : 다양한 데이터 타입과 상황에 맞게 사용할 수 있는 템플릿 기반 설계

STL의 세 가지 주요 구성 요소

1. 컨테이너(Container) : 데이터를 저장하는 자료구조
2. 알고리즘(Algorithm) : 데이터를 조작하는 함수들
3. 반복자(Iterator) : 컨테이너와 알고리즘을 연결하는 다리 역할

STL  분류

1. 컨테이너

데이터를 저장하는 다양한 자료구조 제공 

• 순차 컨테이너 : 원소를 순차적으로 저장하며 크기가 동적으로 조절됨 ㅡ> 사용처 : 데이터의 순차적 접근 및 관리
  ex) vector, deque, list
• 연관 컨테이너 : 키를 기준으로 정렬된 상태로 저장 ㅡ> 사용처 : 정렬된 데이터 저장, 키 기반 검색
  ex) set, map, multiset, multimap
• 비순서 연관 컨테이너 : 해시 기반으로 저장하며, 빠른 검색 지원 ㅡ> 사용처 : 고속 검색이 필요한 경우
  ex) unordered_set, unordered_map
• 컨테이너 어댑터 : 내부적으로 다른 컨테이너를 기반으로 동작 ㅡ> 사용처 : LIFO/FIFO 데이터 관리
  ex) stack, queue, priority_queue

컨테이너 별 삽입 / 삭제 / 검색 시간 복잡도

컨테이너	삽입 (끝)	삽입 (중간/임의)	삭제 (끝)	삭제 (중간/임의)	검색
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))

2. 알고리즘

컨테이너에서 수행할 수 있는 작업들을 알고리즘으로 제공

주요 특징

• 컨테이너와 무관하게 동일한 문법 사용 가능
• 효율적으로 구현된 표준 함수 제공

자주 사용되는 STL 알고리즘

• sort : 컨테이너 내부 데이터 정렬 (시간 복잡도 : O(nlog n))
  ㅡ> 원리 : 내부적으로 퀵 정렬 사용, 최악의 경우 병합 정렬로 대체
• find : 특정 값 검색 (시간 복잡도 : O(n))
  ㅡ> 원리 : 처음부터 끝까지 값을 순차적으로 비교
• binary_search : 정렬된 컨테이너에서 이진 검색 (시간 복잡도 : O(log n))
  ㅡ> 원리 : 중간값과 비교하여 탐색 범위를 절반씩 줄여나감
• partition : 조건에 따라 데이터 분할 (시간 복잡도 : O(n))
  ㅡ> 원리 : 조건을 만족하는 원소를 앞으로, 만족하지 않는 원소를 뒤로 이동
• unique : 중복 원소 제거 (시간 복잡도 : O(n))
  ㅡ> 원리 : 인접한 중복 원소를 제거

3. 반복자

컨테이너의 원소를 순회하거나 특정 위치 접근 시 사용

반복자의 주요 유형

1. 순방향 반복자(Foward Iterator) : begin(), end()를 사용해 처음부터 끝까지 순회
2. 역방향 반복자(Reverse Iterator) : rbegin(), rend()를 사용해 끝에서부터 처음까지 순회
3. 특수 반복자 : advance(iterator, n) ㅡ> 반복자를 n만큼 이동, distance(first, last) ㅡ> 두 반복자 사이의 거리 반환

 

---

참고자료

https://bunnnybin.tistory.com/entry/C-STLStandard-Template-Library%EC%9D%B4%EB%9E%80

[C++] STL(Standard Template Library)이란?

https://eomgisan.tistory.com/26

[ C++ ] STL 정리하기 1. 컨테이너의 종류와 선택팁