# C언어 (13)

## 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`와 같은 원리로, 크기가 자동으로 늘어나는 배열이다.

```cpp
#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` 예외를 던져주므로 더 안전하다. `[]` 연산자는 범위 체크를 하지 않는다.

```cpp
cout << v.at(10) << endl;  // 범위 초과 시 예외 발생
cout << v[10] << endl;     // 범위 초과해도 예외 없음 — 위험
```

#### 데크 (deque)

`deque`(Double-Ended Queue)는 **양쪽 끝에서 삽입/삭제가 빠른 자료구조** 다. `vector`는 뒤에서만 빠르게 추가/삭제할 수 있지만, `deque`는 앞에서도 O(1)으로 가능하다.

```cpp
#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)** 다. 이전에 직접 구현했던 단일 연결 리스트와 달리, 각 노드가 앞 노드와 뒷 노드 모두를 가리킨다.

```cpp
#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`은 **중복 없는 값들의 집합** 이다. 값을 넣으면 자동으로 정렬되고, 같은 값을 두 번 넣으면 하나만 유지된다.

```cpp
#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`에 전부 넣으면 된다.

```cpp
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`은 키가 **자동 정렬** 된다는 차이가 있다.

```cpp
#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`은 연속된 메모리가 아니라 트리 구조이므로 포인터로 순회할 수 없다. 반복자는 **컨테이너의 내부 구조에 관계없이 동일한 방식으로 요소를 순회** 할 수 있게 해준다.

```cpp
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` 키워드를 쓰면 타입을 직접 쓰지 않아도 된다.

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

범위 기반 for문(`for (int x : v)`)은 사실 내부적으로 반복자를 사용하는 것이다. 대부분의 순회에서는 범위 기반 for문이 간편하지만, 요소를 삭제하거나 특정 위치를 조작해야 할 때는 반복자를 직접 사용해야 한다.

```cpp
// 반복자로 특정 요소 삭제
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()`를 가진다. 컨테이너가 바뀌어도 반복자를 쓰는 방식은 동일하다. 이것이 반복자의 핵심 가치다.

```cpp
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`로 값에 접근한다.

```cpp
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()`를 반환한다.

```cpp
#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)이기 때문이다.

```cpp
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`는 범위 안의 요소를 **정렬** 한다. 기본적으로 오름차순이며, 비교 함수를 넘겨서 정렬 기준을 바꿀 수 있다.

```cpp
#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`에 비교 함수를 넘겼던 것과 같은 원리다.

```cpp
// 절댓값 기준으로 정렬
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
```

람다 표현식을 사용하면 비교 함수를 인라인으로 작성할 수도 있다.

```cpp
// 구조체 벡터를 점수 기준으로 정렬
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()` 멤버함수를 사용해야 한다.

```cpp
list<int> lst = {50, 20, 40, 10, 30};
lst.sort();  // list 자체의 sort 멤버함수
```

* * *

## 마무리

STL은 C++ 프로그래밍의 생산성을 크게 높여주는 도구다. 직접 구현했던 동적 배열은 `vector`로, 연결 리스트는 `list`로, 해시맵은 `unordered_map`으로 대체할 수 있다. 반복자라는 추상화 덕분에 컨테이너가 바뀌어도 순회하는 코드는 동일하게 유지되고, `find`나 `sort` 같은 알고리즘도 컨테이너에 관계없이 적용할 수 있다. 자료구조의 원리를 이해한 상태에서 STL을 사용하면, 적재적소에 맞는 컨테이너를 선택하고 효율적인 코드를 작성할 수 있다.