1. STL

STL(Standard Template Library) 은

컨테이너 + 알고리즘 + 이터레이터를 표준으로 묶어, 재사용 가능한 범용 코드를 만드는 C++ 라이브러리 체계

이터레이터를 활용해 알고리즘이 컨테이너를 직접 모르고도 동작하게 만든다.

2. 컨테이너

데이터를 저장하는 자료구조

예를들어 std::vector, std::list, std::deque, std::map, std::set, std::unordered_map … 등이 존재한다.

3. 알고리즘

알고리즘: std::sort, std::find, std::lower_bound, std::accumulate … 등등

4. 이터레이터

STL 알고리즘이 컨테이너 종류와 상관없이 원소를 “가리키고 이동”할 수 있게 하는 포인터

std::vector<int> v = {10,20,30};

for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

//v.begin()은 첫 번째 원소를 가리키는 이터레이터를 반환하고, 
//v.end()는 마지막 원소의 “다음” 위치를 가리키는 이터레이터 (sentinel) 를 반환한다.

이터레이터는 list, map, set처럼 인덱스가 없는 컨테이너도 동일한 방식으로 순회하게 해준다.

5. Vector

동적 배열로, 크기를 자유롭게 변경할 수 있다.

(1) 선언과 초기화

#include <vector>    // bits/stdc++.h면 불필요

vector<int> v1;                    // 빈 벡터
vector<int> v2(5);                 // {0, 0, 0, 0, 0} (크기 5, 0으로 초기화)
vector<int> v3(5, 3);             // {3, 3, 3, 3, 3} (크기 5, 3으로 초기화)
vector<int> v4 = {1, 2, 3, 4, 5}; // 직접 초기화
vector<int> v5(v4);               // v4 복사

(2) 자주 사용하는 함수

vector<int> v = {1, 2, 3};

// 삽입
v.push_back(4);          // 뒤에 추가 → {1, 2, 3, 4}
v.emplace_back(5);       // push_back과 동일 (약간 더 빠름)

// 삭제
v.pop_back();            // 마지막 원소 제거 → {1, 2, 3, 4}

// 접근
v[0];                    // 1 (인덱스 접근, 범위 체크 X)
v.at(0);                 // 1 (범위 체크 O, 약간 느림)
v.front();               // 1 (첫 번째)
v.back();                // 4 (마지막)

// 크기
v.size();                // 4
v.empty();               // false

// 초기화/리셋
v.clear();               // 전부 삭제 → 크기 0
v.assign(5, 0);          // 크기 5, 전부 0으로 재설정
v.resize(10, -1);        // 크기 10으로, 새 자리는 -1로 채움

(3) 2차원 벡터

// 선언
int n = 3, m = 4;

// 방법 1: n×m 크기, 0으로 초기화
vector<vector<int>> grid(n, vector<int>(m, 0));

// 방법 2: 인접 리스트 (그래프에서 매번 씀!)
int V = 100001;
vector<vector<int>> adj(V);     // 빈 벡터 V개

adj[1].push_back(2);   // 1 → 2 간선
adj[1].push_back(3);   // 1 → 3 간선
adj[2].push_back(1);   // 2 → 1 간선

// 입력 받기
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> grid[i][j];
    }
}

(4) 벡터 순회

vector<int> v = {10, 20, 30, 40, 50};

// 방법 1: 인덱스 (가장 기본)
for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
}

// 방법 2: 범위 기반 for (깔끔)
for (int x : v) {
    cout << x << " ";
}

// 방법 3: 참조로 순회 (수정 필요할 때)
for (int &x : v) {
    x *= 2;    // 원본 수정
}

// 방법 4: auto (타입 길 때 편함)
for (auto &x : v) {
    cout << x << " ";
}

6. pair/tuple

(1) pair : 두 값을 묶기

#include <utility>    // bits/stdc++.h면 불필요

// 선언
pair<int, int> p1 = {3, 5};
pair<int, int> p2 = make_pair(3, 5);   // 동일
pair<string, int> p3 = {"Alice", 90};

// 접근
p1.first;     // 3
p1.second;    // 5

// 대입
p1 = {10, 20};

// first 먼저 비교 → 같으면 second로 비교 (사전식)
pair<int,int> a = {1, 5};
pair<int,int> b = {1, 3};
pair<int,int> c = {2, 1};

// a > b (first 같고, 5 > 3)
// c > a (first: 2 > 1)

// → sort하면: b(1,3), a(1,5), c(2,1)

// ① 좌표 저장
pair<int,int> pos = {3, 7};    // (행, 열)

// ② 가중치 그래프의 인접 리스트
vector<vector<pair<int,int>>> adj(N);
// adj[u] = {(v, w), ...}  → u에서 v로 가는 가중치 w
adj[1].push_back({2, 10});   // 1→2, 가중치 10

// ③ 정렬에서 기준 묶기
vector<pair<int,string>> students;
students.push_back({90, "Alice"});
students.push_back({85, "Bob"});
sort(students.begin(), students.end());
// → (85,"Bob"), (90,"Alice") — 점수 오름차순

(2) tuple : 세 값 이상 묶기

#include <tuple>

tuple<int, int, int> t = {1, 2, 3};

// 접근
get<0>(t);    // 1
get<1>(t);    // 2
get<2>(t);    // 3

// 구조화 바인딩 (C++17, 코테에서 사용 가능)
auto [x, y, z] = t;    // x=1, y=2, z=3

// pair에도 구조화 바인딩 사용 가능
pair<int,int> p = {3, 5};
auto [a, b] = p;    // a=3, b=5

7. Stack (LIFO: Last In, First Out)

#include <stack>

stack<int> st;

st.push(1);     // [1]
st.push(2);     // [1, 2]
st.push(3);     // [1, 2, 3]

st.top();       // 3 (맨 위 확인)
st.pop();       // [1, 2] (맨 위 제거, 반환값 없음!)
st.size();      // 2
st.empty();     // false

코테 사용처: 괄호 검사, 후위 표기식, 히스토리/되돌리기

8. Queue (FIFO: First In, First Out)

#include <queue>

queue<int> q;

q.push(1);      // [1]
q.push(2);      // [1, 2]
q.push(3);      // [1, 2, 3]

q.front();      // 1 (맨 앞 확인)
q.back();       // 3 (맨 뒤 확인)
q.pop();        // [2, 3] (맨 앞 제거)
q.size();       // 2
q.empty();      // false

코테 사용처: BFS (너비 우선 탐색) ← 엄청 자주!

9. Deque (Double-Ended Queue)

양쪽(front / back)에서 삽입과 삭제 모두 가능

#include <deque>

deque<int> dq;

// 양쪽 삽입/삭제 모두 O(1)
dq.push_back(1);      // [1]
dq.push_back(2);      // [1, 2]
dq.push_front(0);     // [0, 1, 2]

dq.front();           // 0
dq.back();            // 2

dq.pop_front();       // [1, 2]
dq.pop_back();        // [1]

// 인덱스 접근도 가능! (vector처럼)
dq.push_back(10);
dq.push_back(20);
dq[0];                // 1
dq[1];                // 10

코테 사용처: 슬라이딩 윈도우, 0-1 BFS, 양방향 처리

10. Priority Queue (Heap)

우선순위 큐 = 힙(Heap) — 항상 가장 큰(또는 작은) 원소가 top()에 위치

1. 최대힙 (Max Heap)

#include <queue>    // priority_queue도 여기 있음

priority_queue<int> pq;     // 기본 = 최대힙

pq.push(3);     // [3]
pq.push(1);     // [3, 1]
pq.push(5);     // [5, 3, 1]
pq.push(2);     // [5, 3, 2, 1]

pq.top();       // 5 (가장 큰 값)
pq.pop();       // [3, 2, 1]
pq.top();       // 3
pq.size();      // 3
pq.empty();     // false

2. 최소힙 (min heap)

// 방법 1: greater 사용 (공식)
priority_queue<int, vector<int>, greater<int>> minPQ;

minPQ.push(3);
minPQ.push(1);
minPQ.push(5);

minPQ.top();    // 1 (가장 작은 값!)

11. Set

set — 중복 없는 정렬된 집합

#include <set>

set<int> s;

// 삽입 O(log N)
s.insert(3);     // {3}
s.insert(1);     // {1, 3}
s.insert(5);     // {1, 3, 5}
s.insert(3);     // {1, 3, 5} — 중복 무시!

// 삭제 O(log N)
s.erase(3);      // {1, 5}

// 탐색 O(log N)
if (s.count(5)) {           // 있으면 1, 없으면 0
    cout << "있다!\n";
}
if (s.find(5) != s.end()) { // 동일한 방법
    cout << "있다!\n";
}

// 크기
s.size();        // 2
s.empty();       // false

// 순회 (자동 오름차순 정렬!)
for (int x : s) {
    cout << x << " ";    // 1 5
}

// 최솟값 / 최댓값
*s.begin();      // 1 (첫 번째 = 최솟값)
*s.rbegin();     // 5 (마지막 = 최댓값)

12. map

map 은 key : value 쌍 이다.

#include <map>

map<string, int> m;

// 삽입
m["Alice"] = 90; //key가 "Alice" 이고 value 가 "90"인 경우
m["Bob"] = 85;
m["Charlie"] = 95;
m.insert({"Dave", 88});

// 접근
m["Alice"];       // 90
// ⚠️ 없는 키로 접근하면 자동 생성됨! (값 0)
m["없는키"];      // 0이 들어가면서 키가 생성됨!

// 안전한 접근
if (m.count("Alice")) {      // 있는지 먼저 확인
    cout << m["Alice"] << "\n";
}

// 삭제
m.erase("Bob");

// 순회 (key 기준 오름차순 정렬)
for (auto &[key, val] : m) {           // 구조화 바인딩 (C++17)
    cout << key << ": " << val << "\n";
}
// Alice: 90, Charlie: 95, Dave: 88 (알파벳순)

// 크기
m.size();         // 3

13. unordered_set / unordered_map

unordered_set / unordered_map — 사용법은 set/map과 거의 동일하고 해시 기반이라 더욱 빠름

#include <unordered_set>
#include <unordered_map>

// 사용법은 set/map과 거의 동일!
unordered_set<int> us;
us.insert(3);
us.count(3);    // 1

unordered_map<string, int> um;
um["key"] = 100;

코테 규칙: 정렬이 필요하면 set/map, 그냥 있는지 없는지만 체크하면 unordered_set/unordered_map'

14. multiset

multiset — 중복 허용 정렬 집합

#include <set>

multiset<int> ms;
ms.insert(3);
ms.insert(1);
ms.insert(3);
ms.insert(5);
// {1, 3, 3, 5}

ms.count(3);          // 2 (3이 2개)

ms.erase(ms.find(3)); // 하나만 삭제 → {1, 3, 5}
ms.erase(3);           // 3을 전부 삭제 → {1, 5}

15. 컨테이너 선택 가이드

어떤 컨테이너를 쓸까?

동적 배열이 필요하다 ──────────────→ vector
두 값을 묶고 싶다 ────────────────→ pair
LIFO (후입선출) ───────────────────→ stack
FIFO (선입선출, BFS) ─────────────→ queue
양쪽 삽입/삭제 ────────────────────→ deque
항상 최대/최소를 꺼내야 한다 ──────→ priority_queue
중복 없이 정렬된 집합 ────────────→ set
중복 허용 정렬 집합 ──────────────→ multiset
key→value 매핑 (정렬) ────────────→ map
key→value 매핑 (빠른 탐색) ───────→ unordered_map
단순 존재 체크 ────────────────────→ unordered_set