C++ STL(Standard Template Library)

STL(Standard Template Library)의 정의

STL(Standard Template Library)은 C++ 표준 라이브러리의 핵심 구성 요소로, 자료구조와 알고리즘을 템플릿 기반으로 제공하여 코드의 재사용성과 효율성을 극대화한 라이브러리입니다.

주요 구성 요소로는 데이터를 저장하는 컨테이너(Container), 컨테이너의 원소에 접근을 일반화하는 반복자(Iterator), 그리고 데이터를 처리하는 알고리즘(Algorithm)이 있습니다.

이 세 요소를 조합하여 개발자가 직접 자료구조를 구현하는 수고를 덜고, 검증되고 최적화된 기능을 빠르고 안전하게 사용할 수 있습니다.

 

STL의 핵심 구성 요소

STL은 크게 3가지(넓게는 5가지) 핵심 요소가 유기적으로 연결되어 동작합니다.

구성 요소	설명	대표 예시
컨테이너 (Container)	데이터를 실제로 저장하고 관리하는 자료구조 클래스	vector, list, map, set
알고리즘 (Algorithm)	컨테이너의 데이터를 정렬, 탐색, 수정하는 템플릿 함수	sort, find, copy
반복자 (Iterator)	컨테이너와 알고리즘을 연결하는 '다리' 역할을 하는 범용 포인터	v.begin(), m.end()
함수 객체 (Functor)	함수처럼 동작하는 객체. 알고리즘의 동작을 커스터마이징할 때 사용	greater<int>, less<int>
어댑터 (Adapter)	기존 컨테이너의 인터페이스를 변경하여 새로운 자료구조처럼 사용하게 함	stack, queue, priority_queue

 

컨테이너(Container) 심화

컨테이너는 목적에 따라 크게 세 종류로 나뉩니다.

1. 시퀀스 컨테이너 (Sequence Container)
   • 특징 : 데이터를 선형(순차적)으로 저장합니다.
   • vector : 동적 배열. 임의 접근(O(1))이 빠르지만, 중간 삽입/삭제(O(n))가 느립니다.
   • list : 이중 연결 리스트. 삽입/삭제(O(1))가 빠르지만, 임의 접근(O(n))이 느립니다.
   • deque : Double-Ended Queue. 앞/뒤에서의 삽입/삭제(O(1))가 모두 빠릅니다.
2. 연관 컨테이너 (Associative Container)
   • 특징 : Key-Value 쌍으로 데이터를 저장하며, Key를 기준으로 자동 정렬됩니다.
   • map : Key와 Value를 쌍으로 저장. (레드-블랙 트리 기반) 탐색, 삽입, 삭제 모두 O(logn)
   • set : Key만 저장하며, 중복을 허용하지 않습니다. (레드-블랙 트리 기반) O(logn)
   • multimap, multiset : map, set과 유사하지만 Key의 중복을 허용합니다.
3. 비정렬 연관 컨테이너 (Unordered Associative Container)
   • 특징 : 해시 테이블을 기반으로 하며, 정렬되지 않습니다.
   • unordered_map, unordered_set : 평균적으로 탐색, 삽입, 삭제가 O(1)로 매우 빠르지만, 최악의 경우(해시 충돌) O(n)이 될 수 있습니다