STL 이란 Standard Template Library의 줄임말로 여러가지 자료구조와 알고리즘 등을 데이터 타입에 의존하지 않게 미리 만들어 놓은 라이브러리를 의미한다.
여러가지 유용한 STL이 있지만 그 중에서도 필수적인 몇가지 container에 대해 정리해보겟다.
Container는 특정한 type의 원소들을 저장하는 객체를 말한다.
대표적으로 사용되는 container는 vector, list, set, map, unordered_set, unordered_map, queue, priority_queue가 있다.
이외에도 deque이나 stack 등이 있지만 이번 포스팅에서는 위의 container에 대해서만 알아보겠다.
1. vector
#include <vector> 를 통해 사용할 수 있다.
Python의 list라고 생각하면 된다. 공간 복잡도는 O(n)이고 search, insert, delete 전부 O(n)의 시간복잡도를 갖는다.
하지만 push_back과 pop_back의 경우 O(1)의 시간 복잡도를 가진다.
내가 사용할 데이터의 순서가 중요하지 않고 단순히 저장만 하는 경우 vector를 적극적으로 이용하자.
2. list
#include <list> 를 통해 사용할 수 있다.
양방향 링크드 리스트 이다. 공간 복잡도와 search의 경우 vector와 동일하게 O(n)의 복잡도를 가진다. 하지만 insert와 delete가 O(1)의 시간복잡도를 가진다.
내가 사용할 데이터의 삽입, 삭제가 빈번하고 데이터의 재사용 빈도가 높다면 list 사용을 고려해보자.
3. set / map
#include <set>과 #include <map>을 통해 사용할 수 있다.
set은 key만 저장하지만 map은 key와 value를 저장한다.
set과 map은 binary search tree 형태로 이루어져 있고 중복된 값을 허락하지 않는다. 또한 데이터가 저장되면서 정렬된다.
공간 복잡도는 O(n)이고 search, insert, delete에 대하여 시간복잡도가 O(log n)이다.
내가 사용할 데이터가 중복을 허락하지 않고, 정렬이 필요하다면 set과 map을 사용하자.
4. unordered_set / unordered_map
#include <unordered_set>과 #include <unordered_map>을 통해 사용할 수 있다.
set과 map 처럼 unordered_set은 key만 저장하고 unordered_map은 key와 value를 저장한다.
Hash 구조이므로 어떤 값을 바로 찾을 때 유용하게 사용될 수 있다. 중복된 값을 허락하지 않지만 데이터가 저장될 때 정렬이 되지는 않는다.
공간 복잡도는 O(n)이고 평균적으로 search, insert, delete가 O(1)의 시간복잡도를 갖지만 최악의 경우 O(n)이 된다.
중복되지 않는 id를 가진 데이터에 빠르게 접근하고 싶을 때는 고려해볼만한 container다. 하지만 최악의 경우 O(n)의 시간복잡도를 가지므로, 데이터의 양이 많다면 hash로는 id만 저장하고 vector를 통해 접근하는게 빠를 수 있다.
5. queue
#include <queue>를 통해 사용할 수 있다.
선입선출(FIFO) 구조를 갖는 container 이다. push일 경우 O(1)의 시간복잡도를 갖지만 pop일 경우 O(n)의 시간복잡도를 갖는다.
vector처럼 모든 원소에 접근이 가능한 것이 아니라, 각 동작에 필요한 원소만 접근 가능하다.
BFS와 같은 알고리즘에 적용하여 사용할 수 있다.
6. priority queue
#include <priority_queue>를 통해 사용할 수 있다.
우선순위가 높은 데이터가 먼저 나가는 queue이다. heap 구조로 되어있어 push 시 O(log n) pop 시 O(log n)의 시간복잡도를 갖는다.
Dijkstra 알고리즘에 사용될 수 있고, set이 필요할 때 대신 사용하면 조금더 빠른 성능을 기대할 수 있다. lazy update와 같은 테크닉도 알아두면 좋다.
