STL이란?
STL(Standard Template Library)은 C++의 내장 템플릿 라이브러리로, 컨테이너, 반복자(Iterator), 알고리즘 세 가지 요소로 구성됨.
- 컨테이너(Container): 데이터를 저장·관리하는 자료구조
- 반복자(Iterator): 컨테이너 내 데이터를 순회하는 포인터 역할
- 알고리즘(Algorithm): 정렬, 탐색, 삽입, 삭제 등 다양한 기능 제공
STL을 잘 활용하면 코딩 테스트에서 시간을 크게 절약할 수 있음. 직접 자료구조를 구현하는 것보다 훨씬 효율적.
STL의 3가지 요소
이 세 가지 요소는 서로 연동되어 강력한 기능을 제공함.
- 컨테이너 → 데이터를 담는 창고
- 반복자 → 창고 정리하는 도우미
- 알고리즘 → 문제 해결을 돕는 용병
1. 컨테이너 (Container)
데이터를 저장하는 구조로, vector, list, deque 등이 있음.
vector (동적 배열)
- 연속된 메모리 블록을 사용해 랜덤 접근이 빠름
- push_back() / pop_back() 으로 끝부분 추가·삭제 효율적
- 중간 삽입·삭제 시 데이터 이동이 발생해 비효율적
📌 주요 함수
vector<int> v;
v.push_back(10); // 맨 뒤 추가
v.pop_back(); // 맨 뒤 삭제
v.insert(v.begin() + 1, 20); // 중간 삽입
v.erase(v.begin() + 2); // 중간 삭제list (이중 연결 리스트)
- 중간 삽입·삭제 빠름 (포인터만 변경하면 됨)
- 메모리가 연속적이지 않아 랜덤 접근 느림
- 순차적 추가·삭제에 적합
📌 주요 함수
list<int> lst;
lst.push_back(30);
lst.push_front(20);
lst.insert(next(lst.begin()), 25); // 중간 삽입
lst.erase(lst.begin()); // 첫 번째 원소 삭제deque (양방향 동적 배열)
- 양쪽 끝 삽입·삭제 빠름
- 랜덤 접근 가능
- 중간 삽입·삭제는 비효율적
📌 주요 함수
deque<int> dq;
dq.push_back(10);
dq.push_front(20);
dq.pop_back();
dq.pop_front();
Map (Key - Value)
- (key, value) 쌍을 저장하는 자료구조
- 키를 통해 값을 빠르게 탐색 가능
- 레드-블랙 트리 기반 → 검색, 삽입, 삭제 O(log N)
- 키는 유일하며 자동 정렬됨
📌 주요 함수
map<int, string> mp;
mp.insert({1, "Apple"}); //키-값 쌍 삽입
mp[2] = "Banana"; // operator[key]키로 값에 접근 또는 삽입
if (mp.find(1) != mp.end()) // 키로 요소 검색 (iterator 반환)
mp.erase(2); // 키로 요소 제거
int size = mp.size(); // 요소 개수 반환
Set
- 유일한 키만 저장 (중복 불가)
- 레드-블랙 트리 기반 → O(log N)
- 자동 정렬됨
📌 주요 함수
set<int> s;
s.insert(10);
s.insert(5);
s.insert(20);
if (s.find(10) != s.end())
cout << "10 exists in set" << endl;
s.erase(5);
cout << "Set size: " << s.size() << endl;
// lower_bound(value), upper_bound(value)
cout << "Lower bound of 10: " << *s.lower_bound(10) << endl;
cout << "Upper bound of 10: " << *s.upper_bound(10) << endl;
}2. 반복자 (Iterator)
컨테이너 원소를 순회하는 포인터 역할.
- begin(), end() → 순차 탐색
- rbegin(), rend() → 역순 탐색
- ++it, --it → 이동
- *it → 값 참조
📌 반복자 사용 예시
vector<int> v = {3, 1, 4, 1, 5, 9};
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
cout << *it << " ";
}3. 알고리즘 (Algorithm)
STL이 제공하는 다양한 기능 활용 가능.
📌 정렬 예시
vector<int> v = {3, 1, 4, 1, 5, 9};
sort(v.begin(), v.end()); // 정렬
📌 이진 탐색 예시
binary_search(v.begin(), v.end(), 4); // 4가 존재하면 true어떤 컨테이너를 써야 할까?
✔ 중간 삽입/삭제 많음 → list
✔ 랜덤 접근 필요 → vector
✔ 양쪽 끝 추가/삭제 많음 → deque