STL(Standard Template Library)은 C++ 표준 라이브러리 중에서 컨테이너(Container), 반복자(Iterator), 알고리즘(Algorithm), 함수 객체(Function Object) 등을 묶어서 제공하는 구성요소입니다.
•
컨테이너: 데이터를 저장하는 그릇 (vector, list, map …)
•
반복자: 컨테이너를 순회하는 포인터 비슷한 인터페이스 (begin/end)
•
알고리즘: 반복자를 받아서 동작하는 범용 함수 (sort, find …)
•
어댑터: 기존 컨테이너/구조를 감싸서 다른 동작을 제공 (stack, queue)
핵심 감각
•
컨테이너가 다르면 메모리 배치와 연산 복잡도가 달라집니다.
•
알고리즘은 “어떤 컨테이너인지”보다 “반복자로 순회가 가능한지”가 중요합니다.
•
그래서 STL을 잘 쓰면, 자료구조/알고리즘 지식이 코드로 바로 연결됩니다.
<vector>
•
언제 쓰나
◦
데이터가 연속 메모리에 있으면 좋은 경우 (빠른 인덱싱, 캐시 효율)
◦
뒤쪽에 추가/삭제가 자주 일어나는 경우
•
특징
◦
v[i] 같은 임의 접근(random access) 이 매우 빠릅니다.
◦
중간 삽입/삭제는 느릴 수 있습니다. (뒤의 요소들을 한 칸씩 밀어야 함)
◦
capacity가 부족하면 더 큰 메모리로 옮기는 재할당(reallocation) 이 발생할 수 있습니다.
•
자주 쓰는 메서드
◦
push_back, pop_back, size, clear
◦
reserve(n): 용량을 미리 확보(재할당 줄이기)
◦
resize(n): 실제 크기를 변경(새 요소는 기본값으로 채움)
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v;
v.reserve(8); // push_back 많이 할 예정이면 미리 확보
for (int i = 1; i <= 6; ++i)
v.push_back(i * 10);
std::cout << "size=" << v.size() << "\n";
// 임의 접근
std::cout << "v[2]=" << v[2] << "\n";
// 중간 삽입(뒤 요소 이동 발생)
v.insert(v.begin() + 2, 999);
// 순회
for (int x : v)
std::cout << x << " ";
std::cout << "\n";
// 끝에서 삭제
v.pop_back();
// 주의: resize는 size를 바꾼다(요소가 늘 수 있음)
v.resize(10); // 부족한 칸은 0으로 채워짐(int)
return 0;
}
C++
복사
<list>
•
언제 쓰나
◦
중간 삽입/삭제가 많고, 그 위치(이터레이터)를 이미 알고 있는 경우
◦
요소 이동 없이 노드 연결만 바꾸고 싶을 때
•
특징
◦
이중 연결 리스트(doubly linked list)
◦
임의 접근 불가: list[i] 같은 접근이 없습니다.
◦
순회는 가능하지만 캐시 효율이 낮아 생각보다 느릴 수 있습니다.
•
자주 쓰는 메서드
◦
push_front, push_back, insert, erase, remove
#include <iostream>
#include <list>
int main()
{
std::list<int> lst = { 10, 20, 30, 40 };
// 30 앞에 25 삽입: "위치"를 이터레이터로 찾은 뒤 insert
auto it = lst.begin();
while (it != lst.end() && *it != 30)
++it;
if (it != lst.end())
lst.insert(it, 25);
// 값이 20인 노드 삭제(값 기준)
lst.remove(20);
// 특정 위치 삭제(이터레이터 기준)
auto it2 = lst.begin();
++it2; // 두 번째 원소
lst.erase(it2);
for (int x : lst)
std::cout << x << " ";
std::cout << "\n";
return 0;
}
C++
복사
<map>
•
언제 쓰나
◦
키를 기준으로 정렬된 상태가 필요할 때
◦
범위 검색(예: 50 이상 100 이하)을 자주 할 때
•
특징
◦
키-값(key-value) 쌍을 저장
◦
기본적으로 키 오름차순 정렬
◦
평균이 아니라 항상 O(log n) 수준의 탐색/삽입/삭제(트리 기반)
◦
키는 중복 불가
•
자주 쓰는 메서드
◦
insert, find, erase, lower_bound, upper_bound
◦
operator[]: 없으면 “새로 만들고” 기본값을 넣습니다(이게 자주 함정)
#include <iostream>
#include <map>
#include <string>
int main()
{
std::map<int, std::string> m;
m.insert({ 2, "two" });
m.insert({ 5, "five" });
m.insert({ 1, "one" });
// find
auto it = m.find(5);
if (it != m.end())
std::cout << "5 => " << it->second << "\n";
// operator[] 주의: 없는 키면 새 항목 생성
m[10] = "ten";
std::cout << "size=" << m.size() << "\n";
// 범위 검색: [2, 10) 범위 키 출력
auto b = m.lower_bound(2);
auto e = m.lower_bound(10);
for (auto i = b; i != e; ++i)
std::cout << i->first << " ";
std::cout << "\n";
return 0;
}
C++
복사
<set>
•
언제 쓰나
◦
값의 중복을 허용하지 않는 집합이 필요할 때
◦
자동 정렬 + 빠른 포함 여부 체크가 필요할 때
•
특징
◦
내부적으로 트리 기반
◦
O(log n) 수준의 삽입/삭제/탐색
◦
중복 삽입은 무시(삽입 결과로 성공 여부 확인 가능)
#include <iostream>
#include <set>
int main()
{
std::set<int> s;
auto r1 = s.insert(3);
auto r2 = s.insert(3);
std::cout << "first insert ok? " << r1.second << "\n"; // 1
std::cout << "second insert ok? " << r2.second << "\n"; // 0
if (s.find(3) != s.end())
std::cout << "3 is in set\n";
// 정렬되어 출력됨
for (int x : s)
std::cout << x << " ";
std::cout << "\n";
return 0;
}
C++
복사
<algorithm>
•
언제 쓰나
◦
컨테이너에 상관없이 반복자 구간을 대상으로 정렬/탐색/변환을 하고 싶을 때
•
특징
◦
대부분의 알고리즘은 [begin, end) 구간을 받습니다.
◦
std::sort는 random access iterator가 필요하므로 vector는 가능, list는 불가(대신 list.sort() 사용).
#include <algorithm>
#include <iostream>
#include <vector>
struct Point
{
int x, y;
};
int main()
{
std::vector<int> v = { 5, 1, 9, 3, 7 };
// 정렬
std::sort(v.begin(), v.end());
// 검색
auto it = std::find(v.begin(), v.end(), 7);
if (it != v.end())
std::cout << "found 7 at index " << (it - v.begin()) << "\n";
// 뒤집기
std::reverse(v.begin(), v.end());
for (int x : v)
std::cout << x << " ";
std::cout << "\n";
// 커스텀 정렬
std::vector<Point> p = { {3,4}, {1,9}, {2,2} };
std::sort(p.begin(), p.end(), [](const Point& a, const Point& b)
{
return a.y < b.y; // y 오름차순
});
return 0;
}
C++
복사
<queue>
•
언제 쓰나
◦
“먼저 들어온 게 먼저 처리”되는 처리 흐름(FIFO)이 필요할 때
◦
BFS(너비 우선 탐색), 작업 대기열 같은 패턴
•
특징
◦
std::queue는 기본적으로 std::deque를 내부 컨테이너로 사용합니다.
◦
앞/뒤로 넣고 빼는 동작만 노출합니다.
#include <iostream>
#include <queue>
int main()
{
std::queue<int> q;
for (int i = 1; i <= 4; ++i)
q.push(i);
while (!q.empty())
{
int x = q.front();
q.pop();
std::cout << "process " << x << "\n";
}
return 0;
}
C++
복사
<stack>
•
언제 쓰나
◦
“나중에 넣은 게 먼저 처리”되는 흐름(LIFO)이 필요할 때
◦
DFS(깊이 우선 탐색), 되돌리기(Undo) 같은 패턴
•
특징
◦
std::stack도 내부적으로 std::deque를 기본 사용
◦
위(top)에만 접근 가능
#include <iostream>
#include <stack>
int main()
{
std::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
while (!st.empty())
{
std::cout << st.top() << " ";
st.pop();
}
std::cout << "\n";
return 0;
}
C++
복사
<unordered_map>
•
언제 쓰나
◦
키로 빠르게 찾고 싶은데, 정렬은 필요 없을 때
◦
대량 데이터에서 평균적으로 빠른 조회가 필요할 때
•
특징
◦
해시 테이블 기반
◦
평균 O(1) (충돌이 심하면 최악 O(n))
◦
순서 보장 안 됨
◦
operator[]는 map과 동일하게 “없으면 생성”
#include <iostream>
#include <string>
#include <unordered_map>
int main()
{
std::unordered_map<std::string, int> score;
score["alice"] = 10;
score["bob"] = 20;
// find
auto it = score.find("bob");
if (it != score.end())
std::cout << "bob score=" << it->second << "\n";
// 카운트로 존재 여부 확인(0 또는 1)
if (score.count("charlie") == 0)
std::cout << "no charlie\n";
return 0;
}
C++
복사
<unordered_set>
•
언제 쓰나
◦
중복 없이 저장 + 빠른 포함 여부 체크가 필요할 때(정렬 불필요)
•
특징
◦
해시 기반 집합
◦
평균 O(1) 검색/삽입
◦
순서 보장 안 됨
#include <iostream>
#include <string>
#include <unordered_set>
int main()
{
std::unordered_set<std::string> visited;
visited.insert("Seoul");
visited.insert("Busan");
if (visited.find("Seoul") != visited.end())
std::cout << "visited Seoul\n";
visited.erase("Busan");
return 0;
}
C++
복사
<functional> / std::function
•
언제 쓰나
◦
“함수를 값처럼” 저장/전달하고 싶을 때
◦
콜백을 유연하게 받되, 함수 포인터/람다/멤버 함수 등을 한 타입으로 통일하고 싶을 때
•
특징
◦
std::function<R(Args...)> 형태로 “호출 가능한 것(callable)”을 포장
◦
약간의 런타임 오버헤드가 있을 수 있음(일반 함수 포인터보다 무거울 수 있음)
#include <functional>
#include <iostream>
#include <vector>
int add(int a, int b) { return a + b; }
int main()
{
// 1) 일반 함수
std::function<int(int, int)> f1 = add;
std::cout << f1(2, 3) << "\n";
// 2) 람다
std::function<int(int, int)> f2 = [](int a, int b)
{
return a * b;
};
std::cout << f2(4, 5) << "\n";
// 3) 콜백 패턴 예시: 조건을 외부에서 주입
std::vector<int> v = { 1,2,3,4,5,6,7,8,9,10 };
std::function<bool(int)> pred = [](int x) { return x % 2 == 0; };
for (int x : v)
if (pred(x))
std::cout << x << " ";
std::cout << "\n";
return 0;
}
C++
복사
<memory.h> (권장: <cstring>)
•
설명
◦
C 계열의 메모리 조작 함수들을 담은 헤더입니다.
◦
C++에서는 보통 동일 기능을 제공하는 <cstring>를 더 많이 사용합니다.
•
주요 함수
◦
memset: 특정 값으로 메모리 초기화
◦
memcpy: 메모리 복사(겹치면 위험)
◦
memmove: 겹치는 영역도 안전하게 복사
◦
memcmp: 메모리 비교
#include <cstring> // C++에서는 보통 <cstring>
#include <iostream>
int main()
{
char buf[16];
std::memset(buf, 0, sizeof(buf));
const char* msg = "Hello";
std::memcpy(buf, msg, std::strlen(msg));
std::cout << buf << "\n";
char data[] = "ABCDE";
// 겹치는 영역 복사 예시: memmove는 안전
std::memmove(data + 2, data, 3); // ABABC
std::cout << data << "\n";
return 0;
}
C++
복사
스마트 포인터 (<memory>) 요약
•
std::unique_ptr: 단독 소유. 복사 불가, 이동 가능. 가장 기본 추천.
•
std::shared_ptr: 공유 소유. 참조 카운팅. 순환 참조 주의.
•
std::weak_ptr: shared_ptr의 순환 참조를 끊기 위한 “소유하지 않는 참조”.
#include <iostream>
#include <memory>
struct Node
{
int value;
std::shared_ptr<Node> next;
std::weak_ptr<Node> prev; // 순환 참조 방지
};
int main()
{
auto a = std::make_shared<Node>();
auto b = std::make_shared<Node>();
a->value = 1;
b->value = 2;
a->next = b;
b->prev = a; // weak_ptr라서 카운트 증가 안 함
if (auto p = b->prev.lock())
std::cout << "prev value=" << p->value << "\n";
return 0;
}
C++
복사