STL이란?
표준 템플릿 라이브러리(Standard Template Library: STL)는 C++에서 일반적인 자료 구조와 알고리즘을 구현해 놓은 라이브러리의 집합이다. 지원하는 자료구조에는 vector, map, set 등이 있으며, 여러 가지 탐색 변경 알고리즘을 지원해 주고 있다. vector와 같은 자료 구조에 삽입할 변수의 형이 정해지 있지 않고, 일반적인 형이라고 가정한 뒤 vector와 같은 컨테이너가 구현되어 있다. 즉 이 때는 C++언어의 템플릿 기능을 이용하고 있다. 이처럼 자료의 유형에 상관없이 구현되어 있기 때문에 generic이라고 말하기도 한다.
컨테이너?
자료의 집합을 나타내는 클래스 템플릿이다. 각각의 컨테이너는 단위 작업에 필요한 시간복잡도에 의해 구분된다.
컨테이너 종류 및 특성
vector동적배열 컨테이너를 제공하는 클래스 템플릿이다. 크기 조절이 가능한 C 스타일의 동적 배열처럼 동작한다. 임의의 원소에의 접근이 상수시간이 보장되며, 배열의 끝에서의 삽입/삭제는 상각된(amortized) 상수시간이 보장된다. 하지만 임의의 위치에서의 삽입/삭제는 저장된 원소의 갯수에 비례하는 선형 시간을 필요로 한다. 끝에서의 삭제를 제외한 모든 삽입/삭제 동작에서 모든 반복자 가 무효화한다.deque양쪽 끝에서의 삽입/삭제에 대해 상각된 상수시간을 보장하는 컨테이너이다. 임의의 위치에서의 삽입/삭제는 선형시간을 필요로 한다. 임의의 위치에 대한 접근 역시 상수시간이다. 양쪽 끝에서의 삽입/삭제에는 다른 반복자가 무효화하지 않지만 삭제된 반복자는 무효화하며, 임의의 위치에서 삽입/삭제가 일어날 때역시 모든 반복자가 무효화한다.list임의의 위치에서의 삽입/삭제에 대해 상수시간을 보장하는 컨테이너이다. 모든 삽입/삭제 동작에 대해 상수시간을 보장하며, 명시적으로 삭제되지 않은 반복자가 무효화하는 일이 없다. 단, 임의의 원소에 대한 접근은 선형시간을 필요로 한다.set과 multiset임의의 원소에 대한 접근을 로그시간으로 보장하는 정렬된 집합이다. 모든 삽입/삭제/탐색에 대해 로그시간을 보장하며, 명시적으로 삭제된 것 이외의 반복자가 무효화하지 않는다.map과 multimap임의의 원소에 대한 접근을 로그시간으로 보장하는 정렬된 연관 컨테이너이다. 원소의 키를 원소의 값과 대응시켜 검색한다. 모든 삽입/삭제/탐색에 대해 로그시간을 보장하며, 명시적으로 삭제한 것 이외의 반복자가 무효화하지 않는다. 표준에서는 내부자료구조의 종류를 명시하고 있지는 않지만, 대부분의 STL구현에서는 내부 자료구조로 빨강검정 트리 등의 균형잡힌 이진트리를 사용하며, 시중에는 모든 STL구현에서 빨강검정트리를 사용하고 있다.stack목록의 한쪽 끝(top)에서만 삽입/삭제가 일어나는 자료구조를 나타내는 컨테이너. 끝에서의 삽입/삭제만을 제공하며, 이 작업은 상수시간을 보장한다. 반복자는 제공되지 않는다.queue삽입은 목록의 한쪽 끝(back)에서만, 삭제는 다른 쪽 끝(front)에서만 일어나는 자료구조를 나타내는 컨테이너. 삽입/삭제에 상수시간을 보장한다. 반복자는 제공되지 않는다.
반복자란?
컨테이너 내부의 요소를 순회(traversing)하는 방법을 캡슐화한 객체이다. STL 알고리즘은 반복자(iterator) 쌍으로 지정되는 범위의 자료에 대하여 작업을 수행하도록 되어 있다. 기본적으로 현재 가리키는 요소를 반환하는 *연산자와 ->연산자를 가지고 있으며, 그 외의 연산자는 반복자의 종류에 따라 다르다. 반복자에는 iterator, reverse_iterator, const_iterator, const_reverse_iterator가 있다. 반복자는 클래스 템플릿이며, STL에서는 대부분의 컨테이너가 반복자를 사용할 수 있다. 또한 컨테이너마다 특화되어 있는 자료구조를 선형적으로 다룰 수 있게 해 준다.
위키 펌