C++ Standard Template Library(STL)

c++ STL은 algorithms, containers, functions, iterators를 제공한다.

자료구조를 직접 만들지 않아도 STL을 사용하면 list, stack, queue, deque, priority_queue, set, map등을 사용할 수 있는 것이다. 

1. 구성

1.1. Containers

sequence containers는 iterator를 사용할 수 있고 search가 가능하지만, container adaptors는 iterator를 사용할 수 없고 search가 불가능하다.

구분	Container	Description
Sequence Containers	vector	C의 배열같은 것이다. 배열의 끝에서 삽입 및 삭제는 O(1)의 시간복잡도를 가지지만, 배열의 앞에 삽입 및 삭제는 O(n)의 시간복잡도를 가진다.
	list	doubly linked list(이중연결리스트). 요소들은 메모리에 연속적으로 저장되지 않는다. 삽입 및 삭제는 O(1)의 시간복잡도를 가진다.
	deque	시작과 끝에서 삽입 및 삭제가 O(1)의 시간복잡도를 가지는 vector 이다.
Container Adaptors	queue	push/pop/front/back 명령이 가능한 FIFO queue를 제공한다.
	priority_queue	push/pop/top 명령이 가능한 최대 우선순위큐를 제공한다. heap를 이용해 구현되었다. 삽입과 삭제는 O(log n)의 시간복잡도를 가진다.
	stack	push/pop/top 명령이 가능한 LIFO stack을 제공한다.
Associative Containers	set	수학적 집합이다. 삽입 및 삭제는 O(log n)의 시간복잡도를 가진다.
	map	key-value쌍을 저장하는 컨테이너. 삽입 및 삭제는 O(log n)의 시간복잡도를 가진다.

1.2.  Iterators

iterator는 sequence containers에서 값들에 접글할 때 사용된다.

2. 상세

sequence containers에서는 list, deque중에서 선택하여 사용하면 된다. vector는 deque의 하위호환이다.

2.1. std::vector

아래를 클릭해서 펼치기↓

요소 접근 함수

v.at(숫자)	경계 체크와 함께 지정된 요소 접근
v[숫자]	경계 체크 없이 지정된 요소 접근
v.front()	처음 요소 접근
v.back()	마지막 요소 접근

iterators 함수

v.begin()	처음의 iterator 반환
v.end()	마지막의 iterator 반환

용량 함수

v.empty()	컨테이너가 비어있는지 아닌지
v.size()	요소들의 개수 반환

바꾸는 함수

v.clear()	콘텐츠를 클리어함
v.insert(const_iterator pos, const T& value)	요소 삽입
v.erase(iterator pos)	요소 제거
v.push_back(const T& value)	요소를 맨 뒤에 삽입
v.pop_back()	요소를 맨 뒤에서 제거

예제

#include <iostream>
#include <vector>
using namespace std;
int main(void){
    vector<int> v = {1,2,3,4,5};
    vector<int>::iterator it;
    for(it=v.begin(); it!=v.end(); it++)
        cout << &*it << " " << *it << endl;
    cout << endl;
    v.erase(v.begin());
    for(it=v.begin(); it!=v.end(); it++)
        cout << &*it << " " << *it << endl;
    cout << endl;
    v.insert(v.end(), 6);
    v.insert(v.end(), 7);
    for(it=v.begin(); it!=v.end(); it++)
        cout << &*it << " " << *it << endl;
    return 0;
}

 결과

첫번째 요소를 삭제했을 때, 다음요소들이 모두 저장되어있는 주소를 하나씩 앞으로 옮기는 과정이 보인다. 

 

참고: https://en.cppreference.com/w/cpp/container/vector

2.2. std::list

아래를 클릭해서 펼치기↓

요소 접근 함수

l.front()	처음 요소 접근
l.back()	마지막 요소 접근

iterators 함수

l.begin()	처음의 iterator 반환
l.end()	마지막의 iterator 반환

용량 함수

l.empty()	컨테이너가 비어있는지 아닌지
l.size()	요소들의 개수 반환

바꾸는 함수

l.clear()	콘텐츠를 클리어함
l.insert(const_iterator pos, const T& value)	요소 삽입
l.erase(iterator pos)	요소 제거
l.push_back(const T& value)	요소를 맨 뒤에 삽입
l.pop_back()	요소를 맨 뒤에서 제거
l.push_front(const T& value)	요소를 맨 앞에 삽입
l.pop_front()	요소를 맨 앞에서 제거

예제

#include <iostream>
#include <list>
using namespace std;
int main(void){
    list<int> l = {1,2,3,4,5};
    list<int>::iterator it;
    for(it=l.begin(); it!=l.end(); it++)
        cout << &*it << " " << *it << endl;
    cout << endl;
    l.erase(l.begin());
    for(it=l.begin(); it!=l.end(); it++)
        cout << &*it << " " << *it << endl;
    cout << endl;
    l.insert(l.end(), 6);
    l.insert(l.end(), 7);
    for(it=l.begin(); it!=l.end(); it++)
        cout << &*it << " " << *it << endl;
    return 0;
}

결과

vector와 달리 맨 앞 요소를 제거해도 다른 요소들의 주소값이 달라지지 않는다. 또한 메모리가 연속되지 않는것도 보인다.

 

참고: https://en.cppreference.com/w/cpp/container/list

2.3. std::deque

아래를 클릭해서 펼치기↓

요소 접근 함수

d.at(숫자)	경계 체크와 함께 지정된 요소 접근
d[숫자]	경계 체크 없이 지정된 요소 접근
d.front()	처음 요소 접근
d.back()	마지막 요소 접근

iterators 함수

d.begin()	처음의 iterator 반환
d.end()	마지막의 iterator 반환

용량 함수

d.empty()	컨테이너가 비어있는지 아닌지
d.size()	요소들의 개수 반환

바꾸는 함수

d.clear()	콘텐츠를 클리어함
d.insert(const_iterator pos, const T& value)	요소 삽입
d.erase(iterator pos)	요소 제거
d.push_back(const T& value)	요소를 맨 뒤에 삽입
d.pop_back()	요소를 맨 뒤에서 제거
d.push_front(const T& value)	요소를 맨 앞에 삽입
d.pop_front()	요소를 맨 앞에서 제거

예제

#include <iostream>
#include <deque>
using namespace std;
int main(void){
    deque<int> d = {1,2,3,4,5};
    deque<int>::iterator it;
    for(it=d.begin(); it!=d.end(); it++)
        cout << &*it << " " << *it << endl;
    cout << endl;
    d.erase(d.begin());
    for(it=d.begin(); it!=d.end(); it++)
        cout << &*it << " " << *it << endl;
    cout << endl;
    d.insert(d.end(), 6);
    d.insert(d.end(), 7);
    for(it=d.begin(); it!=d.end(); it++)
        cout << &*it << " " << *it << endl;
    return 0;
}

결과

vector와 달리 맨 앞 요소를 제거해도 다른 요소들의 주소값이 달라지지 않는다. 하지만 list같이 node가 연결되지는 않고, 연속된 메모리에 요소들이 존재한다.

 

참고: https://en.cppreference.com/w/cpp/container/deque

2.4. std::queue

아래를 클릭해서 펼치기↓

요소 접근 함수

q.front()	처음 요소 접근
q.back()	마지막 요소 접근

용량 함수

q.empty()	컨테이너가 비어있는지 아닌지
q.size()	요소들의 개수 반환

바꾸는 함수

q.push(const value_type& value)	요소를 마지막에 삽입
q.pop()	처음 요소 삭제

예제

#include <iostream>
#include <queue>
using namespace std;
int main(void){
    queue<int> q;
    for(int i=0; i<10; i+=2)
        q.push(i);
    for(;!q.empty(); q.pop())
        cout << q.front() << endl;
    return 0;
}

결과

자료구조 queue이다.

 

참고: https://en.cppreference.com/w/cpp/container/queue

2.5. std::priority_queue

아래를 클릭해서 펼치기↓

요소 접근 함수

pq.top()

top 요소 접근

용량 함수

pq.empty()	컨테이너가 비어있는지 아닌지
pq.size()	요소들의 개수 반환

바꾸는 함수

pq.push(const value_type& value)	요소를 삽입 후 정렬
pq.pop()	top 요소 삭제

예제

#include <iostream>
#include <queue>
using namespace std;
int main(void){
    priority_queue<int> pq;
    pq.push(4);
    pq.push(41);
    pq.push(214878);
    pq.push(5385);
    pq.push(8787);
    for(;!pq.empty(); pq.pop())
        cout << pq.top() << endl;
    return 0;
}

결과

heap을 이용한 우선순위 큐이다.

 

참고: https://en.cppreference.com/w/cpp/container/priority_queue

2.6. std::stack

아래를 클릭해서 펼치기↓

요소 접근 함수

s.top()

top 요소 접근

용량 함수

s.empty()	컨테이너가 비어있는지 아닌지
s.size()	요소들의 개수 반환

바꾸는 함수

s.push(const value_type& value)	요소를 top에 삽입
s.pop()	top 요소 삭제

예제

#include <iostream>
#include <stack>
using namespace std;
int main(void){
    stack<int> s;
    s.push(4);
    s.push(41);
    s.push(214878);
    s.push(5385);
    s.push(8787);
    for(;!s.empty(); s.pop())
        cout << s.top() << endl;
    return 0;
}

결과

자료구조 stack이다.

 

참고: https://en.cppreference.com/w/cpp/container/stack

2.7. std::set

아래를 클릭해서 펼치기↓

iterators 함수

s.begin()	처음의 iterator 반환
s.end()	마지막의 iterator 반환

용량 함수

s.empty()	컨테이너가 비어있는지 아닌지
s.size()	요소들의 개수 반환

바꾸는 함수

s.clear()	콘텐츠를 클리어함
s.insert(const value_type& value)	요소 삽입
s.erase(iterator pos) s.erase(const Key& key)	요소 제거

검색 함수

s.contains(const Key& key)	키와 맞는 요소의 개수 반환
s.find(const Key& key)	구체적인 키인 요소를 찾는다.
s.lower_bound(const Key& key)	키보다 작지 않은 요소를 반환
s.upper_bound(const Key& key)	키보다 큰 요소를 반환

예제

#include <iostream>
#include <set>
using namespace std;
int main(void){
    set<int> s;
    set<int>::iterator it;
    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(40);
    cout << s.size() << endl;
    for(it = s.begin(); it!=s.end(); it++)
        cout << *it << " ";
    cout << endl;
    s.insert(40);
    cout << s.size() << endl;
    return 0;
}

결과

수학 집합이다. 동일 값을 여러번 넣어도 한개만 가진다.

 

참고: https://en.cppreference.com/w/cpp/container/set

2.8. std::map

아래를 클릭해서 펼치기↓

요소 접근 함수

m.at(숫자)	경계 체크와 함께 지정된 요소 접근
m[숫자]	경계 체크 없이 지정된 요소 접근 또는 삽입

iterators 함수

m.begin()	처음의 iterator 반환
m.end()	마지막의 iterator 반환

용량 함수

m.empty()	컨테이너가 비어있는지 아닌지
m.size()	요소들의 개수 반환

바꾸는 함수

m.clear()	콘텐츠를 클리어함
m.insert(const value_type& value)	요소 삽입
m.erase(iterator pos) m.erase(const Key& key)	요소 제거

검색 함수

m.contains(const Key& key)	요소가 컨테이너에 들어있는지
m.find(const Key& key)	구체적인 키인 요소를 찾는다.
m.lower_bound(const Key& key)	키보다 작지 않은 요소를 반환
m.upper_bound(const Key& key)	키보다 큰 요소를 반환

예제

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(void){
    map<string, string> m;
    map<string, string>::iterator it;
    m["CPU"] = "ryzen 5600";
    m["GPU"] = "nvidia rtx 4070";
    m["RAM"] = "samsung 8GB 3200Mhz";
    for(it = m.begin(); it!=m.end(); it++)
        cout << it->first << " : " << it->second << endl;
    cout << endl;
    cout << "cpu? " << m["CPU"] << endl;
    m.erase("CPU");
    cout << endl;
    for(it = m.begin(); it!=m.end(); it++)
        cout << it->first << " : " << it->second << endl;
    return 0;
}

결과

python의 dictionary, javascript의 object같이 key-value쌍으로 저장되는 구조이다. 

 

참고: https://en.cppreference.com/w/cpp/container/map