표준 템플릿 라이브러리

표준 템플릿 라이브러리(STL: Standard Template Library)는 C++을 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. 이것은 알고리즘, 컨테이너, 함수자 그리고 반복자라고 불리는 네 가지의 구성 요소를 제공한다.^[1]

STL은 컨테이너와 연관 배열 같은 C++을 위한 일반 클래스들의 미리 만들어진 집합을 제공하는데, 이것들은 어떤 빌트인 타입과도 그리고 어떤 사용자 정의 타입과도 같이 사용될 수 있다. STL 알고리즘들은 컨테이너들에 독립적인데, 이것은 라이브러리의 복잡성을 눈에 띄게 줄여주었다.

STL은 결과를 템플릿의 사용을 통해 달성한다. 이 접근법은 전통적인 런타임 다형성에 비해 훨씬 효과적인 컴파일 타임 다형성을 제공한다. 현대의 C++ 컴파일러들은 STL의 많은 사용에 의해 야기되는 어떤 추상화 페널티도 최소화하도록 튜닝되었다.

STL은 제네릭 알고리즘과 C++을 위한 데이터 구조체들의 첫 번째 라이브러리로서 만들어졌다. 이것은 다음의 네 가지를 기초로 한다. 제네릭 프로그래밍, 효율성을 잃지 않은 추상화, 폰 노이만 구조^[2] 그리고 밸류 시멘틱스(value semantics)가 그것이다.

구성

컨테이너

STL은 연속 컨테이너들과 연관 컨테이너들을 포함한다. 컨테이너들은 데이터를 저장하는 객체들이다. 표준 연속 컨테이너들은 vector, deque, 그리고 list를 포함한다. 표준 연관 컨테이너들은 set, multiset, map, multimap, hash_set, hash_map, hash_multiset 그리고 hash_multimap이다. 또한 container adaptors queue, priority_queue, 그리고 stack이 있는데 이것들은 다른 컨테이너들을 구현으로서 사용하면서 특정한 인터페이스와 함께하는 컨테이너들이다.

컨테이너	서술
간단한 컨테이너들
pair	pair 컨테이너는 간단한 연관 컨테이너로서 데이터 요소의 2-튜플 또는 객체들로(고정된 순서에 따라 'first' 그리고 'second'로 불리는) 이루어진다. STL 'pair'는 배치, 복사 그리고 비교될 수 있다. 모든 'first' 요소들이 유니크 키로서 행동하고 각각이 자신의 'second' 값 객체들과 연관되는 곳에서, map 또는 hash_map에 할당된 객체들의 배열은 기본 값으로 'pair' 타입이다.
시퀀스 (배열/연결 리스트연결 리스트): 정렬되지 않은
vector	C 배열과 같은 동적 배열로서 객체를 삽입하거나 제거할 때 자동으로 자신의 크기를 조정하는 능력을 갖는다. vector의 end에 요소를 삽입하는 것은 상환 상수 시간(amortized constant time)을 필요로 한다. 마지막 요소를 제거하는 것은 단지 상수 시간을 필요로 하는데, 크기 조정이 일어나지 않기 때문이다. 처음 또는 중간에 삽입하거나 삭제하는 것은 선형 시간이 든다. 불린 타입을 위한 특수화가 존재하는데 이것은 불린 값을 비트에 저장하기 위해 공간을 최적화한다.
list	이중 연결 리스트; 요소들이 근접한 메모리에 저장되지 않는다. 느린 검색과 접근(선형 시간)을 갖지만, 한 번 위치가 찾아지면 빠른 삽입과 제거 시간을 갖는다(상수 시간).
slist	단일 연결 리스트; 요소들이 근접한 메모리에 저장되지 않는다. 느린 검색과 접근(선형 시간)을 갖지만, 한 번 위치가 찾아지면 빠른 삽입과 제거 시간을 갖는다(상수 시간). 이것은 이중 연결 리스트보다 삽입과 제거에서 약간 효율적이며 적은 메모리를 사용한다. 하지만 단지 전방향으로만 반복될 수 있다. C++ 표준 라이브러리에서 다음으로 구현된다. `forward_list`
deque (double-ended queue)	시작과 끝에서 삽입과 삭제를 상환 상수 시간에 수행하는 벡터이지만 덱을 교체한 이후에 반복자 유효성을 보장하지 않는다.
컨테이너 어댑터
queue	FIFO 큐 인터페이스를 `push`/`pop`/`front`/`back` 연산들로 제공한다. `front()`, `back()`, `push_back()`, 그리고 `pop_front()` 연산을 지원하는 어느 시퀀스들도 큐를 인스턴스화하는데 사용될 수 있다(예를 들면 `list` 그리고 `deque`).
priority queue	우선순위 큐 인터페이스를 `push/pop/top` 연산들로 제공한다(높은 우선순위 요소가 위에 존재한다). 연산 `front()`, `push_back()`, 그리고 `pop_back()` 를 지원하는 어느 임의 접근 시퀀스도 priority_queue를 인스턴스화하는데 사용될 수 있다(예를 들면 `vector` 그리고 `deque`). 이것은 힙을 사용하여 구현된다. 요소들은 추가적으로 비교를 지원해야 한다(어느 요소가 높은 우선순위를 갖는지와 먼저 pop되어야 하는지를 결정하기 위한).
stack	LIFO stack 인터페이스를 `push/pop/top` 연산들을 통해 지원한다(마지막에 삽입된 요소가 top에 존재한다). 연산 `back()`, `push_back()`, 그리고 `pop_back()`을 지원하는 어떤 시퀀스도 스택을 인스턴스화하는데 사용될 수 있다(예를 들면 `vector`, `list`, 그리고 `deque`).
연관 컨테이너: 정렬된
set	수학적 set; set에서 요소를 삽입하고 제거하는 것은 set에서 가리키는 반복자를 무효화하지 않는다. 집합 연산 union, intersection, difference, symmetric difference 그리고 포함 테스트를 제공한다. 데이터의 형은 반드시 비교 연산 `<` 또는 명시된 커스텀 비교자 함수를 통해서 구현되어야 한다; 이러한 비교 연산 또는 비교자 함수는 반드시 strict weak ordering을 보장해야 하며, 아니면 행위가 정의되지 않는다. 일반적으로 자가 균형 이진 탐색 트리를 사용해서 구현된다.
multiset	set과 같지만 중복 요소들을 허용한다(수학적으로 중복집합(Multiset)).
map	연관 배열; 한 데이터 아이템(키)에서 다른 것(값)으로 매핑을 허용한다. 키의 타입은 반드시 비교 연산 `<` 또는 명시된 커스텀 비교자를 통해 구현되어야 한다; 이러한 비교 연산 또는 비교자 함수는 반드시 strict weak ordering을 보장해야 하며, 아니면 행위가 정의되지 않는다. 일반적으로 자가 균형 이진 탐색 트리를 사용해서 구현된다.
multimap	map과 같지만 중복 키들을 허용한다.
hash_set hash_multiset hash_map hash_multimap	각각 set, multiset, map 또는 multimap과 비슷하지만 해시 테이블을 이용하여 구현된다; 키들은 순차적이지 않지만 해시 함수는 반드시 키 타입을 위해 존재해야 한다. 이러한 타입들은 C++ 표준에서 버려졌다; 비슷한 컨테이너들이 C++11에서 다른 이름으로 표준화되었다(`unordered_set` 그리고 `unordered_map`).
다른 타입의 컨테이너들
bitset	불린의 고정 길이 벡터와 비슷하게 비트들을 저장한다. bitwise 연산을 구현하며 반복자가 없다. 임의 접근을 제공한다.
valarray	수치적 사용을 위해 의도된 또다른 배열 데이터 타입(특히 벡터와 행렬을 표현하기 위한); C++ 표준은 이 의도된 목적을 위해 특정한 최적화를 허용한다.

반복자 (Iterator)

STL은 반복자의 5가지 종류를 구현한다. 이것들로는 input iterators (단지 값들의 시퀀스를 읽는데 사용되는), output iterators (단지 값들의 시퀀스를 쓰는데 사용되는), forward iterators (읽어지고 쓰여지며 앞으로 움직일 수 있는), bidirectional iterators (forward iterator들과 같지만, 뒤로도 움직일 수 있는) 그리고 random access iterators (한 연산에서 어떤 수만큼이라도 자유롭게 움직일 수 있는)이 있다.

전체 10번 중에서 간단하게 앞으로 10번 움직임으로써 bidirectional iterator가 random access iterator처럼 행동하게 할 수 있다. 그러나 random access iterator가 효율적인 장점을 제공한다. 예를 들면 벡터는 random access iterator를 가질 수 있지만, 리스트는 오직 bidirectional iterator만을 가질 수 있다.

Iterator들은 STL의 일반성을 가능케 하는 중요한 특징이다. 예를 들면 시퀀스를 역으로 만드는 알고리즘은 bidirectional iterator를 사용할 수 있지만, 같은 구현이 리스트, 벡터 그리고 데큐를 사용해서 만들어질 수 있다. 사용자가 생성한 컨테이너들은 단지 5개의 표준 반복자 인터페이스 중 하나를 구현한 반복자를 제공하고, STL에서의 모든 알고리즘들은 컨테이너에서 사용될 수 있어야 한다.

이 일반성은 또한 가끔은 단점을 갖는다. 예를 들면 map 또는 set 같은 연관 컨테이너에서 검색을 수행할 때, 컨테이너 자신에게서 제공되는 호출 멤버 함수들 대신 반복자를 사용하는 것이 더 느릴 수 있다. 이것은 연관 컨테이너의 메소드가 내부 구조에 대한 지식을 갖지만 반복자를 사용하는 알고리즘에서는 불투명하기 때문이다.

알고리즘

STL에서 제공되는, 검색이나 정렬 같은 활동을 수행하는 알고리즘 대부분은 각각 반복자의 특정한 수준을 요구한다(그러므로 반복자들에 의해 인터페이스를 제공받는 어떠한 컨테이너에서도 동작할 것이다). binary_search 그리고 lower_bound 같은 검색 알고리즘은 이진 검색 알고리즘을 사용하며 정렬 알고리즘 같이(비교 연산 < 또는 명시된 커스텀 비교자 함수를 구현해야 하는) 데이터 타입을 요구한다; 이러한 비교 연산 또는 비교자 함수는 반드시 strict weak ordering을 보장해야 한다. 이것 외에도 알고리즘들은 다양한 요소들에서 힙을 만들고, 다양한 요소들의 사전 편찬상의 정렬된 순열을 생성하기 위해 제공되며, 정렬된 범위를 합병하고 정렬된 범위들의 합집합, 교집합, 여집합을 수행한다.

함수자(functor)

STL은 함수 호출 연산자 (operator())를 오버로드하는 클래스들을 포함한다. 이러한 클래스들의 인스턴스들은 함수자 또는 함수 객체라고 불린다. 함수자들은 연관된 함수가 파라미터화되는 행동을 허용하고 (예를 들면 함수자의 생성자로 넘겨지는 인자를 통해서) 연관된 per-functor 상태를 함수와 함께 사용될 수 있게 유지한다. 함수자와 함수 포인터 모두 함수 호출의 문법을 사용해서 유발될 수 있기 때문에, 이것들은 상응하는 파라미터가 오직 함수 호출 문맥에서만 보일 때 인자로서 교체될 수 있다.

특히 함수자의 일반적인 타입은 술어 구문(predicate)이다. 예를 들면 find_if 같은 알고리즘은 시퀀스의 요소들에서 동작하는 단항(unary) 술어를 갖는다. sort, partial_sort, nth_element 그리고 모든 정렬된 컨테이너들은 순약 순서(strict weak ordering)를 제공해야 하는 이항 술어를 사용한다. 만약 제공되지 않는다면 이러한 알고리즘들과 컨테이너들은 기본값으로 less를 사용하며, 이것은 결국 less-than-operator <를 호출한다.

비판

C++ 컴파일러들의 구현의 질

C++ 컴파일러의 QoI(Quality of Implementation)은 STL(그리고 일반적으로 템플릿화 된 코드)의 가용성에 큰 영향을 갖는다.

템플릿과 관련된 에러 메시지들은 매우 길고 판독하기 어려운 경향이 있다. 이 문제는 매우 심각하게 여겨져서, 많은 툴들이 이러한 에러 메시지를 간소화하고 이해하기 쉽게하는 식으로 만들어졌다.
STL 템플릿들의 부주의한 사용은 코드 비대화를 유발할 수 있다. 이 문제점은 STL 구현 안에서 사용되는 특별한 기법(내부적으로 void* 컨테이너들의 사용)들과 컴파일러에 의한 최적화 기법 향상으로 대응하고 있다. 이것은 부주의하게 단지 C 라이브러리 함수들 전체를 다른 종류의 작업에 그냥 복사하는 것과 비슷하다.
템플릿 인스턴스화는 컴파일 시간과 메모리 사용을 증가시키는 경향이 있다. 컴파일러 기법이 충분히 향상되기 전까지, 이 문제는 매우 세심하게 특정한 문법을 피하고 세심하게 코딩해도 오직 부분적으로만 제거되었다.

다른 이슈들

STL 컨테이너들을 소스 코드 안의 상수들로 초기화하는 것은 C부터 내려온 데이터 구조체만큼 쉽지 않다.
STL 컨테이너들은 기본(base) 클래스로 사용되기 위한 것이 아니다(이것의 소멸자들은 의도적으로 non-virtual하다); 컨테이너를 상속하는 것은 흔한 실수이다.^[3]^[4]
STL에 의해 구현된 반복자의 개념은 이해하기 어려울 수 있다: 예를 들면 반복자가 가리키던 값이 지워지면, 반복자 자체는 더 이상 유효하지 않다. STL의 대부분의 구현들이 느리지만 이러한 에러를 찾아낼 수 있는 디버그 모드를 제공한다. 예를 들면 자바에서도 비슷한 문제가 존재한다. Range는 반복자를 대체하는 더 안전하고 유연한 형태로 제안된다.^[5]
특정한 반복자 패턴들은 STL 반복자 모델에 매핑되지 않는다. 예를 들면 callback enumeration API들은 coroutine의 사용 없이 STL 모델에 맞게 만들어질 수 없으며,^[6] 이것은 플랫폼 의존적이며 C++ 표준이 아니다.
컴파일러 컴플라이언스는, 컨테이너의 메모리 관리에 사용되는 할당자(allocator) 객체들이 상태 의존적인 행동을 할 것이라는 것을 보장하지 않는다. 예를 들면 포터블 라이브러리는 다른 풀(pool)들에서 이 타입의 다른 할당자 객체들을 사용해서 메모리를 끌어오는 할당자 타입을 정의할 수 없다.
알고리즘들의 집합이 완벽하지 않다: 예를 들면, copy_if 알고리즘은 버려졌다.^[7] (비록 C++11에서 추가되었지만)^[8]