1. STL의 개념
1-1. 배경
C++로 프로그래밍을 하다 보면 동적 배열, 연결 리스트, 정렬, 검색 같은 자료구조와 알고리즘을 반복적으로 구현하게 된다. 프로젝트마다 매번 새로 만들면 시간도 낭비되고, 버그가 생길 가능성도 높아진다.
이런 문제를 해결하기 위해 자주 사용되는 자료구조와 알고리즘을 미리 만들어서 표준 라이브러리에 포함 시킨 것이 STL이다.
1-2. STL이란?
STL(Standard Template Library)은 C++ 표준 라이브러리에 포함된 템플릿 기반의 자료구조와 알고리즘 모음 이다. 이름에 "Template"이 들어있는 것처럼, 앞서 배운 클래스 템플릿과 함수 템플릿으로 만들어져 있다. 그래서 vector<int>, vector<string>처럼 어떤 타입이든 담을 수 있다.
1-3. 성능
STL은 단순히 편리하기만 한 것이 아니라 성능도 보장 된다. 각 컨테이너와 알고리즘의 시간 복잡도가 표준에 명시되어 있다. vector의 인덱스 접근은 O(1), map의 검색은 O(log n), unordered_map의 검색은 평균 O(1)이 보장된다.
직접 구현한 것보다 STL이 느릴까 걱정할 수 있지만, STL은 수십 년간 최적화되어 온 코드다. 대부분의 경우 직접 구현하는 것보다 STL을 사용하는 것이 더 빠르고 안전하다.
2. 구성요소
STL은 크게 컨테이너, 반복자, 알고리즘 세 가지로 구성된다. 컨테이너가 데이터를 저장하고, 반복자가 컨테이너의 요소를 가리키며, 알고리즘이 반복자를 통해 데이터를 처리한다.
2-1. 컨테이너
컨테이너(Container)는 데이터를 저장하는 객체 다. 직접 만들었던 동적 배열, 연결 리스트, 해시 테이블 같은 것들을 STL이 제공하는 것이다. 컨테이너는 데이터를 저장하는 방식에 따라 순차 컨테이너 와 연관 컨테이너 로 나뉜다.
2-2. 순차 컨테이너
순차 컨테이너는 데이터를 삽입한 순서대로 저장한다.
벡터 (vector)
vector는 동적 배열 이다. 이전에 직접 구현했던 DynamicArray와 같은 원리로, 크기가 자동으로 늘어나는 배열이다.
#include <vector>
int main() {
vector<int> v;
// 삽입
v.push_back(10);
v.push_back(20);
v.push_back(30);
// 인덱스 접근 — O(1)
cout << v[0] << endl; // 10
cout << v[1] << endl; // 20
// 크기 확인
cout << v.size() << endl; // 3
cout << v.capacity() << endl; // 할당된 전체 용량
// 마지막 요소 제거
v.pop_back(); // 30 제거
// 범위 기반 for문으로 순회
for (int x : v) {
cout << x << " ";
}
// 출력: 10 20
return 0;
}
push_back()으로 뒤에 추가하고, pop_back()으로 뒤에서 제거한다. JavaScript의 push()/pop()과 같은 동작이다. 인덱스로 바로 접근할 수 있어서 O(1)이지만, 중간 삽입/삭제는 뒤의 요소를 밀어야 하므로 O(n)이다.
vector는 가장 많이 사용되는 컨테이너다. 특별한 이유가 없으면 vector를 기본 선택으로 쓰는 것이 일반적이다.
at() 메서드를 사용하면 범위를 벗어났을 때 out_of_range 예외를 던져주므로 더 안전하다. [] 연산자는 범위 체크를 하지 않는다.
cout << v.at(10) << endl; // 범위 초과 시 예외 발생
cout << v[10] << endl; // 범위 초과해도 예외 없음 — 위험
데크 (deque)
deque(Double-Ended Queue)는 양쪽 끝에서 삽입/삭제가 빠른 자료구조 다. vector는 뒤에서만 빠르게 추가/삭제할 수 있지만, deque는 앞에서도 O(1)으로 가능하다.
#include <deque>
int main() {
deque<int> dq;
// 뒤에 삽입
dq.push_back(10);
dq.push_back(20);
// 앞에 삽입
dq.push_front(5);
dq.push_front(1);
// 현재 상태: 1, 5, 10, 20
// 인덱스 접근 가능
cout << dq[0] << endl; // 1
cout << dq[3] << endl; // 20
// 앞에서 제거
dq.pop_front(); // 1 제거
// 뒤에서 제거
dq.pop_back(); // 20 제거
for (int x : dq) {
cout << x << " ";
}
// 출력: 5 10
return 0;
}
vector와 마찬가지로 인덱스 접근이 O(1)이지만, 내부 구조가 다르다. vector는 하나의 연속 메모리 블록이고, deque는 여러 개의 블록을 연결한 구조다. 앞뒤 삽입/삭제가 모두 빈번한 경우에 deque가 적합하다.
리스트 (list)
list는 이중 연결 리스트(Doubly Linked List) 다. 이전에 직접 구현했던 단일 연결 리스트와 달리, 각 노드가 앞 노드와 뒷 노드 모두를 가리킨다.
#include <list>
int main() {
list<int> lst;
lst.push_back(10);
lst.push_back(20);
lst.push_back(30);
lst.push_front(5);
// 현재 상태: 5, 10, 20, 30
// 인덱스 접근 불가! lst[0]은 에러
// 반복자로 순회해야 함
for (int x : lst) {
cout << x << " ";
}
// 출력: 5 10 20 30
cout << endl;
// 중간 삽입 — 반복자를 사용
auto it = lst.begin();
advance(it, 2); // 2번째 위치로 이동
lst.insert(it, 15); // 10과 20 사이에 15 삽입
for (int x : lst) {
cout << x << " ";
}
// 출력: 5 10 15 20 30
// 특정 값 삭제
lst.remove(20); // 값이 20인 요소 전부 삭제
return 0;
}
list는 어디서든 삽입/삭제가 O(1)이지만(위치를 이미 알고 있을 때), 인덱스로 바로 접근할 수 없다. lst[3] 같은 접근이 불가능하고, 처음부터 순서대로 따라가야 한다. 앞서 배운 연결 리스트의 특성 그대로다.
세 순차 컨테이너의 선택 기준을 정리하면 이렇다. 대부분의 경우 vector 를 쓴다. 앞쪽 삽입/삭제가 빈번하면 deque 를 쓴다. 중간 삽입/삭제가 매우 빈번하고 인덱스 접근이 필요 없으면 list 를 쓴다.
2-3. 정렬 연관 컨테이너
연관 컨테이너는 데이터를 키(key) 기반으로 자동 정렬 하여 저장한다. 삽입 순서가 아니라 키 값에 따라 위치가 결정된다.
셋 (set)
set은 중복 없는 값들의 집합 이다. 값을 넣으면 자동으로 정렬되고, 같은 값을 두 번 넣으면 하나만 유지된다.
#include <set>
int main() {
set<int> s;
s.insert(30);
s.insert(10);
s.insert(50);
s.insert(20);
s.insert(10); // 중복 — 무시됨
// 자동 정렬되어 저장
for (int x : s) {
cout << x << " ";
}
// 출력: 10 20 30 50
cout << endl;
// 검색 — O(log n)
if (s.find(20) != s.end()) {
cout << "20 존재" << endl;
}
// 개수 확인 (set에서는 0 또는 1)
cout << s.count(10) << endl; // 1
cout << s.count(99) << endl; // 0
// 삭제
s.erase(30);
cout << "크기: " << s.size() << endl; // 3
return 0;
}
set은 내부적으로 균형 이진 탐색 트리(레드-블랙 트리) 로 구현되어 있어서, 삽입·검색·삭제 모두 O(log n) 이다. 수학에서의 집합과 같은 개념이다.
중복을 허용하지 않으므로, 데이터에서 고유한 값만 추출하고 싶을 때 유용하다. 예를 들어 배열의 중복을 제거하려면 set에 전부 넣으면 된다.
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
set<int> unique(arr, arr + 10);
// unique: {1, 2, 3, 4, 5, 6, 9}
맵 (map)
map은 키-값(key-value) 쌍을 키 기준으로 정렬하여 저장하는 컨테이너 다. 이전에 배운 해시맵(unordered_map)과 비슷하지만, map은 키가 자동 정렬 된다는 차이가 있다.
#include <map>
int main() {
map<string, int> scores;
// 삽입
scores["홍길동"] = 90;
scores["김철수"] = 85;
scores["이영희"] = 95;
scores["박민수"] = 78;
// 키 기준으로 자동 정렬 (문자열은 사전순)
for (auto &pair : scores) {
cout << pair.first << ": " << pair.second << endl;
}
// 김철수: 85
// 박민수: 78
// 이영희: 95
// 홍길동: 90
// 검색 — O(log n)
if (scores.find("김철수") != scores.end()) {
cout << "김철수의 점수: " << scores["김철수"] << endl;
}
// 삭제
scores.erase("박민수");
// 존재하지 않는 키에 []로 접근하면 자동으로 생성됨 (주의!)
cout << scores["없는사람"] << endl; // 0 (int의 기본값으로 생성됨)
return 0;
}
map은 set과 마찬가지로 레드-블랙 트리로 구현되어 삽입·검색·삭제가 O(log n) 이다. unordered_map의 평균 O(1)보다는 느리지만, 키가 정렬되어 있어야 하는 경우(범위 검색, 순서대로 출력 등)에는 map이 필요하다.
주의할 점은 [] 연산자로 존재하지 않는 키에 접근하면 해당 키가 자동으로 생성 된다는 것이다. 단순히 존재 여부를 확인하려면 find()나 count()를 사용해야 한다.
map과 unordered_map의 선택 기준을 정리하면 이렇다. 키 순서가 필요하면 map(O(log n))을 쓰고, 순서가 필요 없고 속도가 중요하면 unordered_map(평균 O(1))을 쓴다.
3. 반복자
3-1. 반복자란?
반복자(Iterator)는 컨테이너의 요소를 가리키는 객체 다. 포인터와 비슷하게 동작하지만, 포인터보다 추상화된 개념이다.
배열에서는 포인터로 요소를 순회할 수 있었다. 하지만 set이나 map은 연속된 메모리가 아니라 트리 구조이므로 포인터로 순회할 수 없다. 반복자는 컨테이너의 내부 구조에 관계없이 동일한 방식으로 요소를 순회 할 수 있게 해준다.
vector<int> v = {10, 20, 30, 40, 50};
// 반복자 선언과 사용
vector<int>::iterator it;
for (it = v.begin(); it != v.end(); it++) {
cout << *it << " ";
}
// 출력: 10 20 30 40 50
v.begin()은 첫 번째 요소를 가리키는 반복자를 반환하고, v.end()는 마지막 요소의 다음 위치 를 가리킨다. *it로 반복자가 가리키는 값에 접근하고, it++로 다음 요소로 이동한다. 포인터와 사용법이 거의 같다.
auto 키워드를 쓰면 타입을 직접 쓰지 않아도 된다.
for (auto it = v.begin(); it != v.end(); it++) {
cout << *it << " ";
}
범위 기반 for문(for (int x : v))은 사실 내부적으로 반복자를 사용하는 것이다. 대부분의 순회에서는 범위 기반 for문이 간편하지만, 요소를 삭제하거나 특정 위치를 조작해야 할 때는 반복자를 직접 사용해야 한다.
// 반복자로 특정 요소 삭제
vector<int> v = {10, 20, 30, 40, 50};
auto it = v.begin() + 2; // 세 번째 요소 (30)
v.erase(it); // 30 삭제
// v: {10, 20, 40, 50}
모든 STL 컨테이너는 반복자를 제공한다. vector, deque, list, set, map 전부 begin()과 end()를 가진다. 컨테이너가 바뀌어도 반복자를 쓰는 방식은 동일하다. 이것이 반복자의 핵심 가치다.
set<int> s = {30, 10, 50, 20};
for (auto it = s.begin(); it != s.end(); it++) {
cout << *it << " ";
}
// 출력: 10 20 30 50 (자동 정렬)
map의 반복자는 pair를 가리킨다. it->first로 키에, it->second로 값에 접근한다.
map<string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}};
for (auto it = m.begin(); it != m.end(); it++) {
cout << it->first << ": " << it->second << endl;
}
4. 알고리즘
STL 알고리즘은 <algorithm> 헤더에 포함되어 있으며, 반복자를 통해 컨테이너의 데이터를 처리 한다. 컨테이너의 종류에 관계없이 동일한 알고리즘을 적용할 수 있다.
4-1. find
find는 범위 안에서 특정 값을 검색 한다. 순차 검색을 수행하며, 찾으면 해당 요소를 가리키는 반복자를, 못 찾으면 end()를 반환한다.
#include <algorithm>
#include <vector>
int main() {
vector<int> v = {10, 20, 30, 40, 50};
auto it = find(v.begin(), v.end(), 30);
if (it != v.end()) {
cout << "찾음: " << *it << endl; // 찾음: 30
cout << "인덱스: " << (it - v.begin()) << endl; // 인덱스: 2
} else {
cout << "못 찾음" << endl;
}
return 0;
}
find(시작 반복자, 끝 반복자, 찾을 값) 형태로 호출한다. vector뿐 아니라 deque, list 등 어떤 순차 컨테이너에서도 같은 방식으로 사용할 수 있다.
다만 set이나 map에서는 find 알고리즘 대신 컨테이너 자체의 find 멤버함수 를 쓰는 것이 좋다. set::find()는 트리 구조를 활용해 O(log n)이지만, 알고리즘 find()는 순차 검색이라 O(n)이기 때문이다.
set<int> s = {10, 20, 30, 40, 50};
// 좋은 방법 — O(log n)
auto it = s.find(30);
// 나쁜 방법 — O(n)
auto it2 = find(s.begin(), s.end(), 30);
4-2. sort
sort는 범위 안의 요소를 정렬 한다. 기본적으로 오름차순이며, 비교 함수를 넘겨서 정렬 기준을 바꿀 수 있다.
#include <algorithm>
#include <vector>
int main() {
vector<int> v = {50, 20, 40, 10, 30};
// 오름차순 정렬
sort(v.begin(), v.end());
for (int x : v) {
cout << x << " ";
}
// 출력: 10 20 30 40 50
cout << endl;
// 내림차순 정렬
sort(v.begin(), v.end(), greater<int>());
for (int x : v) {
cout << x << " ";
}
// 출력: 50 40 30 20 10
return 0;
}
sort(시작, 끝) 으로 오름차순, sort(시작, 끝, greater<타입>()) 으로 내림차순 정렬한다. 시간 복잡도는 O(n log n) 으로, 내부적으로 인트로소트(Introsort)라는 효율적인 알고리즘을 사용한다.
비교 함수를 직접 만들어서 커스텀 정렬을 할 수도 있다. C에서 qsort에 비교 함수를 넘겼던 것과 같은 원리다.
// 절댓값 기준으로 정렬
bool absCompare(int a, int b) {
return abs(a) < abs(b);
}
vector<int> v = {-5, 3, -1, 4, -2};
sort(v.begin(), v.end(), absCompare);
// 결과: -1 -2 3 4 -5
람다 표현식을 사용하면 비교 함수를 인라인으로 작성할 수도 있다.
// 구조체 벡터를 점수 기준으로 정렬
struct Student {
string name;
int score;
};
vector<Student> students = {
{"홍길동", 90},
{"김철수", 75},
{"이영희", 85}
};
sort(students.begin(), students.end(), [](const Student &a, const Student &b) {
return a.score > b.score; // 점수 내림차순
});
for (auto &s : students) {
cout << s.name << ": " << s.score << endl;
}
// 홍길동: 90
// 이영희: 85
// 김철수: 75
sort는 임의 접근 반복자(Random Access Iterator) 를 요구하므로 vector와 deque에서 사용할 수 있다. list는 임의 접근이 안 되므로 sort 알고리즘을 쓸 수 없고, 대신 list 자체의 sort() 멤버함수를 사용해야 한다.
list<int> lst = {50, 20, 40, 10, 30};
lst.sort(); // list 자체의 sort 멤버함수
마무리
STL은 C++ 프로그래밍의 생산성을 크게 높여주는 도구다. 직접 구현했던 동적 배열은 vector로, 연결 리스트는 list로, 해시맵은 unordered_map으로 대체할 수 있다. 반복자라는 추상화 덕분에 컨테이너가 바뀌어도 순회하는 코드는 동일하게 유지되고, find나 sort 같은 알고리즘도 컨테이너에 관계없이 적용할 수 있다. 자료구조의 원리를 이해한 상태에서 STL을 사용하면, 적재적소에 맞는 컨테이너를 선택하고 효율적인 코드를 작성할 수 있다.