STL 정리

STL은 C++에 내장된 템플릿 기반의 라이브러리이다.
크게 컨테이너, 반복자(Iterator), 그리고 알고리즘으로 구성되어있다.

📍컨테이너: 데이터를 저장, 관리하는 구조체들의 집합 ➡️ 마을에 속한 창고

📍반복자: 컨테이너 내 데이터들을 순회할 수있도록 도와주는 일종의 포인터 ➡️ 창고 정리를 도와주는 NPC

📍알고리즘: 정렬, 탐색, 삽입, 삭제 등과 같은 로직을 매우 효율적으로 제공 ➡️ 일 참 잘하는 용병

 

 

📌 컨테이너

컨테이너는 데이터를 안전하고 편리하게 담아두는 창고이다.
다양한 컨테이너들이 있고, 각 컨테이너마다 삽입, 삭제, 접근 방식이 조금씩 다르다. 

✅ vector

• 크기가 동적으로 조정되는 배열 컨테이너
• 연속된 메모리 블록을 사용하여서 O(1)로 임의 접근이 빠르다. 
• 삽입/삭제는 O(1)로 끝에서 빠르며, 중간 삽입/삭제는 O(N)으로 비용이 크다 ➡️ 데이터 이동이 발생하기 때문

📍주요 함수

• push_back(value): 맨 뒤에 원소 추가
• pop_back(): 맨 뒤의 원소 제거
• size(): 원소 개수 반환
• capacity(): 현재 할당된 메모리 크기
  • 용량이 증가할 수록 재할당과 복사가 발생해서 reserve()로 미리 공간 확보가 가능
• at(index): 지정된 인덱스의 원소 반환(범위 초과 시 예외 발생)
• front(): 첫 번째 원소 반환
• back(): 마지막 원소 반환
• clear(): 모든 원소 제거
• insert(iterator, value): 지정된 위치에 원소 삽입
• erase(iterator): 지정된 위치의 원소 제거
• data(): 내부 배열 포인터 반환

 

✅ list

• 노드 기반의 이중 연결 리스트 ➡️ 앞/뒤로 자유롭게 탐색 가능하고 삭제가 효율적
• 순차적 데이터 추가/삭제에 적합
• 중간 삽입/삭제가 O(1)로 빨라 효율적
• 연속된 메모리 블럭을 사용하지 않아 크기 조절 비용이 없음
• 임의 접근이 불가능

📍주요 함수

• push_back(value): 맨 뒤에 원소 추가
• push_front(value): 맨 앞에 원소 추가
• pop_back(): 맨 뒤 원소 제거
• pop_front(): 맨 앞 원소 제거
• insert(iterator, value): 지정된 위치에 원소 삽입
• erase(iterator): 지정된 위치의 원소 제거

 

✅ deque

• vector와 마찬가지로 중간 삽입/삭제 시 비효율적이지만 양방향으로의 삽입/삭제가 빠른 동적 배열
• 랜덤 접근 속도가 vector보다 느림
• 연속된 메모리를 사용하지 않음

📍주요 함수

• push_back(value): 맨 뒤에 원소 추가
• push_front(value): 맨 앞에 원소 추가
• pop_back(): 맨 뒤의 원소 제거
• pop_front(): 맨 앞의 원소 제거
• at(index): 지정된 인덱스의 원소 반환(범위 초과 시 예외 발생)
• front(): 첫 번째 원소 반환
• back(): 마지막 원소 반환
• clear(): 모든 원소 제거
• insert(iterator, value): 지정된 위치에 원소 삽입
• erase(iterator): 지정된 위치의 원소 제거

 

✅ map

• Red - Black Tree 기반의 정렬된 Key - Value 쌍으로 저장하는 연관 컨테이너
• O(log N) 시간 복잡도로 탐색, 삽입, 삭제가 빠름
• Key 중복 허용하지 않음 ➡️ 동일한 Key에 많은 Value를 저장해야 한다면 multimap 사용

📍주요 함수

• insert(pair): 키와 값 쌍으로 삽입
• erase(key): 키로 요소 제거
• find(key): 키로 요소 검색 / 있으면 key의 iterator 반환, 없으면 end() 반환
• operator[key]: 키로 값에 접근 또는 삽입
• size(): 요소 개수 반환

 

✅ set

• Red - Black Tree 기반의 정렬된 Key 값만을 저장하는 컨테이너
• O(long N) 시간 복잡도로 탐색, 삽입, 삭제가 빠름
• 중복 혀용하지 않음 ➡️동일한 Key를 허용하는 multiset이 존재하지만, vector와 다를게 없다.

📍주요 함수

• insert(value): 요소 추가
• erase(value): 요소 제거
• find(value): 요소 검색 / 있으면 iterator 반환, 없으면 end() 반환
• lower_bound(value): value 값 이상의 첫 번째 요소 반환
• upper_bound(value): value 값 초과하는 첫 번째 요소 반환

 

🔎Red - Black Tree란?

항상 균형을 유지하도록 설계된 균형 이진 탐색 트리이다.
이 균형 유지 덕분에 탐색, 삽입, 삭제 연산이 O(log N) 시간 복잡도로 수행되며 자동 정렬이 보장된다.

📍Red - Black Tree의 규칙

1. 각 노드는 Red 혹은 Black 중 하나의 색을 가진다.
2. 루트 노드는 항상 Black이다.
3. 모든 리프 노드(null)은 Black이다.
4. Red 노드의 자식은 반드시 Black이어야 한다. 즉 Red노드가 연속해서 등장할 수 없음.
5. 어떤 노드에서 리프 노드까지 가튼 모든 경로에는 같은 개수의 Black 노드가 있어야한다.
6. 위와 같은 규칙을 유지하도록 삽입, 삭제 시 재조정 연산을 수행하며 이 또한 비용 발생.

📍재조정 과정

 

 

 

---

 

 

📌 algorithm 헤더의 함수 정리

✅ binary_search (이진 탐색)

• 배열이나 컨테이너에서 특정 값이 존재하는지 탐색
• 반드시 정렬된 배열에서 사용해야함
• 원소가 있는지 여부를 반환 (true / false)
  • 이진 탐색을 더욱 세밀하게 하려면 lower_bound와 upper_bound를 활용
  • lower_bound(vector.begin(), vector.end(), 3): 3 이상의 위치 Iterator 반환 / 첫 번째 3의 위치
  • upper_bound(vector.begin(), vector.end(), 3): 3 초과의 위치 Iterator 반환 / 3이 끝난 다음 위치

vector<int> v = {1, 3, 3, 3, 7, 9};
    
// 정렬된 상태에서 이진 탐색 수행
bool find = binary_search(v.begin(), v.end(), 3); // true
    
// lower_bound: 3 이상(≥ 3)인 첫 번째 위치 찾기
auto lower = lower_bound(v.begin(), v.end(), 3); // 1번 위치

// upper_bound: 3보다 큰(> 3) 값이 처음 나오는 위치 찾기
auto upper = upper_bound(v.begin(), v.end(), 3); // 4번 위치

// 특정 값(3)의 개수 찾기
int count = upper - lower; // 3개

 

✅ priority_queue (우선 순위 큐)

• 내부적으로 힙(Heap) 자료구조를 사용하고 기본적으로 Max Heap 사용(최대 값이 top에 위치)
• priority_queue<int, vector<int>, greater<int>> minPq 이렇게 세 번째 인자에 greater<int>를 넣음으로 Min Heap 사용 가능하고, 람다 함수나 compare함수 커스텀 정의하여 활용할 수 있다.
• 삽입/삭제는 항상 O(log N)이고, 우선순위가 가장 높은 원소 top()의 조회는 O(1)이다.
• 가장 큰/작은 원소를 빠르게 추출해야하는 문제에 최적

// Max-Heap 선언
// 기본적으로 Max-Heap으로 동작한다.
// 우선순위 큐는 내부적으로 백터를 이용해서 생략을 해도 되지만, 
// 세 번째 인자를 넣기 위해선 명시적으로 써주어야한다.
priority_queue<int> == priority_queue<int, vector<int>, less<int>> MaxHeap;

// Min-Heap 선언
priority_queue<int, vector<int>, greater<int>> MinHeap;

// 커스텀 우선 순위
struct Node
{
	int Num;
    char Name;
    bool operator<(const Node& Other) const
    {
    	if(Num < Other.Num) return 1;
        if(Num > Other.Num) return 0;
        
        return Name < Other.Name;
}

priority_queue<Node> CustomPQ;

 

✅ next_permutation / prev_permutation (순열 생성)

• next_permutation: 주어진 범위를 사전순 다음 순열로 바꿈
• prev_permutation: 주어진 범위를 사전순 이전 순열로 바꿈
• 다음 순열이 존재하지 않으면 false 반환
• 원본 데이터는 꼭 정렬 상태여야만 함

    vector<int> v = { 1,2,3 };
    do {
        for (int x : v) cout << x << " ";
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));
    /*
     결과
     1 2 3
     1 3 2
     2 1 3
     2 3 1
     3 1 2
     3 2 1
    */

    vector<int> v = { 3,2,1 };
    do {
        for (int x : v) cout << x << " ";
        cout << endl;
    } while (prev_permutation(v.begin(), v.end()));
    /*
     결과
     3 2 1
     3 1 2
     2 3 1
     2 1 3
     1 3 2
     1 2 3
    */

 

✅ unique + erase (중복 제거_ 정렬 필요)

• 연속된 중복을 제거
• 정렬 후 사용해야 완전한 중복 제거 가능

vector<int> v = {1, 4, 4, 2, 2, 2, 5, 1};
sort(v.begin(), v.end()); // sort 결과 -> {1, 1, 2, 2, 2, 4, 4, 5}

auto newEnd = unique(v.begin(), v.end()); // unique 결과 -> {1, 2, 4, 5, ?, ?, ?, ?}
v.erase(newEnd, v.end()); // ?구간 삭제

 

✅ min_element / max_element / minmax_element

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

// 1. max_element: 최댓값의 위치 iterator 반환
auto max_it = max_element(v.begin(), v.end());
cout << "최댓값: " << *max_it << endl; // 8 출력
    
// 2. min_element: 최솟값의 위치 iterator 반환
auto min_it = min_element(v.begin(), v.end());
cout << "최솟값: " << *min_it << endl; // 1 출력
    
// 3. minmax_element: 최솟값과 최댓값을 한 번에! (구조적 바인딩 활용했어요)
auto [min_iter, max_iter] = minmax_element(v.begin(), v.end());
// c++14 이하 버전에서는 pair로 직접 받아야함
pair<vector<int>::iterator , vector<int>::iterator> minmax = minmax_element(v.begin(), v.end());
cout << "최댓값2: " << *max_iter << endl; // 8 출력
cout << "최소값2: " << *min_iter << endl; // 1 출력

 

✅ count / count_if

• 컨테이너에서 특정 조건을 만족하는 원소 개수 반환

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

int count = count(v.begin(), v.end(), 2); // 2의 개수 3반환
int even_count = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }); // 짝수의 개수 4반환

 

---

 

 

📌 numeric 헤더의 함수 정리

✅ accumulate (누적 총합)

• 주어진 번위의 전체 합을 계산하는 함수
• 단순 덧셈 뿐만 아니라 다른 연산도 적용 가능
• 최종 합계의 값을 반환

 std::vector<int> v = {1, 2, 3, 4, 5};
 int sum = accumulate(v.begin(), v.end(), 0); // 1+2+3+4+5 = 15

 

✅ partial_sum (연속 구간 부분 합 계산)

• 각 요소까지의 누적 합을 배열로 반환하는 함수
• 3번째 인자로 새로운 컨테이너 시작 iterator를 전달하면 각 인덱스마다 부분합이 계산된다.

vector<int> v = {1, 2, 3, 4, 5};
vector<int> result(v.size());
partial_sum(v.begin(), v.end(), result.begin());
for (int n : result) cout << n << " "; // 1 3 6 10 15