STL 이란?
- Standard Template Library의 약자로서 C++에서 제공하는 템플릿 기반 표준 라이브러리이다.
- 프로그램에 필요한 자료구조와 알고리즘을 Template로 제공하는 라이브러리
- STL라이브러리는 크게 STL 컨테이너(Container)와 STL 알고리즘(Algorithm)으로 구성되어 있다.
STL 컨테이너(Container)
STL 컨테이너는 데이터를 보관하고 관리하기 위한 여러가지 기능을 제공한다.
vector
- 동적 배열이므로 배열의 크기를 변경할 수 있다.
- 임의 접근이 가능하며, 뒤에서의 삽입이 빠르다.
- 삽입, 삭제, 탐색 O(n), 임의 원소 접근 O(1)보장
- Java의 ArrayList와 동일하다고 볼 수있다.
list
- 연결리스트이므로 데이터를 순차적으로 접근하고 관리할 때 유용하다.
- 위치에 관계없이 삽입과 삭제가 빠르다.
- 삽입, 삭제, 탐색 O(n), 임의 원소 접근 O(1)보장
deque
- 덱, 데크라고 한다.
- 임의 접근이 가능하며 앞과 뒤에서의 삽입이 빠르다.
- 삽입, 삭제, 탐색 O(n), 임의 원소 접근 O(1)보장
map
- 특정 키(key)로 데이터를 접근하고 관리할 수 있다.
- 키로 값에 접근하며 삽입과 삭제가 빠르다.
- 삽입, 삭제, 탐색 모두 O(log n) 보장
set
- 원소를 순서대로 관리하며 소속 검사와 삽입, 삭제가 빠르다.
- 중복된 원소를 허용하지 않는다.
- 삽입, 삭제, 탐색 모두 O(log n) 보장
stack
- top에서만 삽입과 삭제가 가능하다.
- LIFO(Last In First Out)방식으로 데이터를 삽입, 삭제한다.(후입선출)
- 삽입, 삭제 O(1) 보장
queue
- 삽입은 뒤쪽에서, 삭제는 앞쪽에서 수행한다.
- FIFO(First In First Out)방식으로 데이터를 삽입, 삭제한다.(선입선출)
- 삽입, 삭제 O(1) 보장
STL 컨테이너는 데이터를 저장하는 방식과 삽입, 정렬, 삭제하는 관리 방식에 따라 크게 세 가지 부류로 나눠볼 수 있다.
순차 컨테이너
- 데이터를 순차적으로 저장하는 가장 일반적인 컨테이너
- 삽입된 데이터를 저장할 때 별도의 제약이나 관리 규칙을 갖지 않는다.
- 임의의 위치에 원소를 삽입하거나 삭제할 수 있다.
- vector, list, deque 등이 속한다.
연관 컨테이너
- 데이터를 무조건 저장만 하는 것이 아니라 일정한 규칙에 따라서 데이터를 관리하는 컨테이너
- 정렬이나 해시 등의 방법을 통해 삽입되는 데이터를 항상 일정한 기준에 맞는 위치에 저장하므로 검색 속도가 빠르다.
- set, map 등이 속한다.
어댑터 컨테이너
- 순차 컨테이너를 변형하여 데이터를 미리 정해진 방식에 따라 관리한다.
- 데이터를 삽입하고 제거하는 순서가 항상 컨테이너의 규칙에 의해 결정된다.
- stack, queue, priority_queue 등이 속한다.
STL 컨테이너는 공통적으로 iterator 클래스를 제공 한다.
iterator는 반복자라고도 하는데 마치 포인터처럼 STL컨테이너의 특정 위치를 나타내는 역할을 한다.
- ++연산자를 이용해 다음 원소를 가리키도록 변경할 수 있고, * 연산자를 통해 해당 원소에 접근할 수 도 있다.
- list.begin(), list.end()와 같은 함수를 제공하는대 begin은 컨테이너의 가장 처음, end는 컨테이너의 마지막 위치를 가리킨다.
STL 알고리즘(Algorithm)
STL 알고리즘은 STL이 제공하는 범용 함수를 말한다.
정렬이나 검색처럼 프로그램에 구현에 자주 사용되는 기능을 함수 템플릿으로 준비해둔 것.
STL 알고리즘은 크게 네 가지로 분류 할 수 있다.
변경 불가 시퀀스 알고리즘 (find, for_each)
변경 가능 시퀀스 알고리즘 (copy, generate, remove, replace, fill, swap, reverse, transform)
정렬 관련 알고리즘 (sort, binary_search, merge)
범용 수치 알고리즘 (accumulate, inner_product)
참조
https://wonjayk.tistory.com/208?category=535160
https://blockdmask.tistory.com/67?category=249379
