STL

표준 c++ 라이브러리로 프로그램에 필요한 자료구조와 알고리즘을 Template로 제공하는 라이브러리이다. 주로 사용하는 것은 'pair, vector, queue, stack, set, priority queue' 6가지가 있다.

입출력

c++에서 개행을 하기 위해 endl을 그대로 사용하게 되면 출력 버퍼를 비우는 시간까지 꽤나 긴 시간을 소요하게 된다. 따라서 이러한 시간 낭비를 줄이기 위해서 3가지의 방법정도 존재한다.
1) C에서 사용한 scanf(), printf() 사용
2) endl대신 \n 사용

#include <cstdio> // <stdio.h>도 사용 가능

int main(void)
{
	int n;
	scanf("%d", &n); // cin
	printf("%d\n", n); // cout
}

3) ios_base::sync_with_stdio(false), cin.tie(NULL) 사용

#include <iostream>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false); // 표준 입출력 스트림을 동기화 X
	cin.tie(nullptr); // cin 사용시 출력 버퍼를 비우지(flush) 않음

	...
}

Pair

사용자가 지정한 2개의 타입의 자료형을 하나의 쌍으로 묶을 수 있게 해준다. 기본적으로 <utility> 헤더에서 제공되는 것이나, <vector>나 <algorithm> 헤더 파일에 포함되어 있어 이를 많이 사용한다.

첫 번째 데이터는 first, 두 번째 데이터는 second로 접근할 수 있다.
p = make_pair(f,s)로 한 번에 데이터를 대입하는 것도 가능하다.

📌 코드

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(int argc, const char * argv[]) {
  pair<int, char> p; // int, char 자료형 2개를 묶음.
  
  scanf("%d %c", &p.first, &p.second);
  printf("%d %c\n", p.first, p.second);
  
  p.first = 1;
  p.second = 'a';
  printf("%d %c\n", p.first, p.second);
  
  p=make_pair(3, 'b'); // 한 번에 대입
  printf("%d %c\n", p.first, p.second);
  
}

📌 출력

7 c
7 c
1 a
3 b

Vector

크기가 가변적인 배열로, 동적으로 할당되어 크기를 자유자재로 변경할 수 있어 사용에 용이하다. <vector> 헤더파일을 추가하여 사용하면 된다.

front() : 벡터의 첫 번째 원소를 반환
back() : 벡터의 마지막 원소를 반환
begin() : 벡터의 첫 번째 원소를 가리킴
end() : 벡터의 마지막 원소를 가리킴
push_back(): 마지막에 데이터 추가
pop_back() : 마지막 데이터 빼기
size() : 벡터의 원소의 개수
clear() : 배열 비우기

📌 코드

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(int argc, const char * argv[]) {
    vector<int> v1 = {1, 2, 3};
    vector<pair<int, char>> v2;
    int a, b;
    char c, d;
    
    v1.push_back(4);
    v1.push_back(5);
    for (int i=0; i < v1.size(); i++) {
        printf("%d ", v1[i]);
        
    }
    
    printf("\n"); // 개행
    
    a = v1.front();
    b = v1.back();
    printf("front: %d, back: %d\n", a, b); // 벡터의 첫 번째 원소와 마지막 원소
    
    v1.pop_back();
    for (int i=0; i < v1.size(); i++) {
        printf("%d ", v1[i]);
        
    }
    
    printf("\n");
    
    // pair인 vector
    v2.push_back(make_pair(1, 'a'));
    v2.push_back(make_pair(2, 'b'));
    v2.push_back(make_pair(3, 'c'));
    for (int i=0; i < v2.size(); i++) {
        printf("<%d %c> ", v2[i].first, v2[i].second);
        
    }
    
    printf("\n");
    
    // 벡터의 첫 번째 원소와 마지막 원소의 pair 값 출력
    a = v2.front().first;
    c = v2.front().second;
    b = v2.back().first;
    d = v2.back().second;
    printf("front: <%d %c>\n", a, c);
    printf("back: <%d %c>\n", b, d);
    
    v2.clear();
    
}

📌 출력

1 2 3 4 5
front: 1, back: 5
1 2 3 4
<1 a> <2 b> <3 c>
front: <1 a>
back: <3 c>

Queue

데이터를 일시적으로 쌓아두기 위한 자료구조로, 스택과는 다르게 FIFO(First In First Out)형태를 가진다. <queue> 헤더를 추가하여 사용할 수 있고, BFS(Breadth First Search)에 유용하다.

push(): 큐 마지막에 데이터 추가
pop(): 큐의 첫 번째 데이터 뽑기
front(): 큐의 첫 번째 원소
back(): 큐의 마지막 원소
size(): 큐의 크기
empty(): 큐가 비어있는지 확인

📌 코드

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int main(int argc, const char * argv[]) {
    queue<int> q1;
    int n;
    
    q1.push(1);
    q1.push(2);
    q1.push(3);
    q1.push(4);
    q1.push(5);
    a = q1.front();
    b = q1.back();
    n = q1.size();
    
    for(int i=0; i<n; i++){
        printf("%d ", q1.front());
        q1.pop(); // 맨 처음에 들어온 원소부터 빠짐        
    }
    
    printf("\n");
    
    printf("front: %d, back: %d\n", a, b);
}

📌 출력

1 2 3 4 5
front: 1, back: 5

Stack

데이터를 일시적으로 쌓아두기 위한 자료구조로, LIFO(Last In First Out)형태를 가지고 있다. <stack> 헤더를 추가하여 사용할 수 있다.

push(): 스택의 top에서 데이터 추가
pop(): 스택의 top에서 데이터 뽑기
top(): 스택의 top에 있는 원소
size(): 스택의 크기
empty(): 스택이 비어있는지 확인

📌 코드

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;

int main(int argc, const char * argv[]) {
    stack<int> s1;
    int a;
    int n;
    
    s1.push(1); s1.push(2); s1.push(3);
    s1.push(4); s1.push(5);
    
    a = s1.top();
    n = s1.size();
    
    for(int i=0; i<n; i++){
        printf("%d ", s1.top()); s1.pop();
        
    }
    
    printf("\n");
    
    printf("top: %d\n", a); // top에 있는 원소 출력
    
}

📌 출력

5 4 3 2 1
top: 5

Set

연관 컨테이너(associative container) 중 하나로 노드 기반 컨테이너이자 균형 이진트리로 구현되어 있다. Key라 불리는 원소들의 집합으로 이루어진 컨테이너로 Key값은 중복이 허용되지 않으며, insert()를 통해 삽입할 수 있고 자동으로 오름차순(less) 정렬된다. <set> 헤더를 추가하여 사용한다.

연관 컨테이너의 공통적인 특징 : 노드 기반 컨테이너, 균형 이진트리, 멤버 변수, 생성자 등등

insert(k): Set에 원소 k 삽입
begin(): Set의 첫 번째 원소를 가리키는 iterator 반환
end(): Set의 마지막 원소를 가리키는 iterator 반환
find(k): Set에서 원소 k를 가리키는 iterator 반환
size(): Set의 크기
empty(): Set이 비어있는지 확인

📌 코드

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;

int main(int argc, const char * argv[]) {
    set<int> s1;
    s1.insert(1); s1.insert(2); s1.insert(6);
    s1.insert(5); s1.insert(4); s1.insert(3);
    
    set<int>::iterator it; // set에서 사용할 iterator
    
    for (it = s1.begin(); it != s1.end(); it++) {
        printf("%d ", *it);
        
    }
    
    printf("\n");
    
    it = s1.find(9);
    printf("%d\n", *it);
    
    it = s1.find(4);
    printf("%d\n", *it);
    
}

📌 출력

1 2 3 4 5 6
0 
4

Map

연관 컨테이너(associative container) 중 하나로 <key, value>의 쌍으로 저장한다. Set과 마찬가지로 key의 중복이 허용되지 않으며, insert()를 통해 삽입할 수 있고 자동으로 오름차순 정렬된다. map은 [] 연산자가 제공되어 key에 해당하는 원소의 value에 바로 접근이 가능하다.

insert(make_pair(k,v)): Map에 원소를 <key, value>의 pair로 삽입
erase(k): Map의 key값 'k'를 갖는 원소를 삭제
begin(): Map의 첫 번째 원소를 가리키는 iterator 반환
end(): Map의 마지막 원소를 가리키는 iterator 반환
find(k): Map의 key값 'k'를 갖는 원소를 가리키는 iterator 반환
size(): Map의 크기
empty(): Map이 비어있는지 확인

📌 코드

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

int main(int argc, const char * argv[]) {
    map<char, int> m1;
    m1.insert(make_pair('a', 1)); m1.insert(make_pair('e', 5));
    m1.insert(make_pair('c', 3)); m1.insert(make_pair('d', 4));
    m1.insert(make_pair('b', 2));
    
    m1['e'] = 6; // <e, 5>에서 <e, 6>로 변경
    m1['f'] = 7; // <f, 7> 삽입
    
    map<char, int>::iterator it; // Map에 사용할 iterator
    for (it = m1.begin(); it != m1.end(); it++) {
        printf("<%c %d> ", (*it).first, (*it).second);
        
    }
    
    printf("\n");
    
    it = m1.find('a');
    printf("%d\n", (*it).second);
    
    it = m1.find('d');
    printf("%d\n", (*it).second);
    
    // 삭제
    m1.erase('b');
    m1.erase('e');
    
    // 삭제 후 출력
    for (it = m1.begin(); it != m1.end(); it++) {
        printf("<%c %d> ", (*it).first, (*it).second);
        
    }
    
    printf("\n");
    
}

📌 출력

<a 1> <b 2> <c 3> <d 4> <e 6> <f 7>
1
4
<a 1> <c 3> <d 4> <f 7>

Priority queue

Container의 한 종류로 일반적인 Queue와 조금 다르게 모든 원소중에서 가장 큰 값에 우선순위를 부여하여 Top을 유지하고 먼저 pop되는 queue이다. 또한 Priorty queue는 내부적으로 Heap이라는 자료구조를 사용하고 있다. <queue> 헤더를 추가하여 사용할 수 있다.

queue에서 사용하는 함수와 똑같음.
push(): 우선순위 큐의 top에 데이터 추가
pop(): 우선순위 큐의 top에서 데이터 뽑기
top(): 우선순위 큐의 top에 있는 원소
size(): 우선순위 큐의 크기
empty(): 우선순위 큐가 비어있는지 확인

📌 코드

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int main(int argc, const char * argv[]) {
    priority_queue< int, vector<int>, less<int> > q;
    int n;
    
    q.push(3); q.push(2);
    q.push(5); q.push(4);
    q.push(1); q.push(6);
    
    printf("top: %d\n", q.top());
    n = q.size();
    
    for(int i=0; i<n; i++){
        printf("%d ", q.top());
        q.pop();
        
    }
    
    printf("\n");
    
}

📌 출력

top: 6
6 5 4 3 2 1