2017년 2월 6일 (월) 04:11에 Maintenance script님의 편집

2017-02-06T04:11:42Z

새 문서

[include(틀:프로젝트 문서,프로젝트=나무위키 컴퓨터 프로젝트)]
'''S'''tandard '''T'''emplate '''L'''ibrary

[목차]

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

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

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

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

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

이 외에도 다양한 구현이 있다. [[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로 삽입 시점부터 정렬된 상태로 저장된다. 구현은 대개의 경우(사용가능한 범위 내에서는 전부라고 해도 무방할 정도로) [[트리#s-3.1.1.3|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'''과 개념적으로 유사하나 [[트리#s-3.1.1.3|red-black tree]] 대신 [[해시|hash]]를 이용하여 구현되어 시간복잡도도 [[해시|hash]]의 특성을 따른다. 삽입/검색/삭제는 평균적으로 O(1), 최악의 경우 O(n).
* '''stack'''/'''queue'''/'''priority_queue''': 위의 container들을 이용하여 [[스택(자료구조)|스택]], [[큐(자료구조)|큐]], 우선순위 큐를 위한 인터페이스 제공

=== 반복자 ===
컨테이너의 원소를 순회하는 방법을 추상화한 객체들.
* '''forward_iterator'''
* '''reverse_iterator'''
* '''insert_iterator'''
* '''input_iterator_tag'''
* '''output_iterator_tag'''
추가바람

=== 알고리즘 ===
반복자로 지정되는 자료의 집합에 대한 작업을 정의해놓은 템플릿 함수.
* for_each
* transform
* generate
* find
* binary_search
* stable_sort
* sort
추가바람
== 여담 ==
C++11 이 나오면서 많은 변화를 겪었는데, rvalue reference 가 지원되면서 move semantics 가 적용되어 불필요한 복사를 줄여 성능 개선이 있었다. 또한, lambda function 을 지원하면서 과거에 클래스를 정의하고 그 안에 함수를 정의하여 넘기는 식으로 functor를 복잡하게 만들어야 했었던 부분들을 lambda 로 변경하여 프로그래밍이 깔끔해졌다.[* for_each 같은 것을 예로 들 수 있다.]

== 외부 링크 ==
* [[http://en.cppreference.com/w/|레퍼런스 위키 사이트]]

STL - 편집 역사

2017년 2월 6일 (월) 04:11에 Maintenance script님의 편집