[C++] C++ 표준 라이브러리

STL : 표준 템플릿 라이브러리 (Standard Template Library)

• C++를 위한 라이브러리로서 C++ 표준 라이브러리의 많은 부분에 영향을 끼쳤다. 

C++ 표준 라이브러리 (C++ Standard Library)

• C++과 C++ ISO 표준 자체로 쓰여진 클래스들과 함수들의 집합이다.
• C++ 표준 라이브러리는 여러 Generic 컨테이너들, 그리고 이러한 컨테이너들과 함수 객체, Generic 문자열, stream, 몇몇 언어 특징 그리고 power 연산 같은 작업을 위한 함수들을 제공한다.
• C++ 표준 라이브러리의 특징은 namespace 내에 선언된다는 것이다. (.h 헤더가 아님)
• C++ 표준 라이브러리와 STL이 많은 특징들을 공유하지만, 둘 중 어느것도 다른 하나의 상위 집합은 아니다.

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로 삽입 시점부터 정렬된 상태로 저장된다.
삽입/검색/삭제 O(log n). set의 경우는 정렬 시 사용되는 값이 유일해야 하며, multiset의 경우는 그렇지 않고, 같은 값인 경우 삽입된 순서가 유지된다.
map/multimap : set과 거의 비슷하나 그냥 객체만 저장하는 것이 아니라 정렬이 가능한 key와 그 key가 가리키는 객체의 pair로 저장된다. 
map은 key가 유일해야 하며, multimap의 경우는 그렇지 않고, 같은 경우 삽입된 순서가 유지된다.

stack/queue/priority_queue : 위의 컨테이너들을 이용하여 스택, 큐, 우선순위 큐를 위한 인터페이스를 제공한다. 컨테이너 어댑터에 속하며 컨테이너는 아니다.

 

반복자 : 컨테이너의 원소를 순회하는 방법을 추상화한 객체들.

각 컨테이너마다 상수시간 내에 처리 가능한 반복자(효율성에 저하를 주지 않는 반복자)들을 만들어 둠으로써, Generic 프로그래밍을 효과적으로 구현하고 있다. 일례로 Vector의 경우는 임의 접근 반복자를 지원하지만 List의 경우는 지원하지 않는다.

forward_iterator
reverse_iterator
insert_iterator
input_iterator_tag
output_iterator_tag
bidirectional_iterator
random_iterator

 

알고리즘 : 반복자로 지정되는 자료의 집합에 대한 작업을 정의해놓은 템플릿 함수.

for_each
transform
generate
find
binary_search
stable_sort
sort