표준 템플릿 라이브러리 document_id A220623194654

표준 템플릿 라이브러리(STL: Standard Template Library)는 C++을 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. 이것은 알고리즘, 컨테이너, 함수자 그리고 반복자라고 불리는 네 가지의 구성 요소를 제공한다. STL은 컨테이너와 연관 배열 같은 C++을 위한 일반 클래스들의 미리 만들어진 집합을 제공하는데, 이것들은 어떤 빌트인 타입과도 그리고 어떤 사용자 정의 타입과도 같이 사용될 수 있다. STL 알고리즘들은 컨테이너들에 독립적인데, 이것은 라이브러리의 복잡성을 눈에 띄게 줄여주었다. STL은 결과를 템플릿의 사용을 통해 달성한다. 이 접근법은 전통적인 런타임 다형성에 비해 훨씬 효과적인 컴파일 타임 다형성을 제공한다. 현대의 C++ 컴파일러들은 STL의 많은 사용에 의해 야기되는 어떤 추상화 페널티도 최소화하도록 튜닝되었다. STL은 제네릭 알고리즘과 C++을 위한 데이터 구조체들의 첫 번째 라이브러리로서 만들어졌다. 이것은 다음의 네 가지를 기초로 한다. 제네릭 프로그래밍, 효율성을 잃지 않은 추상화, 폰 노이만 구조 그리고 밸류 시멘틱스(value semantics)가 그것이다. 구성 >> 컨테이너 STL은 연속 컨테이너들과 연관 컨테이너들을 포함한다. 컨테이너들은 데이터를 저장하는 객체들이다. 표준 연속 컨테이너들은 vector, deque, 그리고 list를 포함한다. 표준 연관 컨테이너들은 set, multiset, map, multimap, hash_set, hash_map, hash_multiset 그리고 hash_multimap이다. 또한 ''container adaptors'' queue, priority_queue, 그리고 stack이 있는데 이것들은 다른 컨테이너들을 구현으로서 사용하면서 특정한 인터페이스와 함께하는 컨테이너들이다. 불린 타입을 위한 특수화가 존재하는데 이것은 불린 값을 비트에 저장하기 위해 공간을 최적화한다. 연산 front(), push_back(), 그리고 pop_back() 를 지원하는 어느 임의 접근 시퀀스도 priority_queue를 인스턴스화하는데 사용될 수 있다(예를 들면 vector 그리고 deque). 이것은 힙을 사용하여 구현된다. 요소들은 추가적으로 비교를 지원해야 한다(어느 요소가 높은 우선순위를 갖는지와 먼저 pop되어야 하는지를 결정하기 위한). 연산 back(), push_back(), 그리고 pop_back()을 지원하는 어떤 시퀀스도 스택을 인스턴스화하는데 사용될 수 있다(예를 들면 vector, list, 그리고 deque). 반복자 (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)를 제공해야 하는 이항 술어를 사용한다. 만약 제공되지 않는다면 이러한 알고리즘들과 컨테이너들은 기본값으로 [http://www.sgi.com/tech/stl/less.html less]를 사용하며, 이것은 결국 less-than-operator <를 호출한다. 비판 >> C++ 컴파일러들의 구현의 질 C++ 컴파일러의 QoI(Quality of Implementation)은 STL(그리고 일반적으로 템플릿화 된 코드)의 가용성에 큰 영향을 갖는다.