[C++] STL - C++ 표준 템플릿 라이브러리

정의

C++ STL은 Standard Template Library의 약자로, C++ 표준 라이브러리의 일부입니다.

STL은 다양한 유형의 알고리즘과 데이터 구조를 제공하며, 이들은 모두 템플릿으로 제공되어 다양한 데이터 타입에 대해 동작할 수 있습니다.

 

종류

STL은 크게 컨테이너, 알고리즘, 반복자, 함수 객체(함수자)의 네 가지 구성 요소로 나눌 수 있습니다.

 

컨테이너 (Container)

컨테이너는 자료를 저장하는 클래스 템플릿들의 집합이며 연속 컨테이너, 정렬 연관 컨테이너, 비정렬 연관 컨테이너, 컨테이너 어댑터로 나눌 수 있습니다.

 

연속 컨테이너 (= 시퀀스 컨테이너, Sequence Containers)

연속 컨테이너는 데이터를 순차적으로 저장합니다. 이들은 배열과 비슷한 형태를 가지며, 내부의 요소들은 특정 순서에 따라 배치됩니다.

 

> vector, list, forward_list, deque, array, string

vector : 동적 배열을 구현한 컨테이너
list :  이중 연결 리스트를 구현한 컨테이너
forward_list : 단일 연결 리스트를 구현한 컨테이너
deque : 양쪽 끝에서 삽입/삭제가 가능한 동적배열
array : C++11 부터 추가되어 고정 크기의 배열을 나타내는 컨테이너
string : 문자열을 나타내는 특수한 시퀀스 컨테이너로, 문자열 처리 기능뿐만 아니라 일련의 문자에 대해 벡터와 유사하게 동작

 

연관 컨테이너 (Associative Containers)

연관 컨테이너는 키-값(key-value) 쌍을 저장합니다.

정렬 연관 컨테이너는 일반적으로 빠른 검색을 위해 내부적으로 정렬된 상태를 유지하고, 비정렬 연관 컨테이너는 내부적인 정렬 없이 키-값 쌍을 저장합니다.

 

정렬 연관 컨테이너
> set, multiset, map, multimap

set : 중복 없는 요소 집합을 저장하는 컨테이너, 요소들은 키와 동일하며, 키에 따라 자동으로 정렬
multiset : set과 유사하지만, 중복 요소를 허용
map : key-value 쌍을 저장하는 컨테이너, 각 키는 고유한 값을 가지고, 키에 따라 자동으로 정렬
multimap : map과 유사하지만, 동일한 키를 가진 여러 value를 허용

 

위와 같은 정렬 연관 컨테이너들(set, multiset, map, multimap)은 균형 이진 탐색 트리인 "Red-Black Tree"를 사용하여 데이터를 저장합니다. 그로인해 데이터를 삽입/삭제할 때마다 자동으로 재균형화(rebalancing)가 일어나서 효율적인 검색 성능을 유지합니다.

 

비정렬 연관 컨테이너
> unordered_set, unordered_ multiset, unordered_ map, unordered_ multimap

각 컨테이너의 기능은 정렬 연관 컨테이너와 동일합니다. 다만, 자동 정렬되지 않는다는 차이점이 있습니다.

 

위와 같은 비정렬 연관 컨테이너들(unordered_set, unordered_multiset, unordered_map, unordered_multimap)은 해시 함수 기반의 "해시 테이블" 구조를 사용하여 데이터를 저장합니다. 그로인해 평균적으로 O(1)의 검색 속도를 제공하며 최악의 경우에도 O(n)의 시간복잡도를가져 빠른 검색 성능을 제공합니다.

 

(반면, 정렬 연관 컨테이너는 레드블랙 트리를 사용하여 데이터를 저장하기 때문에 검색 시 O(log n)의 시간복잡도를 갖습니다.)

 

컨테이너 어댑터 (Container Adapters)

컨테이너 어댑터는 기존 STL 컨테이너에 특정한 인터페이스나 동작을 추가하여, 새로운 형태의 컨테이너로 만든것입니다. 이들은 기본적으로 다른 STL 컨테이너를 내부적으로 사용하며, 그 위에 추가적인 기능을 제공합니다.

 

> stack, queue, priority_queue

stack : 스택 자료구조를 구현한 컨테이너, 일반적으로 deque 또는 list와 같은 컨테이너로 구축
queue : 큐 자료구조를 구현한 컨테이너, 일반적으로 deque 또는 list와 같은 컨테이너로 구축
priority_queue : 우선순위 큐 자료구조를 구현한 컨테이너, 일반적으로 vector와 함께 make_heap, push_heap, pop_heap 등의 알고리즘이 사용되어 구축

---

알고리즘 (Algorithm)

STL 알고리즘은 주로 컨테이너의 요소에 대해 수행할 수 있는 일련의 연산을 정의합니다.

이러한 알고리즘에는 정렬(sort), 검색(find), 복사(copy), 변환(transform) 등이 포함됩니다.

STL 알고리즘이 특별한 이유 중 하나는 그것들이 일반화되어 있어서 어떤 종류의 컨테이너에도 적용할 수 있다는 점입니다.

 

반복자 (Iterator)

반복자는 포인터와 유사하게 작동하는 객체로, 컨테이너 내부의 개별 요소를 가리킵니다.

반복자를 사용하면 컨테이너의 시작부터 끝까지 요소에 순차적으로 접근할 수 있습니다. 

더 나아가, 5가지 종류의 반복자(입력, 출력, 전진, 양방향 및 임의 접근 반복자)가 있으며 이들은 서로 다른 연산을 지원합니다.

 

입력 반복자 - input iterators : 순차적으로 한 번만 읽을 수 있는 가장 기본적인 반복자
출력 반복자 - output iterators : 입력 반복자와 마찬가지로 순차적으로 한 번만 사용할 수 있지만, 데이터를 쓰는 데 사용
전진 반복자 - forward iterators : 입력과 출력 능력을 모두 갖추고 있으며, 동일한 시퀀스를 여러 번 통과
양방향 반복자 - bidirectional iterators : 양방향은 전진 방식뿐 아니라 역방향으로도 이동할 수 있는 기능
임의 접근 반복자 - random access iterators : 임의 접근은 어떤 위치로든 직접 점프하는 것이 가능하여 가장 강력한 종류의 반복기

 

함수 객체 (Function Objects)

함수 객체 또는 펑터(functor)라고도 하는 함수 객체는 호출 가능한 클래스입니다.

즉, 클래스 인스턴스를 함수처럼 호출할 수 있습니다(operator() 오버로딩).

함수 객체는 일반 함수보다 유연성이 높아서 많은 경우에서 사용됩니다.

---

 

위 예제에서 std::find_if는 STL 알고리즘, nums.begin(), nums.end()는 반복자, IsEven은 함수 객체로 사용되고 있습니다.

---

https://ko.wikipedia.org/wiki/%ED%91%9C%EC%A4%80_%ED%85%9C%ED%94%8C%EB%A6%BF_%EB%9D%BC%EC%9D%B4%EB%B8%8C%EB%9F%AC%EB%A6%AC

표준 템플릿 라이브러리 - 위키백과, 우리 모두의 백과사전