STL 알고리즘

1. 유틸리티 알고리즘

min(), max() : 주어진 두 값 중에서 작은 값, 또는 큰 값을 리턴한다. C++11에서는 두 개 이상의 값을 함수 인자로 사용할 수 있다.

minmax() : 주어진 2개 이상의 값 중 최소값과 최대값을 pair 타입 쌍으로 리턴한다.

swap() : 주어진 두 변수의 값을 교환한다.

2. 불변 알고리즘

항목의 나열을 대상으로 하여 항목의 어떤 정보를 리턴하거나 항목마다 특정 함수를 실행한다.

● 검색 알고리즘 - C++11

알고리즘	개요	정렬된 상태	복잡도
find()  find_if()	주어진 값과 같거나  주어진 조건이 true가 되는 첫 번째 항목을 찾는다.	불필요	선형
find_if_not()	주어진 조건이 false가 되는 첫 번째 항목을 찾는다.	불필요	선형
find_first_of()	find()와 같으나 동시에 여러 항목을 찾는다.	불필요	이차함수
adjacent_find()	주어진 값이 조건에 연속적으로 합치되는 인접한 두 항목을 찾는다.	불필요	선형
search()  find_end()	주어진 나열 값 또는  주어진 조건과 합치되는 첫번째 또는 마지막 부분열을 찾는다.	불필요	이차함수
search_n()	주어진 값이나 주어진 조건에 첫 번째로 n번 연속 합치되는 항목을 찾는다.	불필요	선형
lower_bound()  upper_bound()  equal_range()	주어진 범위 값에 합치되는 가장 극단 항목을 찾는다. lower는 시작 항목, upper는 마지막 항목, equal은 양 끝 단 항목을 모두 찾는다.	필요	로그
binary_search()	정렬된 항목열에서 이진 탐색으로 값을 찾는다.	필요	로그
min_element()  max_element()	최소값을 가지는 항목 또는  최대값을 가지는 항목을 찾는다.	불필요	선형
minmax_element()	최소값 항목과 최대값 항목을 pair 타입 쌍으로 찾아서 리턴한다.	불필요	선형
all_of()	항목 열이 비어있거나 주어진 조건을 모든 항목이 만족하면 true, 아니면 false를 리턴한다.	불필요	선형
any_of()	항목 열이 비어있거나 주어진 조건을 모든 항목이 만족 시키지 못하면 false, 아니면 true를 리턴한다.	불필요	선형
none_of()	항목 열이 비어있거나 주어진 조건을 모든 항목이 만족시키지 못하면 true, 아니면 false를 리턴한다.	불필요	선형
partition_point()	주어진 조건에 맞는 항목과 맞지 않는 항목을 양쪽으로 나누어 그 경계를 인덱스로 가진 반복자를 리턴한다.	불필요	로그

● 수치 연산 알고리즘 - C++11

알고리즘	개요
count()  count_if()	주어진 값 또는 주어진 조건에 합치되는 항목의 개수를 헤아린다.
accumulate()	항목 열의 모든 값을 누적한다. 디폴트 동작은 모든 항목에 대한 덧셈이나, 함수 호출 측에서 다른 이항 함수를 지정할 수도 있다.
inner_product()	두 열 각각에서 하나씩 병렬적으로 취한 항목 쌍을 대상으로 이항 함수를 호출한 다음 그 결과 값을 또 다른 이항 함수를 통해 누적한다.
partial_sum()	주어진 범위의 부분 열 a0, a1, a2..에 대해서 a0, a0+a1, a1+a2.. 의 결과 열로 출력한다. 디폴트인 덧셈 외에 다른 이항 함수도 가능하다.
adjacent_difference()	주어진 범위의 부분 열 a0,a1,a2..에 대해서 a0, a1-a0, a2-a1.. 의 결과 열로 출력한다. 디폴트인 뺄셈 외에 다른 이항 함수도 가능하다.

● 비교 알고리즘 - C++11

알고리즘	개요
equal()	주어진 두 항목열에서 병렬적으로 동일 순서 위치의 각 항목쌍이 모두 값이 같거나 주어진 조건에 합치하는지 검사한다.
mismatch()	주어진 두 항목열에서 병렬적으로 동일 순서 위치의 각 항목쌍 중 값이 일치하지 않는 첫 번째 위치를 리턴한다.
lexicographical_compare()	두 항목열에서 병렬적으로 동일 순서 위치의 각 항목쌍을 시점 시작 지점부터 차례대로 비교하여 서로 값이 다른 항목쌍이 있을 때, 두 값의 사전적 순서를 결과로 리턴한다.

● 작업 알고리즘 - C++11

알고리즘	개요
for_each()	항목열의 항목마다 특정 함수를 실행한다.

● 변경 알고리즘 - C++11

알고리즘	개요
transform()	한 개의 항목열에 대하여 항목마다 일할 함수를 호출하거나, 두 개의 항목열의 병렬적인 항목 쌍에 대해 이항 함수를 호출한다.
copy(), copy_backward()	원본 항목열에서 대상 항목열로 항목들을 복제한다.
iota()	순차적으로 주어진 값을 각 항목에 대입하되, 한 번 대입할 때마다 값을 증가시킨다
copy_if()	주어진 조건에 대해 참인 항목을 다른 항목열로 복제한다.
copy_n()	n개의 행목을 다른 항목열로 복제한다.
partition_copy()	원본 항목열의 각 항목을 주어진 조건의 참/거짓 여부에 따라 분리하여 두 개의 항목열로 만든다.
move()	항목들을 다른 항목열로 이동시킨다.
move_backward()	항목들을 다른 항목열로 이동시키되, 제일 뒤 항목부터 이동한다.
iter_swap()  swap_ranges()	두 항목 또는  두 항목열을 서로 교환한다.
replace()  replace_if()	주어진 값과 같거나  주어진 조건에 합치된느 항목을 새로운 항목으로 바꾼다.
fill()  fill_n()	모든 항목 또는  첫 n개 항목을 새로운 값으로 세팅한다.
generate()  generate_n()	주어진 생성 함수를 모든 항목 또는  첫 n개 항목에 적용하여 생성 함수의 결과 값으로 값을 세팅한다.
remove()  remove_if()	주어진 값과 같거나  주어진 조건에 합치되는 항목을 제거한다.
remove_copy()  remove_copy_all()	주어진 값과 같거나  주어진 조건에 합치되는 항목을 제거함과 동시에 다른 항목열로 복제한다.
unique()  unique_copy()	항목열에서 연속적으로 중복되는 항목을 그 자리에서 제거하거나  중복 항목이 제거된 새로운 항목열로 복제한다.
reverse()  reverse_copy()	항목열의 각 항목의 순서를 그 자리에서 거꾸로 만든거나  새로운 항목열에 거꾸로 된 항목열을 복사한다.
rotate()  rotate_copy()	항목열을 주어진 항목 개수만큼 그 자리에서 회전시키거나  회전된 항목열을 새로운 항목열에 복사한다.
next_permutation()  prev_permutation()	주어진 항목열을, 그 항목들로 생성 가능한 다음 순열 조합 또는  이전 순열 조합에 맞추어 그 자리에서 변환한다.

● 정렬 알고리즘 - C++11

알고리즘	개요	성능
sort()  stable_sort()	원본에서 바로 정렬한다. 동일 항목은 순서가 바뀔 수도 있고 순서가 유지될 수도 있다.	선형X로그
partial_sort()  partial_sort_copy()	항목열의 처음 n개 항목만 정렬한다. 원본에서 정렬할 수도 있고 정렬 결과를 다른 항목열에 복제할 수도 있다.	선형X로그
nth_element()	n번째 항목만 전체 정렬 시 위치할 곳으로 이동시킨다.	선형
merge()  inplace_merge()	두 정렬된 항목열을 새로운 항목열로 복제 병합하거나 둘 중 한 항목열에 바로 병합한다.	선형  선형X로그
make_heap()  is_heap()  is_heap_until()	주어진 원소들을 재배치하여 힙으로 구성한다.	선형
push_heap()  pop_heap()	힙에 요소를 추가하거나  삭제한다.	로그
sort_heap()	힙 요소를 정렬한다.	선형X로그
partition()	주어진 조건에 합치되는 항목들은 앞쪽으로, 불합치 되는 항목들은 뒤쪽으로 옮긴다. 원래 순서가 유지되지 않는다.	선형
stable_partition()	주어진 조건에 합치되는 항목들은 앞쪽으로, 불합치 되는 항목들은 뒤쪽으로 옮긴다. 원래 순서가 유지된다.	선형X로그
random_partition()	항목열의 항목들을 랜덤하게 뒤섞는다.	선형
is_sorted()  is_sorted_until()	항목열 전체 또는  일부분이 정렬된 상태인지 검사한다.	선형

● 집합 알고리즘 - C++11

알고리즘	개요
includes()	어떤 항목이 다른 항목열에 완전히 속하는지 검사한다.
set_union()  set_intersection()  set_difference()  set_symmetric_difference()	두 개의 정렬된 항목열을 대상으로 합집합  교집합  차집합  대칭차집합을 수행하고 그 결과를 다른 항목열에 복제한다.