STL은 표준 c++ 라이브러리의 일부분으로 Standard Template Library의 약자이다. STL은 프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하는 라이브러리이다.
STL의 구성 요소
- 컨테이너(Container): 객체를 지정하는 객체로 컬렉션 혹은 자료구조라고도 한다.
- 반복자(Iterator): 포인터와 비슷한 개념으로 컨테이너의 원소를 가리키고, 가리키는 원소에 접근하여 다음 원소를 가리키게 하는 기능을 한다.
- 알고리즘(Algorithm): 정렬, 삭제, 검색, 연산 등을 해결하는 일반화된 방법을 제공하는 함수 템플릿이다.
- 함수 객체(Function Object): 함수처럼 동작하는 객체로 operator() 연산자를 오버로딩한 객체이다. 컨테이너와 알고리즘 등에 클라이언트 정책을 반영하게 한다.
- 어댑터(Adaptor): 구성 요소의 인터페이스를 변경해 새로운 인터페이스를 갖는 구성 요소로 변경한다.(새로운 구성 요소처럼 보인다)
- 할당기(Allocator): 컨테이너의 메모리 할당 정책을 캡슐화한 클래스 객체로 모든 컨테이너는 자신만의 기본 할당기를 가지고 있다.
컨테이너(Container)
컨테이너는 같은 타입을 저장, 관리할 목적으로 만들어진 클래스이다. 컨테이너는 두 가지로 나뉜다.
- 표준 시퀸스 컨테이너(standrad squence container): 컨테이너 원소가 자신만의 삽입 위치(순서)를 가지를 컨테이너(vector, deque, list: 선형적)
- 표준 연관 컨테이너(standard associative container): 저장 원소가 삽입 순서와 다르게 특정 정렬 기준에 의해 자동 정렬되는 컨테이너(set, multiset, map, multimap: 비 선형적)
String 컨테이너 string 컨테이너는 스퀸스 컨테이너의 일종이지만 문자만을 저장하는 컨테이너로 표준 컨테이너의 요구사항을 지키지 못한다. 이런 컨테이너를 근사 컨테이너(almost container)라 하며, 내장 배열(arr[n])과 valarray도 근사 컨테이너이다.
또 컨테이너는 데이터를 하나의 연속한 메모리 단위로 저장하느냐에 따라 두 가지로 나뉜다.
- 연속 메모리 기반 컨테이너(array-based container): 데이터 여러 개가 하나의 메모리 단위에 저장된다. (vector, deque)
- 노드 기반 컨테이너(node-based cantainer): 데이터 하나를 하나의 메모리 단위에 저장한다. (list, set, multiset, map, multimap)
반복자(Iterator)
컨테이너의 원소를 가리키는 포인터처럼 동작하며, 컨테이너 원소를 순회하고 접근하는 일반화된 방법을 제공한다.
- 컨테이너의 종류에 상관없이 모든 컨테이너에서 사용하는 방법이 동일하다 (일반화)
- 반복자가 일반화 돼있기 때문에 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 한다.
반복자의 특징
- 반복자는 컨테이너 내부의 원소(객체)를 가리키고 접근할 수 있어야 한다.(*연산자 제공)
- 다음 원소로 이동하고 컨테이너의 모든 원소를 순회할 수 있어야 한다.(++ 연산자 제공, != ,== 비교연산자 제공)
STL에서 컨테이너 원소(객체)의 집합을 순차열(Sequence)라 한다.
모든 컨테이너는 자신만의 반복자를 제공하며, 멤버 함수 begin(), end()를 사용해 시작과 끝을 가리키는 반복자를 반환한다. 여기서 주의할 점은 순차열의 시작과 끝에서 끝은 실제 원소가 아닌 끝을 표시하는 원소하는 점이다.
반복자는 조작 방법에 따라 다섯 가지로 나뉜다.
- 입력 반복자(input iterator): 현 위치의 원소를 한 번만 읽을 수 있는 반복자
- 출력 반복자(output iterator): 현 위치의 원소를 한 번만 쓸 수 있는 반복자
- 순방향 반복자(forward iterator): 입력, 출력 반복자 기능에 순방향으로 이동(++)이 가능한 재할당 될 수 있는 반복자
- 양방향 반복자(bidirectional iterator): 순방향 반복자 기능에 역방향으로 이동(--)이 가능한 반복자
- 임의 접근 반복자(random access iterator): 양방향 반복자 기능에 +, -, +=, -=, [] 연산이 가능한 반복자
모든 컨테이너는 양방향 반복자 이상을 제공하며, 배열 기반 컨테이너인 vector와 deque는 임의 접근 반복자를 제공한다.
알고리즘(Algorithm)
일반적인 용어의 알고리즘은 어떤 문제를 해결하기 위한 수행 절차나 방법을 의미한다. ‘정렬’이라는 문제를 해결하는 방법(알고리즘)은 무수히 많다. 이런 해결 방법의 절차를 알고리즘이라 한다.
STL 알고리즘은 같은 기능을 수행하는 여러 가지 버전으로 오버로딩되며, 약 100개의 정의가 되어 있다. STL 알고리즘은 일곱가지 범주로 분류된다.
- 원소를 수정하지 않는 알고리즘(nonmodifying algorithms)
- 원소를 수정하는 알고리즘(modifying algorithms)
- 제거 알고리즘(removing algorithms)
- 변경 알고리즘(mutating algorithms)
- 정렬 알고리즘(sorting algorithms)
- 정렬된 범위 알고리즘(sorted range algorithms)
- 수치 알고리즘(numeric algorithms)
함수 객체(Function Object)
STL에서 함수 객체는 클라이언트가 정의한 동작을 다른 구성 요소에 반영하려 할 때 사용된다.
많은 STL알고리즘이 함수 객체, 함수, 함수 포인터 등의 함수류를 인자로 받아 알고리즘을 유연하게 동작시킨다.
어댑터 (Adaptor)
어댑터는 구성 요소의 인터페이스를 변경한다.
STL의 어댑터
- 컨테이너 어댑터(container adaptor): stack, queue, priority_qeueu
- 반복자 어댑터(iterator adaptor): reverse_iterator, back_insert_iterator, front_insert_iterator, insert_iterator
- 함수 어댑터(function adaptor): 바인더(binder), 부정자(negator), 함수 포인터 어댑터(adaptor for pointers to functions)
컨테이너 어댑터의 대표적인 예시는 stack이다.
stack 컨테이너 어댑터는 일반 컨테이너를 LIFO방식의 스택(stack) 컨테이너로 변환한다. emtpy, size, push_back, pop_back, back 인터페이스(멤버 함수)를 지원하는 컨테이너는 모두 stack컨테이너 어댑터를 사용하여 LIFO방식의 스택으로 변환이 가능하다. stack컨테이너 어댑터의 디폴트 컨테이너는 deque컨테이너이다.
할당기(Allocator)
할당기는 컨테이너의 메모리 할당 정보와 정책(메모리 할당 모델)을 캡슐화한 STL 구성 요소이다.
할당기는 템플릿 클래스이며 모든 컨테이너는 기본 할당기는 사용한다.
STL의 할당기는 사용자가 직접 할당기를 정의하고 사용할 수 있다. 다중 스레드에 최적화되고 안전한 사용자 메모리 할당 모델이 필요한 경우 사용 된다. 하지만 대부분의 프로그램에서는 STL에서 제공하는 기본 할당기만으로 충분하다.
모든 컨테이너는 템플릿 매개변수에 할당기를 인자로 받는다.
기본 할당기는 allocator<T>이며 컨테이너는 템플릿 매개변수에 디폴트 매개변수 값으로 기본 할당기를 지정한다.
ex) vector<typename T, typename Alloc = allocator<T>>
Uploaded by
N2T