표준 템플릿 라이브러리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
C++ 표준 라이브러리
입출력 라이브러리
표준 템플릿 라이브러리
(STL)
v  d  e  h

표준 템플릿 라이브러리(Standard Template Library: STL)는 C++에서 일반적인 자료 구조와 알고리즘을 구현해 놓은 라이브러리의 집합이다. 지원하는 자료구조에는 vector, map, set 등이 있으며, 여러 가지 탐색 변경 알고리즘을 지원해 주고 있다. vector와 같은 자료 구조에 삽입할 변수의 형이 정해지 있지 않고, 일반적인 형이라고 가정한 뒤 vector와 같은 컨테이너가 구현되어 있다. 즉 이 때는 C++언어의 템플릿 기능을 이용하고 있다. 이처럼 자료의 유형에 상관없이 구현되어 있기 때문에 generic이라고 말하기도 한다.

구성[편집]

컨테이너[편집]

자료의 집합을 나타내는 클래스 템플릿이다. 각각의 컨테이너는 단위 작업에 필요한 시간복잡도에 의해 구분된다.

vector
동적배열 컨테이너를 제공하는 클래스 템플릿이다. 크기 조절이 가능한 C 스타일의 동적 배열처럼 동작한다. 임의의 원소에의 접근이 상수시간이 보장되며, 배열의 끝에서의 삽입/삭제는 상각된(amortized) 상수시간이 보장된다. 하지만 임의의 위치에서의 삽입/삭제는 저장된 원소의 갯수에 비례하는 선형 시간을 필요로 한다. 끝에서의 삭제를 제외한 모든 삽입/삭제 동작에서 모든 반복자 가 무효화한다.
deque
양쪽 끝에서의 삽입/삭제에 대해 상각된 상수시간을 보장하는 컨테이너이다. 임의의 위치에서의 삽입/삭제는 선형시간을 필요로 한다. 임의의 위치에 대한 접근 역시 상수시간이다. 양쪽 끝에서의 삽입/삭제에는 다른 반복자가 무효화하지 않지만 삭제된 반복자는 무효화하며, 임의의 위치에서 삽입/삭제가 일어날 때역시 모든 반복자가 무효화한다.
list
임의의 위치에서의 삽입/삭제에 대해 상수시간을 보장하는 컨테이너이다. 모든 삽입/삭제 동작에 대해 상수시간을 보장하며, 명시적으로 삭제되지 않은 반복자가 무효화하는 일이 없다. 단, 임의의 원소에 대한 접근은 선형시간을 필요로 한다.
setmultiset
임의의 원소에 대한 접근을 로그시간으로 보장하는 정렬된 집합이다. 모든 삽입/삭제/탐색에 대해 로그시간을 보장하며, 명시적으로 삭제된 것 이외의 반복자가 무효화하지 않는다.
mapmultimap
임의의 원소에 대한 접근을 로그시간으로 보장하는 정렬된 연관 컨테이너이다. 원소의 키를 원소의 값과 대응시켜 검색한다. 모든 삽입/삭제/탐색에 대해 로그시간을 보장하며, 명시적으로 삭제한 것 이외의 반복자가 무효화하지 않는다. 표준에서는 내부자료구조의 종류를 명시하고 있지는 않지만, 대부분의 STL구현에서는 내부 자료구조로 빨강검정 트리 등의 균형잡힌 이진트리를 사용하며, 시중에는 모든 STL구현에서 빨강검정트리를 사용하고 있다.
stack
목록의 한쪽 끝(top)에서만 삽입/삭제가 일어나는 자료구조를 나타내는 컨테이너. 끝에서의 삽입/삭제만을 제공하며, 이 작업은 상수시간을 보장한다. 반복자는 제공되지 않는다.
queue
삽입은 목록의 한쪽 끝(back)에서만, 삭제는 다른 쪽 끝(front)에서만 일어나는 자료구조를 나타내는 컨테이너. 삽입/삭제에 상수시간을 보장한다. 반복자는 제공되지 않는다.

반복자[편집]

컨테이너 내부의 요소를 순회(traversing)하는 방법을 캡슐화한 객체이다. STL 알고리즘은 반복자(iterator) 쌍으로 지정되는 범위의 자료에 대하여 작업을 수행하도록 되어 있다. 기본적으로 현재 가리키는 요소를 반환하는 *연산자와 ->연산자를 가지고 있으며, 그 외의 연산자는 반복자의 종류에 따라 다르다. 반복자에는 iterator, reverse_iterator, const_iterator, const_reverse_iterator가 있다. 반복자는 클래스 템플릿이며, STL에서는 대부분의 컨테이너가 반복자를 사용할 수 있다. 또한 컨테이너마다 특화되어 있는 자료구조를 선형적으로 다룰 수 있게 해 준다.

무효화(invalidation)
반복자가 가리키는 원소에 대한 참조가 정상적인 동작을 보장할 수 없게 되는 경우. 반복자를 제공한 컨테이너의 내용에 변화가 생길 때 주로 발생한다. 무효화 시점은 컨테이너의 종류마다 다르다.

알고리즘[편집]

가장 자주 쓰이는 몇가지 알고리즘을 들면 다음과 같다.

헤더 <algorithm>
find()
주어진 원소와 동등한 것으로 판단되는 원소를 검색하는 선형 검색 알고리즘. 기본적으로 ==연산자를 사용한다.
sort()
정렬 알고리즘으로서, O( n log n )의 시간 복잡도를 가진다. 대부분의 STL구현은 퀵 정렬 알고리즘을 사용한다.
stable_sort()
동등한 두 원소간의 상대적 위치가 변경되지 않음을 보장하는 정렬 알고리즘. 술어구문에 등호를 사용해도 무한루프에 빠지지 않는다.
make_heap()
어떤 구간 [S, E)를 힙으로 만든다.
sort_heap()
힙의 어떤 구간 [S, E)를 정렬된 배열로 만든다.
헤더 <functional>
max()
주어진 입력 중에서 가장 큰 값을 구한다. 기본 자료형 외에도 연산자를 오버로딩한 클래스나 구조체를 입력으로 받을 수 있다.
min()
max와 기능은 같지만 최소값을 반환한다.

함수자[편집]

알고리즘의 동작을 결정하는 객체. 함수호출 연산자( ()연산자 )를 적용할 수 있는 모든 대상이 함수자(functor)가 될 수 있다. 즉, 일반 함수, 혹은 ()연산자를 오버로딩한 클래스의 객체들이 해당된다. <functional>에는 greater<>, less<>, equal_to<> 등 여러 알고리즘에서 유용하게 사용할 수 있는 템플릿이 있다. 이 외에도 클래스 멤버 함수나 일반 함수를 함수 객체로 포장하는 여러 종류의 바인더 객체들이 정의되어 있다.
술어구문(predicate)
알고리즘의 동작을 정의하는 불린 함수자를 술어구문이라고 부른다. 일반 함수자와 다르게 술어구문은 내부상태가 없는 객체여야 한다. 특히 STL알고리즘에 쓰이는 이진 술어구문은 내부상태가 없을 것 이외에도 다음과 같은 조건(Strick Weak Ordering)을 가져야 한다.
  1. 한 원소 a에 대하여 술어구문 P는 P( a, a ) == false 이어야 한다.
  2. 두 원소 a와 b가 동등(equivalent)하다면, P( a, b ) == false 이고, P( b, a ) == false 이어야 한다.
  3. 세 원소 a, b, c에 대하여 P( a, b ) == true이고, P( b, c ) == true이면, P( a, c ) == true 이어야 한다.

문제점[편집]

STL은 개발의 범용성과 편리성의 장점 뒤에 단점이 존재한다.

  • 기본 할당자의 문제
대표적인 문제로, 메모리 할당이 비효율적이다. 비록 메모리 누수 같은 버그는 없지만, 메모리 단편화 현상을 유발시킨다. 하지만, 메모리 단편화의 문제는 사용자정의 할당자를 만들어 피할 수 있다.

같이 보기[편집]

바깥 고리[편집]