STL이란 : Standard Template Library의 약자로 일반적으로 많이 사용이 되는 자료구조와 알고리즘을 일반화해서 사용하기 쉽도록 만들어놓은 라이브러리이다.
장점 : 처음부터 일일이 짤 필요가 없고 #include로 선언을 하고 사용하면 되기때문에 소스의 크기가 줄어든다.
단점 : 처음 배울때 시간을 많이 투자해야한다.
가독성이 떨어진다.
STL의 종류 : vector, list, stack, queue, map, set, deque, multiset, multimap, priority_queue
이것들도 각자의 성향에 따라 분류가 되는데 우선, 순차적컨테이너는 삽입과 삭제를 할때 순차적으로 이뤄지는 컨테이너다. 연관컨테이너는 삽입할 때마다 기본적으로 정렬이 되어서 들어가게된다. 그리고 이진트리구조를 갖는다. 마지막으로 어댑터컨테이너는 stack은 LIFO(Last In First Out), queue는 FIFO(First In Frist Out)처럼 정해진 방법으로 삽입삭제가 이루어진다.
순차 컨테이너(Sequence Container) : vector, list, deque
연관 컨테이너(Associate Container) : map, set, multimap, multiset
어댑터 컨테이너(Adapter Container) : stack, queue, priority_queue
컨테이너 |
설명 |
Vector |
뒤에 삽입이나 삭제시 속도가 빠르지만 중간에 할경우는 해당 위치에따라 속도가 다르다. 인덱스값으로 접근이 가능하기때문에 검색속도가 빠르다 |
List |
위치에 상관없이 삽입과 삭제가 빠르게 이뤄질수 있다. 순차적으로 검색을 해야하고, 벡터처럼 임의의 접근을 할수 없다. |
Deque |
앞뒤로 삽입과 삭제가 빠르고, 중간에 할경우에는 해당 위치에 따라 속도가 다르다. 인덱스값으로 접근이 가능하기때문에 검색속도가 빠르다. |
컨테이너 |
설명 |
Map |
키와 데이터를 같이 관리하는데, 키는 중복이 허용되지 않는다. 키값을 이용하여 원하는 데이터를 찾을 수 있다. 삽입과 삭제가 빠르지만 삽입할때마다 정렬을 한다. 양방향 반복자를 사용한다. |
Set |
map과 비슷하지만 키만 갖고, 중복이 허용되지 않는다. 검색, 삽입, 삭제가 빠르다. 양방향 반복자를 사용한다. |
Multimap |
map과 다른요인은 동일하지만, 키값이 중복될 수 있다. |
Multiset |
set과 다른요인은 동일하지만, 중복이 가능하다. |
컨테이너 |
설명 |
Stack |
top에서만 삽입과 삭제가 이루어진다. |
Queue |
삽입은 뒤에서 삭제는 앞에서 이루어진다. |
Priority_queue |
큰 값부터 차례대로 정렬이 이루어진다. 가장 큰 값의 접근과 삭제가 빠르게 이루어진다. |
삽입과 삭제가
중간에서 많이 일어날 경우 : list
앞에서 많이 일어날 경우 : deque, list
뒤에서 많이 일어날 경우 : stack, queue
임의의 접근이 일어날 경우 : vector, deque
가장 큰 값을 많이 찾는 경우 : priority_queue
|
vector |
list |
deque |
map |
set |
stack |
queue |
priority_queue |
삽입 |
O(n) |
O(1) |
O(1) |
O(log n) |
O(log n) |
O(1) |
O(1) |
O(1) / O(n) |
삭제 |
O(n) |
O(1) |
O(1) |
O(log n) |
O(log n) |
O(1) |
O(1) |
O(n) / O(1) |
검색 |
O(1) |
O(n) |
O(log n) |
O(log n) |
O(log n) |
|
|
|
| | | | | | top에서만 | | |
< O(n) < 