C++ STL(Standard Template Library)

STL은 네 가지의 구성 요소로 이루어진다. 

• Containers(컨테이너)
• Iterators(반복자)
• Algorithms(알고리즘)
• Functions(함수자)

---

1. Containers(컨테이너)

STL 컨테이너는 데이터를 모아서 저장해둘 수 있는 제네릭 데이터 구조다.

컨테이너 클래스	컨테이너 타입	삽입 성능	삭제 성능	접근 성능
vector	시퀀스 컨테이너	끝부분에서 분할 상쇄 상수 시간 \(O(1)\), 임의의 위치 p로의 삽입은 \(O(N-p)\)	끝부분에서 분할 상쇄 상수 시간 \(O(1)\), 임의의 위치 p에서의 삭제는 \(O(N-p)\)	\(O(1)\)
list	시퀀스 컨테이너	\(O(1)\)	\(O(1)\)	\(O(N)\), 확률적으로 \(O(N/2)\)
forward_list	시퀀스 컨테이너	\(O(1)\)	\(O(1)\)	\(O(N)\), 확률적으로 \(O(N/2)\)
deque	시퀀스 컨테이너	시작 또는 끝부분에서는 분할 상쇄 상수 시간 \(O(1)\), 임의의 위치 p로의 삽입은 \(O(min(N-p, p))\)	시작 또는 끝부분에서는 분할 상쇄 상수 시간 \(O(1)\), 임의의 위치 p에서의 삭제는 \(O(min(N-p, p))\)	\(O(1)\)
array	시퀀스 컨테이너	N/A	N/A	\(O(1)\)
queue	컨테이너 어댑터	\(O(1)\)	\(O(1)\)	N/A
priority_queue	컨테이너 어댑터	\(O(log(N))\)	\(O(log(N))\)	N/A
stack	컨테이너 어댑터	\(O(1)\)	\(O(1)\)	N/A
set multiset	정렬된 연관 컨테이너	\(O(log(N))\)	\(O(log(N))\)	\(O(log(N))\)
map multimap	정렬된 연관 컨테이너	\(O(log(N))\)	\(O(log(N))\)	\(O(log(N))\)
unordered_map unordered_multimap	비순차 연관 해시 테이블 컨테이너	평균적으로 \(O(1)\), 최악의 경우 \(O(N)\)	평균적으로 \(O(1)\), 최악의 경우 \(O(N)\)	평균적으로 \(O(1)\), 최악의 경우 \(O(N)\)
unordered_set unordered_multiset	비순차 연관 해시 테이블 컨테이너	평균적으로 \(O(1)\), 최악의 경우 \(O(N)\)	평균적으로 \(O(1)\), 최악의 경우 \(O(N)\)	평균적으로 \(O(1)\), 최악의 경우 \(O(N)\)
bitset	특수 컨테이너	N/A	N/A	\(O(1)\)
pair	간단한 연관 컨테이너. map에 할당된 객체들의 배열은 기본 값으로 'pair' 타입이다.
string	기술적으로 string도 컨테이너로 볼 수 있다.

 

 

2. Iterator(반복자)

STL은 컨테이너의 항목에 범용적인 접근 방법을 제공하기 위해 반복자 패턴을 채용했다. 각 컨테이너는 그 컨테이너만의 반복자를 지원한다. 반복자는 특정 컨테이너의 항목들을 어떻게 순회할지 알고 있는 스마트 포인터이다.

함수 이름	설명
begin() end()	non-const 타입 순방향 반복자를 리턴한다. begin()은 첫 번째 항목을, end()는 마지막 항목 직후 위치를 리턴한다.
cbegin() cend()	const 타입 순방향 반복자를 리턴한다. cbegin()은 첫 번째 항목을, cend()는 마지막 항목 직후 위치를 리턴한다.
rbegin() rend()	non-const 타입 역방향 반복자를 리턴한다. rbegin()은 마지막 항목을, rend()는 첫 번째 항목 위치를 리턴한다.
crbegin() crend()	const 타입 순방향 반복자를 리턴한다. crbegin()은 마지막 항목을, crend()는 첫 번째 항목 위치를 리턴한다.

 

 

3. Algorithms(알고리즘)

알고리즘의 카테고리
불변 알고리즘	변경 순차 알고리즘	작업 알고리즘
교환 알고리즘	분할 알고리즘	정렬 알고리즘
이진 탐색 알고리즘	집합 알고리즘	힙 알고리즘
최대/최소 알고리즘	수치 처리 알고리즘	순열 알고리즘

불변 알고리즘	알고리즘 개요	복잡도(성능)
adjacent_find()	주어진 값이 조건에 연속적으로 합치되는 인접한 두 항목을 찾는다.	선형
find() find_if()	주어진 값과 동일하거나, 주어진 조건이 true가 되는 첫 번째 항목을 찾는다.	선형
find_first_of()	find()와 같으나 동시에 여러 항목을 찾는다.	제곱
find_if_not()	주어진 조건이 false가 되는 첫 번째 항목을 찾는다.	선형
search() find_end()	주어진 나열 값 또는 주어진 조건과 합치되는 첫 번째(search()) 또는 마지막(find_end()) 부분열을 찾는다. 즉, 전체 대상 리스트에서 조건에 맞는 서브 리스트를 찾는다.	제곱
search_n()	주어진 값이나 주어진 조건에 첫 번째로 n번 연속 합치되는 항목들을 찾는다.	선형
equal()	주어진 두 항목열에서 병렬적으로 동일 순서 위치의 항목쌍들이 모두 값이 같거나 주어진 조건에 합치하는지 검사한다.	-
mismatch()	주어진 두 항목열에서 병렬적으로 동일 순서 위치의 항목쌍들 중 값이 일치하지 않는 첫 번째 위치를 리턴한다.	-
lexicographical_compare()	주어진 두 항목열을 사전순에 맞춰 비교한다. 즉, 두 항목열에서 병렬적으로 동일 순서 위치의 항목쌍들을 시작 지점부터 차례대로 비교하여 서로 값이 다른 항목쌍이 있을 때 두 값의 사전적 순서를 결과로 리턴한다.	-
all_of()	항목열이 비어 있거나 주어진 조건을 모든 항목이 만족하면 true를 리턴하고 그 외의 경우에는 false를 리턴한다.	-
any_of()	항목열이 비어 있거나 주어진 조건을 모든 항목이 만족시키지 못하면 false를 리턴하고 그 외의 경우에는 true를 리턴한다.	-
none_of()	항목열이 비어 있거나 주어진 조건을 모든 항목이 만족시키지 못하면 true를 리턴하고 그 외의 경우에는 false를 리턴한다.	-
count() count_if()	주어진 값 또는 주어진 조건에 합치되는 항목의 개수를 센다.	-

변경 순차 알고리즘	알고리즘 개요
copy() copy()_backward()	원본 항목열에서 대상 항목열로 항목들을 복제한다.
copy_if()	주어진 조건에 대해 참인 항목을 다른 항목열로 복제한다.
copy_n()	n개의 항목을 다른 항목열로 복제한다.
fill()	모든 항목을 새로운 값으로 세팅한다.
fill_n()	첫 n개 항목을 새로운 값으로 세팅한다.
generate()	주어진 생성 함수를 모든 항목에 적용하여 생성 함수의 결괏값으로 값을 세팅한다.
generate_n()	주어진 생성 함수를 첫 n개 항목에 적용하여 생성 함수의 결괏값으로 값을 세팅한다.
move() move_backward()	항목들을 다른 항목열로 이동시킨다. 이때 이동 시맨틱을 따른다.
remove() remove_if() remove_copy() remove_copy_if()	주어진 값과 동일하거나 주어진 조건에 합치되는 항목을 제거한다. 또는 동시에 다른 항목열로 복제한다(copy 버전).
replace() replace_if() replace_copy() replace_copy_if()	주어진 값과 동일하거나(replace) 주어진 조건에 합치되는(replace_if) 항목을 새로운 항목으로 모두 바꾼다. 또는 복제된 항목으로 바꾼다(copy 버전).
reverse() reverse_copy()	항목열의 각 항목의 순서를 그 자리에서 거꾸로 만들거나(reverse()), 새로운 항목열에 거꾸로 된 항목열을 복사한다(reverse_copy()).
rotate() rotate_copy()	항목열을 주어진 항목 개수만큼 그 자리에서 회전시키거나(rotate()), 회전된 항목열을 새로운 항목열에 복사한다(예: 1,2,3,4,5, -> +2만큼 회전 -> 3,4,5,1,2).
shuffle() random_shuffle()	항목들의 순서를 무작위로 뒤섞는다. 사용할 난수 생성기의 속성을 조정할 수도 있다. random_shuffle()은 C++14부터 사용 중단 안내되었다.
transform()	한 개 항목열에 대해 각 항목마다 단항 함수를 호출하거나, 두 개 항목열의 병렬적인 항목쌍에 대해 이항 함수를 호출한다.
unique() unique_copy()	항목열에서 연속적으로 중복되는 항목을 그 자리에서 제거하거나(unique()), 중복 항목이 제거된 항목열을 새로운 항목열로 복제한다(unique_copy()).

작업 알고리즘	알고리즘 개요
for_each()	항목열의 각 항목마다 특정 함수를 실행한다. 대상 항목열은 정렬된 상태일 필요가 없고 선형 실행 시간 복잡도를 가진다.

교환 알고리즘	알고리즘 개요
iter_swap() swap_ranges()	두 항목(iter_swap) 또는 두 항목열(swap_ranges)을 서로 교환한다.
swap()	주어진 두 변수의 값을 교환한다. <utility> 헤더 파일에 정의되어 있다.

분할 알고리즘	알고리즘 개요	복잡도(성능)
is_partitioned()	항목을 구분하는 프레디킷(predicate) 함수가 섞임 없이 연속된 true와 연속된 false를 리턴하면 true를 리턴한다.	선형
partition()	프레디킷 함수가 true를 리턴하는 항목을 앞으로 보내고 false를 리턴하는 항목을 뒤로 보낸다. 이때 원래 항목 간 순서는 보존되지 않는다.	선형
stable_partition()	프레디킷 함수가 true를 리턴하는 항목을 앞으로 보내고 false를 리턴하는 항목을 뒤로 보내되 원래의 항목 간 순서가 지켜지도록 한다.	선형로그
partition_copy()	원본 항목열을 두 개의 다른 항목열로 복제한다. 이때 복제되는 항목들은 프레디킷 함수의 true 또는 false 리턴에 의해 결정된다.	선형
partition_point()	주어진 조건에 합치되는 항목을 앞에 두고 불합치되는 항목을 뒤에 두는 반복자를 리턴한다. 다시 말해, 주어진 조건에 맞는 항목과 맞지 않는 항목을 양쪽으로 나누어 그 경계를 인덱스로 가진 반복자를 리턴한다.	로그

정렬 알고리즘	알고리즘 개요	복잡도(성능)
is_sorted() is_sorted_until()	항목열 전체(is_sorted()) 또는 일부분(is_sorted_until())이 정렬된 상태인지 검사한다.	선형
nth_element()	n번째 항목만 전체 정렬 시 위치할 곳으로 이동시킨다. n번째 항목 앞에는 n번째 항목보다 빠른 항목들이, 뒤에는 느린 항목들이 위치하나 정렬된 상태는 아니다.	선형
partial_sort() partial_sort_copy()	항목열의 처음 n개 항목만 정렬하고 나머지는 그대로 둔다. 원본에서 바로 정렬될 수도 있고(partial_sort()), 정렬 결과를 다른 항목열에 복제할 수도 있다(partial_sort_copy()).	선형로그
sort() stable_sort()	원본에서 바로 정렬한다. 동일 항목은 순서가 바뀔 수도 있고(sort()), 순서가 유지될 수도 있다(stable_sort()).	선형로그

이진 탐색 알고리즘	알고리즘 개요
lower_bound() upper_bound() equal_range()	주어진 항목 값을 기준으로 가장 극단 항목을 찾는다. lower_bound()는 시작 항목, upper_bound()는 마지막 항목, equal_bound()는 양 끝단 항목을 찾는다.
binary_search()	정렬된 항목에서 이진 탐색으로 값을 찾는다.

집합 알고리즘	알고리즘 개요	복잡도(성능)
inplace_merge()	두 정렬된 항목열을 둘 중 한 항목열에 바로 병합한다.	선형로그
merge()	두 정렬된 항목열을 새로운 항목열로 복제하면서 병합한다.	선형
includes()	어떤 항목열이 다른 항목열에 완전히 속하는지 검사한다.	선형
set_union() set_intersection() set_difference() set_symmetric_difference()	두 개의 정렬된 항목열을 대상으로 합집합(union()), 교집합(intersection()), 차집합(difference()), 대칭차집합(symmetric_difference())을 수행하고 그 결과를 다른 항목열에 복제한다.	선형

힙 알고리즘	알고리즘 개요	복잡도(성능)
is_heap()	주어진 범위의 항목들이 힙을 만족하는지 검사한다.	선형
is_heap_until()	주어진 범위의 항목들 중에서 힙을 만족하는 가장 큰 부분 범위를 찾는다.	선형
make_heap()	주어진 범위의 항목들을 이용하여 힙을 만든다.	선형
push_heap() pop_heap()	힙에 항목을 추가 또는 삭제한다.	선형로그
sort_heap()	힙을 오름차순으로 정렬된 항목열로 반환한다.	선형로그

최대/최소 알고리즘	알고리즘 개요
min() max()	주어진 2개 이상의 값 중에서 최솟값 또는 최댓값을 리턴한다.
minmax()	주어진 2개 이상의 값 중에서 최솟값과 최댓값을 찾고 그 둘을 묶어서 pair 타입으로 리턴한다.
min_element() max_element()	최솟값 항목(min_element()) 또는 최댓값 항목(max_element())을 찾는다.
minmax_element()	최솟값 항목과 최댓값 항목을 찾고 그 둘을 묶어서 pair 타입으로 리턴한다.

수치 처리 알고리즘	알고리즘 개요
accumulate()	항목열의 모든 값을 누적한다. 디폴트 동작은 모든 항목에 대한 덧셈이지만, 함수 호출 측에서 다른 종류의 이항 항수(binary function, 인자가 두 개인 함수)를 지정할 수도 있다.
adjacent_difference()	주어진 범위의 부분열 \(a_0, a_1, ..., a_N\)에 대해 \(a_0, a_1-a_0, a_2-a_1, ..., a_N-a_{N-1}\)을 결과열로 출력한다. 마찬가지로 디폴트인 뺄셈 대신 다른 이항 함수를 지정할 수도 있다.
inner_product()	accumulate()와 유사하나 두 개의 항목열을 대상으로 하는 것이 다르다. 두 열 각각에서 하나씩 병렬적으로 취한 항목 쌍을 대상으로 이항 함수(디폴트는 곱셈)를 호출한 다음 그 결괏값을 또 다른 이상 함수를 통해 누적(디폴트는 덧셈)한다. 만약 두 열이 수학의 벡터를 의미할 경우 전체 결괏값은 벡터의 내적과 동일하다.
itoa()	주어진 초깃값을 각 항목에 대입하되 순차적으로 대입할 때마다 값을 증가시킨다.
partial_sum()	주어진 범위의 부분열 \(a_0, a_1, ..., a_N\)에 대해 \(a_0, a_0+a_1, a_0+a_1+a_2, ..., a_0+\cdots+a_N\)을 결과열로 출력한다. 이때 디폴트인 덧셈 대신 다른 이항 함수를 지정할 수도 있다.

순열 알고리즘	알고리즘 개요	복잡도(성능)
is_permutation()	항목열이 다른 항목열의 순열이면 true를 리턴한다.	제곱
next_permutation() prev_permutation()	주어진 항목열을 사전순에 따라서, 그 항목들로 생성 가능한 다음 순열 조합(next_permutation()) 또는 이전 순열 조합(prev_permutation())에 맞추어 항목열의 순서를 변환한다(예를 들어 1, 2, 3은 3!개의 순열 조합 경우의 수가 있고, 1, 2, 3 다음의 순열 조합은 1, 3, 2가 될 수 있다). 올바르게 정렬된 상태에서 연속해서 next_permutation과 prev_permutation을 호출하면 모든 가능한 순열은 완전 탐색할 수 있다. 더 이상 탐색할 조합이 없으면 false를 리턴한다.	선형

 

4. Functions(함수자)

1. 람다 표현식

람다 표현식 문법

제네릭 람다 표현식

람다 캡처 표현식

리턴 타입으로서의 람다 표현식

파라미터로서의 람다 표현식

 

2. 함수 객체

산술 함수 객체

비교 함수 객체

논리 함수 객체

비트 연산 함수 객체

함수 객체 어댑터- 바인더, 부정 연산, 멤버 함수의 호출