STL

Standard Template Library

1 개요

C++ 언어 표준으로 포함되어 있는 라이브러리 중 하나이다. 오해의 소지가 있을 수 있는데, STL 이라고 표준에 직접 명세가 되어 있는 것은 아니다. C++ 표준에서는 그냥 표준 라이브러리를 정의하고 있을 뿐이다. STL 은 독립적으로 존재했던 과거의 이름으로, 표준에 포함된 이후로는 특별히 구분하지는 않는다. C++ 표준 라이브러리에는 기존 STL 이 제공하는 것 외에도 많은 것이 있다. 물론 용어가 조금 애매하기 때문에 표준 라이브러리 전체를 STL 이라고 부르는 경우도 종종 보인다.

1979년 Alexander Stepanov 라는 사람이 만든 라이브러리가 STL 의 시초이다. 1979년이라는 연도를 보고 이상하게 생각하는 위키러도 있을 수 있는데, C++ 이 발표된 것은 1983년이다. 즉 이 라이브러리는 원래 C++ 용 표준 라이브러리를 만들어보자 라는 생각으로 만들어진 것은 아니다. 알다시피 STL 은 타입 독립적인 컨테이너에 대한 개념인 제네릭 프로그래밍을 잘 구현해놓은 라이브러리이고, 원래 Alexander Stepanov 는 제네릭 프로그래밍을 적용한 구현체를 개발하는 것이 목표였다. 즉 특정 언어를 타겟으로 만든 것은 아니지만, 어른의 사정으로 C++ 용 라이브러리를 개발하였고 이것이 나중에 표준 명세에 포함되었다.

이름에서 알 수 있다시피 템플릿을 이용해서 제네릭 프로그래밍을 잘 구현하고 있으며, 여기에 포함된 자료구조 컨테이너를 사용할 때는 어떤 타입이든 사용할 수 있다. 물론 사용자 정의 타입의 경우 vector 처럼 vector<A> 식으로 정의하면 바로 사용할 수 있는 경우도 있는 반면, 데이터에 대한 연산이 필요한 경우^[1] 별도의 함수를 정의해주어야 하는 경우가 있다.

표준 명세에 포함이 되어 있지만, 당연히 구현은 컴파일러가 하는 것이므로 성능은 구현체마다 천차만별이다. 인터페이스만 동일하면 되므로 자기 자신만의 STL 을 만들어 볼 수도 있고, 다른 구현체와 성능을 비교해보면 재미있을 것이다. 구현체의 종류는 대략 아래와 같은 것들이 있다.

SGI STL - Alexander Stepanov 의 구현체를 기반으로 하는 최초의 구현체로, 이름 그대로 실리콘 그래픽스사에서 개발하였다. 다른 많은 구현체들이 이 버전을 기반으로 하고 있을 정도로 가장 잘 알려진 구현체라고 할 수 있다.
Dinkumware STL - Visual Studio 에서 이를 기반으로 하고 있다. VS 에서 이를 기반으로 개량해서 사용했는데 성능에서 안 좋은 얘기를 많이 들었다.
STLPort - SGI 의 구현체를 기반으로 하고 있는 구현체. 과거에 괜찮은 속도로 Visual Studio 에서 STLPort 를 가져다가 사용하는 경우도 잦았으나 왜인지 지금은 업데이트가 되지 않고 있다.

이 외에도 다양한 구현이 있다. GCC 나 Visual Studio 가 과거에는 특정 구현체를 기반으로 만들어졌지만 독립적으로 개발하면서 지금은 전혀 다른 구현체라고 해도 무방하다.

2 구성

STL은 크게 컨테이너, 반복자, 알고리즘의 3가지로 구성되어 있다,

2.1 컨테이너

자료를 저장하는 클래스 템플릿의 집합. 구현하고자 하는 동작에서 가장 오버헤드가 걸릴 것으로 생각되는 부분을 고려하여 container를 선택하면 성능 향상에 도움이 된다.

vector/deque: 이름이 다소 이상하게 붙어 있지만 개념적으로는 크기가 자동으로 동적 할당되는 배열이며 operator overloading을 통해 C의 배열과 거의 비슷하게 사용할 수 있다. vector는 임의 위치 참조 O(1), 끝에 삽입/삭제 O(1), 끝을 제외한 임의 위치에서의 삽입/삭제 O(n). deque는 앞/끝 모두에서 O(1)로 삽입/삭제가 가능하지만 vector와는 달리 메모리 상에서 연속적인 공간으로 할당되지는 않는다.
list/forward_list: 양방향/단방향 연결 리스트. 임의 위치 참조 불가, 검색 O(n), 대신 위치를 알고 있는 경우 어느 위치에서나 삽입/삭제 O(1). 이러한 특성상 한개씩 스캐닝하면서 빈번히 삽입/삭제를 해야하는 경우에 유용하다.
set/multiset: 정렬이 가능한 객체들을 담기위한 container로 삽입 시점부터 정렬된 상태로 저장된다. 구현은 대개의 경우(사용가능한 범위 내에서는 전부라고 해도 무방할 정도로) red-black tree를 이용한다. 삽입/검색/삭제 O(log n). set의 경우는 정렬시 사용되는 값이 유일해야하며, multiset의 경우는 그렇지 않고, 같은 값인 경우 삽입된 순서가 유지된다.
map/multimap: set과 거의 비슷하나 그냥 객체만 저장하는 것이 아니라 정렬이 가능한 key와 그 key가 가리키는 객체의 pair로 저장된다. map은 key가 유일해야하며, multimap의 경우는 그렇지 않고, 같은 경우 삽입된 순서가 유지된다.
unordered_set/unordered_multiset/unordered_map/unordered_multimap: 위의 set, multiset, map, multimap과 개념적으로 유사하나 red-black tree 대신 hash를 이용하여 구현되어 시간복잡도도 hash의 특성을 따른다. 삽입/검색/삭제는 평균적으로 O(1), 최악의 경우 O(n).
stack/queue/priority_queue: 위의 container들을 이용하여 스택, 큐, 우선순위 큐를 위한 인터페이스 제공

2.2 반복자

컨테이너의 원소를 순회하는 방법을 추상화한 객체들.

forward_iterator
reverse_iterator
insert_iterator
input_iterator_tag
output_iterator_tag

추가바람

2.3 알고리즘

반복자로 지정되는 자료의 집합에 대한 작업을 정의해놓은 템플릿 함수.

for_each
transform
generate
find
binary_search
stable_sort
sort