표준 템플릿 라이브러리
'''S'''tandard '''T'''emplate '''L'''ibrary
타입 독립적인 자료구조와 알고리즘을 사용하는 일반화 프로그래밍(Generic programming) 개념을 구현하기 위해 개발되었던 C++ 라이브러리를 지칭하는 말. 현재의 C++ 언어 표준 라이브러리(C++ Standard Library)[1]에 크게 영향을 주었다.
Alexander Stepanov (1979)는 제네릭 프로그래밍 기법에 대한 연구를 했다. 이 연구는 특정 언어와 관련있는 연구는 아니었지만 C++ (1983)에 영향을 주어 STL의 시초를 만들게 되었다. 연구의 결과물인 STL 구현체가 1993년에 C++ 표준안 제정 위원회[2]에 처음 제출되면서 C++과 인연을 맺게 되었고 Meng Lee와 David Musser가 추가로 협력하여 개선한 STL 구현체가 1994년에 C++ 표준으로 승인되었다.
현재의 modern C++ standard library가 Stephanov, Lee, Musser가 90년대에 개발한 Standard Template Library(STL)의 아이디어를 많이 수용한 것은 사실이나, C++ 표준안 그 어디에도 STL이라는 표현은 등장하지 않는다는 점이 주목할 만 하다. Effective C++의 저자인 Scott Meyers와 같이 나이 많은 거장 프로그래머들이 90년대의 관습 그대로 STL이라는 용어를 자신의 저작물에 지속적으로 사용하는 바람에 STL이라는 용어가 아직도 널리 사용되고 있으나, STL과 C++ standard library의 차이가 뭔지 묻는 수많은 구글 검색 결과가 보여주듯이 초보자들에게 꽤 커다란 혼돈을 주는 요소이다. STL은 여러 유명한 프로그래머의 강연이나 저자물에서 용어를 각기 다르게 사용해서 널리 오해되고 잘못 사용되는 용어이다. 예를 들면 Standard Template Library의 약자라는 설, Stephanov와 Lee가 근무하던 Software Technology Laboratory의 약자라는 설, STephanov and Lee의 약자라는 설, 등등. Stephanov와 Lee가 직접 작성한 Hewlet-Packard 버전의 최초의 STL이나, 실질적으로 더 널리 쓰이던 Silicon Graphics 버전의 SGI STL은 더 이상 관리가 되지 않고 방치가 된 지 오래이고, SGI STL을 계승하려고 노력하던 STLPort도 개발이 중단되었다. 결국 2019년 시점에서 평가하자면 초창기 STL의 구현체는 모두 사라지고 그 아이디어만이 살아남아서 C++ Standard Library에 흡수되었으므로, STL을 따로 떼어 지칭하는 것이 이제 의미가 없다고 하겠다.
이름에서 알 수 있다시피 템플릿을 이용해서 제네릭 프로그래밍을 잘 구현하고 있으며, 여기에 포함된 자료구조 컨테이너를 사용할 때는 어떤 타입이든 사용할 수 있다. 물론 사용자 정의 타입의 경우 vector처럼 vector<A> 식으로 정의하면 바로 사용할 수 있는 경우도 있는 반면, 데이터에 대한 연산이 필요한 경우 별도의 함수를 정의해 주어야 하는 경우가 있다. 키를 이용해 정렬이나 연산을 하는 경우를 예로 들 수 있고, map 계열이 대표적이다.
STL은 독립적으로 존재했던 역사적 이름으로, 표준에 포함된 이후로는 특별히 구분하지는 않는다. C++ 표준 라이브러리에는 기존 STL이 제공하는 것 외에도 템플릿 문법을 사용하는 많은 것이 있기 때문이다. 물론 아직도 표준 라이브러리 전체를 STL이라고 부르거나, 표준 라이브러리의 컨테이너 부분을 STL이라고 부르는 경우도 종종 보인다.
성능은 구현체마다 천차만별이었으나 C++14의 move semantics가 등장한 이후에 상향 평준화되는 추세다. 인터페이스만 동일하면 되므로 자기 자신만의 STL을 만들어 볼 수도 있고, 다른 구현체와 성능을 비교해보면 재미있을 것이다. 구현체의 종류는 대략 아래와 같은 것들이 있다.
STL은 크게 컨테이너, 반복자, 알고리즘의 3가지로 구성되어 있다,
자료를 저장하는 클래스 템플릿의 집합. 구현하고자 하는 동작에서 가장 오버헤드가 걸릴 것으로 생각되는 부분을 고려하여 container를 선택하면 성능 향상에 도움이 된다.
컨테이너의 원소를 순회하는 방법을 추상화한 객체들.
반복자로 지정되는 자료의 집합에 대한 작업을 정의해놓은 템플릿 함수.
C++11이 나오면서 많은 변화를 겪었는데, 표준 라이브러리에 우측값 참조가 적용되어 불필요한 복사를 줄일 수 있다. 또한 람다 함수를 지원하면서 프로그래밍이 깔끔해졌다. for_each 같은 것을 예로 들 수 있다.
C++17에서 드디어 알고리즘들이 멀티스레드를 지원하기로 하였다. 알고리즘 호출시에
표준 라이브러리는 단순히 API만 표준이며 성능이 천차만별이다. 이는 전체적으로 예외 처리나 플랫폼 이식성, 호환성, 범용성, 완성도 같은 문제 때문이다. 게임 업계에서는 예외 기능을 거의 쓰지 않으며 성능을 극한까지 끌어내야 고품질, 대량의 처리가 가능해지므로 직접 구현해서 쓰는 경우가 적지 않다. 게임 엔진을 사서 쓰지 않고 자체 엔진이 있다면 90%는 재구현한다. 특히 C++ 소스코드를 지원하는 게임엔진들은 vector나 list 등의 기본적인 템플릿 자료형부터 따로 지원되는 경우가 많다.
Boost에서 넘어온 라이브러리들이 상당히 많다. 애초에 부스트의 개발진들이 표준 위원회에 많이 속해있으며, 사실상 부스트가 STL로 넘어오기 전에 사용되는 테스트베드라고 봐도 좋을 정도이다.
1. 개요
타입 독립적인 자료구조와 알고리즘을 사용하는 일반화 프로그래밍(Generic programming) 개념을 구현하기 위해 개발되었던 C++ 라이브러리를 지칭하는 말. 현재의 C++ 언어 표준 라이브러리(C++ Standard Library)[1]에 크게 영향을 주었다.
2. 역사
Alexander Stepanov (1979)는 제네릭 프로그래밍 기법에 대한 연구를 했다. 이 연구는 특정 언어와 관련있는 연구는 아니었지만 C++ (1983)에 영향을 주어 STL의 시초를 만들게 되었다. 연구의 결과물인 STL 구현체가 1993년에 C++ 표준안 제정 위원회[2]에 처음 제출되면서 C++과 인연을 맺게 되었고 Meng Lee와 David Musser가 추가로 협력하여 개선한 STL 구현체가 1994년에 C++ 표준으로 승인되었다.
현재의 modern C++ standard library가 Stephanov, Lee, Musser가 90년대에 개발한 Standard Template Library(STL)의 아이디어를 많이 수용한 것은 사실이나, C++ 표준안 그 어디에도 STL이라는 표현은 등장하지 않는다는 점이 주목할 만 하다. Effective C++의 저자인 Scott Meyers와 같이 나이 많은 거장 프로그래머들이 90년대의 관습 그대로 STL이라는 용어를 자신의 저작물에 지속적으로 사용하는 바람에 STL이라는 용어가 아직도 널리 사용되고 있으나, STL과 C++ standard library의 차이가 뭔지 묻는 수많은 구글 검색 결과가 보여주듯이 초보자들에게 꽤 커다란 혼돈을 주는 요소이다. STL은 여러 유명한 프로그래머의 강연이나 저자물에서 용어를 각기 다르게 사용해서 널리 오해되고 잘못 사용되는 용어이다. 예를 들면 Standard Template Library의 약자라는 설, Stephanov와 Lee가 근무하던 Software Technology Laboratory의 약자라는 설, STephanov and Lee의 약자라는 설, 등등. Stephanov와 Lee가 직접 작성한 Hewlet-Packard 버전의 최초의 STL이나, 실질적으로 더 널리 쓰이던 Silicon Graphics 버전의 SGI STL은 더 이상 관리가 되지 않고 방치가 된 지 오래이고, SGI STL을 계승하려고 노력하던 STLPort도 개발이 중단되었다. 결국 2019년 시점에서 평가하자면 초창기 STL의 구현체는 모두 사라지고 그 아이디어만이 살아남아서 C++ Standard Library에 흡수되었으므로, STL을 따로 떼어 지칭하는 것이 이제 의미가 없다고 하겠다.
3. 내용
이름에서 알 수 있다시피 템플릿을 이용해서 제네릭 프로그래밍을 잘 구현하고 있으며, 여기에 포함된 자료구조 컨테이너를 사용할 때는 어떤 타입이든 사용할 수 있다. 물론 사용자 정의 타입의 경우 vector처럼 vector<A> 식으로 정의하면 바로 사용할 수 있는 경우도 있는 반면, 데이터에 대한 연산이 필요한 경우 별도의 함수를 정의해 주어야 하는 경우가 있다. 키를 이용해 정렬이나 연산을 하는 경우를 예로 들 수 있고, map 계열이 대표적이다.
STL은 독립적으로 존재했던 역사적 이름으로, 표준에 포함된 이후로는 특별히 구분하지는 않는다. C++ 표준 라이브러리에는 기존 STL이 제공하는 것 외에도 템플릿 문법을 사용하는 많은 것이 있기 때문이다. 물론 아직도 표준 라이브러리 전체를 STL이라고 부르거나, 표준 라이브러리의 컨테이너 부분을 STL이라고 부르는 경우도 종종 보인다.
4. 구현체 종류
성능은 구현체마다 천차만별이었으나 C++14의 move semantics가 등장한 이후에 상향 평준화되는 추세다. 인터페이스만 동일하면 되므로 자기 자신만의 STL을 만들어 볼 수도 있고, 다른 구현체와 성능을 비교해보면 재미있을 것이다. 구현체의 종류는 대략 아래와 같은 것들이 있다.
- SGI STL - Alexander Stepanov의 구현체를 기반으로 하는 구현체로, 이름 그대로 실리콘 그래픽스사에서 개발하였다. 다른 많은 구현체들이 이 버전을 기반으로 하고 있을 정도로 가장 잘 알려진 구현체라고 할 수 있다. 개발이 중단된 지 오래되었다.
- Dinkumware STL - Visual Studio에서 이를 기반으로 개량해서 사용했는데 성능에서 안 좋은 얘기를 많이 들었다.
- STLPort - SGI의 구현체를 기반으로 하고 있는 구현체. 과거에 괜찮은 속도로 Visual Studio에서 STLPort를 가져다가 사용하는 경우도 잦았으나 지금은 업데이트가 되지 않고 있다.
- EASTL - EA SPORTS에서 구현한 STL로, 게임 회사들은 이처럼 퍼포먼스 극대화를 위해 자체적으로 STL을 개발하여 쓰기도 한다.
- TSTL - TypeScript에 포팅된 STL 구현체. 이례적으로 C++가 아닌 다른 언어에 구현된 STL.
5. 구성
STL은 크게 컨테이너, 반복자, 알고리즘의 3가지로 구성되어 있다,
5.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: 위의 컨테이너들을 이용하여 스택, 큐, 우선순위 큐를 위한 인터페이스를 제공한다. 컨테이너 어댑터에 속하며 컨테이너는 아니다.
5.2. 반복자
컨테이너의 원소를 순회하는 방법을 추상화한 객체들.
- forward_iterator
- reverse_iterator
- insert_iterator
- input_iterator_tag
- output_iterator_tag
- bidirectional_iterator
- random_iterator
5.3. 알고리즘
반복자로 지정되는 자료의 집합에 대한 작업을 정의해놓은 템플릿 함수.
- for_each
- transform
- generate
- find
- binary_search
- stable_sort
- sort
6. 여담
C++11이 나오면서 많은 변화를 겪었는데, 표준 라이브러리에 우측값 참조가 적용되어 불필요한 복사를 줄일 수 있다. 또한 람다 함수를 지원하면서 프로그래밍이 깔끔해졌다. for_each 같은 것을 예로 들 수 있다.
C++17에서 드디어 알고리즘들이 멀티스레드를 지원하기로 하였다. 알고리즘 호출시에
std::execution::sequenced_policy, std::execution::parallel_policy, std::execution::parallel_unsequenced_policy표준 라이브러리는 단순히 API만 표준이며 성능이 천차만별이다. 이는 전체적으로 예외 처리나 플랫폼 이식성, 호환성, 범용성, 완성도 같은 문제 때문이다. 게임 업계에서는 예외 기능을 거의 쓰지 않으며 성능을 극한까지 끌어내야 고품질, 대량의 처리가 가능해지므로 직접 구현해서 쓰는 경우가 적지 않다. 게임 엔진을 사서 쓰지 않고 자체 엔진이 있다면 90%는 재구현한다. 특히 C++ 소스코드를 지원하는 게임엔진들은 vector나 list 등의 기본적인 템플릿 자료형부터 따로 지원되는 경우가 많다.
Boost에서 넘어온 라이브러리들이 상당히 많다. 애초에 부스트의 개발진들이 표준 위원회에 많이 속해있으며, 사실상 부스트가 STL로 넘어오기 전에 사용되는 테스트베드라고 봐도 좋을 정도이다.