'''S'''tandard '''T'''emplate '''L'''ibrary [목차] == 개요 == 타입 독립적인 [[자료구조]]와 [[알고리즘]]을 사용하는 일반화 프로그래밍(Generic programming) 개념을 구현하기 위해 개발되었던 [[C++]] 라이브러리를 지칭하는 말. 현재의 [[C++]] 언어 표준 라이브러리(C++ Standard Library)[* gcc에 내장된 구현체: libstdc++, clang에 내장된 구현체: libc++]에 크게 영향을 주었다. == 역사 == Alexander Stepanov (1979)는 제네릭 프로그래밍 기법에 대한 연구를 했다. 이 연구는 특정 언어와 관련있는 연구는 아니었지만 C++ (1983)에 영향을 주어 STL의 시초를 만들게 되었다. 연구의 결과물인 STL 구현체가 1993년에 C++ 표준안 제정 위원회[* 이 위원회의 결과물이 C++98 표준이다.]에 처음 제출되면서 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을 만들어 볼 수도 있고, 다른 구현체와 성능을 비교해보면 재미있을 것이다. 구현체의 종류는 대략 아래와 같은 것들이 있다. * SGI STL - Alexander Stepanov의 구현체를 기반으로 하는 구현체로, 이름 그대로 실리콘 그래픽스사에서 개발하였다. 다른 많은 구현체들이 이 버전을 기반으로 하고 있을 정도로 가장 잘 알려진 구현체라고 할 수 있다. 개발이 중단된 지 오래되었다. * Dinkumware STL - [[Visual Studio]]에서 이를 기반으로 개량해서 사용했는데 성능에서 안 좋은 얘기를 많이 들었다. * STLPort - SGI의 구현체를 기반으로 하고 있는 구현체. 과거에 괜찮은 속도로 Visual Studio에서 STLPort를 가져다가 사용하는 경우도 잦았으나 지금은 업데이트가 되지 않고 있다. * [[https://github.com/electronicarts/EASTL|EASTL]] - [[EA SPORTS]]에서 구현한 STL로, 게임 회사들은 이처럼 퍼포먼스 극대화를 위해 자체적으로 STL을 개발하여 쓰기도 한다. * [[https://github.com/samchon/tstl|TSTL]] - [[TypeScript]]에 포팅된 STL 구현체. 이례적으로 C++가 아닌 다른 언어에 구현된 STL. 이 외에도 다양한 구현이 있다. [[GCC]]나 [[Visual Studio]]가 과거에는 특정 구현체를 기반으로 만들어졌지만 독립적으로 개발하면서 지금은 전혀 다른 구현체라고 해도 무방하다. == 구성 == STL은 크게 컨테이너, 반복자, 알고리즘의 3가지로 구성되어 있다, === 컨테이너 === 자료를 저장하는 클래스 템플릿의 집합. 구현하고자 하는 동작에서 가장 오버헤드가 걸릴 것으로 생각되는 부분을 고려하여 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''': 위의 컨테이너들을 이용하여 [[스택(자료구조)|스택]], [[큐(자료구조)|큐]], 우선순위 큐를 위한 인터페이스를 제공한다. 컨테이너 어댑터에 속하며 컨테이너는 아니다. === [[Iterator|반복자]] === 컨테이너의 원소를 순회하는 방법을 추상화한 객체들. * '''forward_iterator''' * '''reverse_iterator''' * '''insert_iterator''' * '''input_iterator_tag''' * '''output_iterator_tag''' * '''bidirectional_iterator''' * '''random_iterator''' === 알고리즘 === 반복자로 지정되는 자료의 집합에 대한 작업을 정의해놓은 템플릿 함수. * '''for_each''' * '''transform''' * '''generate''' * '''find''' * '''binary_search''' * '''stable_sort''' * '''sort''' == 여담 == C++11이 나오면서 많은 변화를 겪었는데, 표준 라이브러리에 우측값 참조가 적용되어 불필요한 복사를 줄일 수 있다. 또한 [[람다 함수]]를 지원하면서 프로그래밍이 깔끔해졌다. for_each 같은 것을 예로 들 수 있다. C++17에서 드디어 알고리즘들이 멀티스레드를 지원하기로 하였다. 알고리즘 호출시에 {{{std::execution::sequenced_policy, std::execution::parallel_policy, std::execution::parallel_unsequenced_policy}}}를 선택할 수 있다. 2019년 6월 현재 GCC 9와 MSVC 2017, Intel C++ 컴파일러가 이를 지원한다. LLVM/Clang의 경우 아직 지원하지 않는다. 표준 라이브러리는 단순히 API만 표준이며 성능이 천차만별이다. 이는 전체적으로 [[예외 처리]]나 플랫폼 이식성, 호환성, 범용성, 완성도 같은 문제 때문이다. 게임 업계에서는 예외 기능을 거의 쓰지 않으며 성능을 극한까지 끌어내야 고품질, 대량의 처리가 가능해지므로 직접 구현해서 쓰는 경우가 적지 않다. [[게임 엔진]]을 사서 쓰지 않고 자체 엔진이 있다면 90%는 재구현한다. 특히 C++ 소스코드를 지원하는 게임엔진들은 vector나 list 등의 기본적인 템플릿 자료형부터 따로 지원되는 경우가 많다. [[Boost]]에서 넘어온 라이브러리들이 상당히 많다. 애초에 부스트의 개발진들이 표준 위원회에 많이 속해있으며, 사실상 부스트가 STL로 넘어오기 전에 사용되는 테스트베드라고 봐도 좋을 정도이다. == 외부 링크 == * [[http://www.cplusplus.com/reference|레퍼런스 사이트 - cplusplus.com]] * [[http://en.cppreference.com/w/|래퍼런스 사이트 - cppreference.com]] [[분류:라이브러리]]