[코드 중심 C++] - STL(Standard Template Library)

STL

Standard Template Library의 약어.
C++에서 자체적으로 제공하는 자료구조 라이브러리이다.
C++의 1/3이 문법이고, C++ 1/3이 탬플릿이고, 그 나머지가 STL일 것이라고... 누가 말했었는데 기억이 안난다.

STL Container Adater

스택, 큐, 우선순위 큐 등의 기본적인 자료구조를 탬플릿형태로 제공한다.

Stack

stack 클래스의 멤버함수로 push, pop, top(조회), empty, size가 주어진다.

#include <iostream>
#include <stack> // 이렇게 include해준다.

using namespace std;

int main(void){
    stack<int> s; // stack이 template로 구현되어있다. int형 데이터를 담는 stack이라 선언
    s.push(7); s.push(5); s.push(4); s.pop(); s.push(6); s.pop();

    while (!s.empty()){ // stack 원소가 하나라도 남아있는 경우
        cout << s.top() << ' ';
        s.pop();
    }

    return 0;
}

// output:
5 7

Queue

Queue 클래스의 멤버함수로 push, pop, front, back, empty, size가 주어진다.

#include <iostream>
#include <queue>

using namespace std;

int main(void){
    queue<int> q;
    q.push(7); q.push(5); q.push(4); q.pop(); q.push(6); q.pop();

    while (!q.empty()){ // stack 원소가 하나라도 남아있는 경우
        cout << q.front() << ' ';
        q.pop();
    }

    return 0;
}

// output:
4 6

Priority Queue

Priority Queue 클래스의 멤버함수로 push, pop, top, empty, size이 주어진다.
Queue와 똑같이 queue헤더를 사용한다.

push를 할 때마다 자동으로 정렬한다.

#include <iostream>
#include <queue>

using namespace std;

int main(void){
    int n, x;
    cin >> n;

    priority_queue<int> pq; // 선언. 최대식 구조를 이용한 우선순위 큐

    for(int i = 0; i < n; i++){ cin >> x; pq.push(x); }
    while(!pq.empty()){
        cout << pq.top() << ' ';
        pq.pop();
    }

    return 0;
}

// output:
4
5
6
7
1
7 6 5 1

STL Container

클래스 템플릿으로 구현되어있다.
container는 sequence container, associative container가 있다.

• Sequence Container : array (C++ 11), vector, list, deque
• associative Container : set, multiset, map, multimap

STL Sequence Container

vector, deque가 가장 많이 사용된다.

접근하는데 사용하는 멤버변수로 iterator가 제공된다.

deque

deque 은 양 끝에서 데이터를 넣거나 뺄 수 있다.

push_front, pop_front, push_back, pop_back, insert 등의 멤버함수가 제공된다.

#include<iostream>
#include<deque>


using namespace std;

int main(){
    deque<int> d;

    d.push_front(3); d.push_back(7); d.pop_front(); d.push_front(4);
    // 4 7
    for(int i = 0; i < d.size(); i++){ cout << d[i] << ' ';}
    cout << '\n';

    deque<int>::iterator iter; // 각 원소에 접근하게 해주는 iterator
    iter = d.begin(); // 시작 부분에 위치한다.
    // deque.insert(position, numbers, data)
    d.insert(iter + 1, 3, 5); // 5를 3번 입력해서 4 5 5 5 7
    iter = d.begin();
    d.insert(iter + 1, 1, 9); // 9를 1번 입력해서 4 9 5 5 5 7

    for(int i = 0; i < d.size(); i++){ cout << d[i] << ' '; }
    cout << '\n';
    d.clear(); // 덱의 모든 원소 제거
    cout << d.empty() << '\n'; // 비어있으면 empty함수가 1을 반환

    return 0;
}

// output:
4 7
4 9 5 5 5 7
1

vector

vector는 뒤쪽에서만 push pop이 가능하다. 배열처럼 사용 가능

멤버함수로 push_back, pop_back, insert를 지원한다.

#include<iostream>
#include<vector>

using namespace std;

int main(){
    vector<int> v;
    v.push_back(3); v.push_back(5); v.push_back(8); // 3 5 8

    vector<int>::iterator iter;
    iter = v.begin();
    v.insert(iter + 1, 3, 7); // 3 7 7 7 5 8
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ' ';
    }
    cout << '\n';

    v.clear();
    cout << v.empty(); // 비어있으면 1 반환

    return 0;
}

// output:
3 7 7 7 5 8
1

STL Associate Container

key와 value로 데이터를 쌍으로 저장하는 컨테이너이다.
set, map이 핵심이다.
python의 set과 dictionary와 비슷하다

set

set은 data를 key로 사용한다. 정렬된 위치에 데이터를 삽입하여 검색 속도가 빠르다.
키의 중복은 허용되지 않는다.

#include<iostream>
#include<set>

using namespace std;

int main(){
    int array[5] = {2, 4, 6, 8, 10};
    set<int> s(array, array + 5); // array를 set으로 바꿀 때에는 s(배열시작주소, 배열끝주소)
    // set<int> s{2,4,6,8,10}; 도 가능
    set<int>::iterator iter = s.begin();

    for(; iter != s.end(); iter++){ //2 4 6 8 10
        cout << *iter << ' '; // iterator는 pointer의 속성을 가지는 객체이다.
    }
    cout << '\n';

    s.insert(1);
    s.insert(3);
    s.insert(5);
    s.insert(5);
    iter = s.begin();
    for(; iter != s.end(); iter++){ //1 2 3 4 5 6 8 10
        cout << *iter << ' ';
    }
    cout << '\n';

    return 0;
}

// output:
2 4 6 8 10
1 2 3 4 5 6 8 10

5가 중복되지 않는 것을 볼 수 있다. 정말 python의 set과 비슷하다.

map

map은 저장하는 key를 value와 한 쌍으로 사용한다.
정렬된 위치에 데이터를 삽입하여 검색 속도가 빠르다.
key는 중복되지 않는다.

hash 자료구조를 대신하는데 많이 쓰인다.

#include<iostream>
#include<string>
#include<map>

using namespace std;

int main(){
    map<string, int> m; // string이 key, int가 value
    m["홍길동"] = 1; m["alex"] = 2; m["bob"] = 3; //m[key] = value;
    map<string, int>::iterator iter = m.begin();

    for(; iter !=m.end(); iter++){
        cout << iter->first << ':' << iter->second << '\n';
    }
    m["hmm"] = 4; // 새로운 key, value를 추가한다.
    cout << m["nobody"] << '\n'; // nobody도 접근을 시도했기에, 0의 value로 새로 생긴다.

    cout << '\n';

    iter = m.begin();
    for(; iter != m.end(); iter++){
        cout << iter->first << ':' << iter->second << '\n';
    }

    return 0;
}

// output:
alex:2
bob:3
홍길동:1
0

alex:2
bob:3
hmm:4
nobody:0
홍길동:1

0만 나오는 출력이 cout << m["nobody"] << '\n';에 의한 것이다.

---

참고

STL의 개념

https://blockdmask.tistory.com/67

https://en.cppreference.com/w/cpp/container

iterator(반복자)에 관한 내용

htps://eehoeskrap.tistory.com/263