STL의 알고리즘
- 100여개가 넘는 알고리즘을 가지고 있음
- 대분류로 7가지의 알고리즘으로 분류가능
- 대부분은 algorithm의 헤더에 정의되어 있으나, 수치 관련(7번)은 numeric 헤더에 정의되어 있음
- 원소를 수정하지 않는 알고리즘(nonmodifying algorithms)
- 원소를 수정하는 알고리즘(modifying algorithms)
- 제거 알고리즘(removing algorithms)
- 변경 알고리즘(mutating algorithms)
- 정렬 알고리즘(sorting algorithms)
- 정렬된 범위 알고리즘(sorted range algorithms)
- 수치 알고리즘(numeric algorithms)
원소를 수정하지 않는 알고리즘
p = adjacent_find(b,e) : p는 반복자 구간 [b,e)의 원소 중 *p == *(p+1)인 첫 원소를 가리키는 반복자
p = adjacent_find(b,e,f) : p는 반복자 구간 [b,e)의 원소 중 f(*p == *(p+1))이 참인 첫 원소를 가리키는 반복자
n = count(b,e,x) : n은 반복자 구간 [b,e)의 원소 중 x 원소의 개수
n = count_if(b,e,f) : n은 반복자 구간 [b,e)의 원소 중 f(*p)가 참인 원소의 개수
equal(b,e,b2) : [b, e)와 [b2, b2+(e-b))의 모든 원소가 같은가
equal(b,e,b2,f) : [b, e)와 [b2, b2+(e-b))의 모든 원소에서 f(*p, *q)가 참인가
p = find(b,e,x) : [b,e)에서 x와 같은 첫 원소의 반복자
p = find_end(b,e,b2,e2) : [b,e)에서 [b2, e2)의 순차열과 일치하는 순차열 첫 원소의 반복자, 만약 일치하는 것이 여러개라면 마지막 순차열의 반복자
p = find_end(b,e,b2,e2,f) : [b,e)에서 [b2, e2)의 순차열과 일치하는 순차열 첫 원소의 반복자, 만약 일치하는 것이 여러개라면 마지막 순차열의 반복자, 이 때 비교는 f를 사용
p = find_first_of(b,e,b2,e2) : [b,e)에서 [b2, e2)의 순차열과 일치하는 순차열 첫 원소의 반복자
p = find_first_of(b,e,b2,e2,f) : [b,e)에서 [b2, e2)의 순차열과 일치하는 순차열 첫 원소의 반복자, 비교는 f를 사용
p = find_if(b,e,f) : p는 [b,e)에서 f(*p)가 참인 첫 원소를 가리키는 반복자
f = for_each(b,e,f) : [b, e)에 f(*p)를 적용하고, f를 반환
lexicographical_compare(b,e,b2,e2) : [b, e)의 순차열의 구간이 [b2, e2)의 순차열보다 작다면(less) 참, 아니면 거짓 반환 / 작음은 사전순으로 비교
lexicographical_compare(b,e,b2,e2,f) : [b, e)의 순차열의 구간이 [b2, e2)의 순차열보다 작다면(less) 참, 아니면 거짓 반환 / 작음은 [b,e)의 반복자 p와 [b2,e2) 의 반복자 q에 대해 f(*p, *q)가 참
k = max(a,b) : a,b중 큰것을 반환
k = max(a,b,f) : a,b중 큰것에 f(a,b)를 적용
p = max_element(b,e) : [b,e)의 구간에서 가장 큰 원소의 반복자
p = max_element(b,e,f) : [b,e)의 구간에서 f로 비교를 해 가장 큰 원소의 반복자
k = min(a,b) : a,b중 작은것 반환
k = min(a,b,f) : a,b중 작은것에 f(a,b)를 사용
p = min_element(b,e) : [b,e)의 구간에서 f로 비교를 해 가장 작은 원소의 반복자
p = min_element(b,e,f) : [b,e)의 구간에서 f로 비교를 해 가장 작은 원소의 반복자
pair(p,q) = mismatch(b,e,b2) : (p, q)는 구간 [b,e)와 [b2, b2+(e-b))에서 !(*p == *q)의 첫 원소를 가리키는 반복자의 쌍
pair(p,q) = mismatch(b,e,b2,f) : (p, q)는 구간 [b,e)와 [b2, b2+(e-b))에서 !f(*p,*q)가 참인 첫 원소를 가리키는 반복자의 쌍
p = search(b,e,b2,e2) : p는 [b,e)의 순차열 구간 중, [b2,b2+(e-b))의 순차열과 일치하는 순차열 첫 원소의 반복자
p = search(b,e,b2,e2,f) : p는 [b,e)의 순차열 구간 중, [b2,b2+(e-b))의 순차열과 일치하는 순차열 첫 원소의 반복자 / 이 때 비교는 f를 사용
p = search_n(b,e,n,x) : p는 [b,e)의 원소 중 x값이 n개 연속한 첫 원소의 반복자
p = search_n(b,e,n,f) : p는 [b,e)의 원소 중 f(*p, x)가 참인 값이 연속한 첫 원소의 반복자- 찾기 알고리즘은 원소를 발견하지 못하면 찾는 구간의 끝 반복자를 반환! 즉 e의 위치를 반환함
원소를 수정하는 알고리즘
p = copy(b,e,t) : [b,e)의 모든원소를 [t,p)로 모두 복사
p = copy_backward(b,e,f) : [b,e)의 원소를 마지막 원소로부터 [p,t)로 복사
fill(b,e,x) : [b,e)의 모든 원소를 x로 채움
fill_n(b,n,x) : [b,b+n)의 모든 원소를 x로 채움
f = for_each(b,e,f) : [b,e)에 f(*p) 동작을 적용하고 f를 다시 반환
generate(b,e,f) : [b,e)의 모든 원소를 f()로 채움
generate_n(b,n,f) : [b,b+n)의 모든 원소를 f()로 채움
iter_swap(p,q) : 반복자 p,q가 가리키는 *p, *q의 원소를 바꿈
p = merge(b,e,b2,e2,t) : [b,e) 와 [b2,e2)를 [t,p)로 합병정렬
p = merge(b,e,b2,e2,t,f) : [b,e) 와 [b2,e2)를 [t,p)로 합병정렬 / 비교는 f를 사용
replace(b,e,x,x2) : [b,e)의 원소 중 x를 x2로 수정
replace_it(b,e,f,x2) : [b,e)의 원소 중 f(*p)가 참인 원소를 x2로 수정
p = replace_copy(b,e,t,x,x2) : [b,e)의 원소 중 x를 x2로 수정해서 [t,p)로 복사
p = replace_copy_it(b,e,t,f,x2) : [b,e)의 원소 중 f(*p)가 참인 원소를 x2로 수정하여 [t,p)로 복사
swap(a,b) : a와 b를 swap
swap_ranges(b,e,b2) : [b,e)의 원소와 [b2, b2+(e-b))의 원소를 교환
p = transform(b,e,t,f) : [b,e)의 모든 원소를 f(*p)하여 [t, t+(e-b))에 저장 / p는 저장된 마지막 원소의 반복자(t+(e-b))
p = transform(b,e,b2,t,f) : [b,e)와 [b2, b2+(e-b))의 반복자가 각각 p,q일 때, 모든 원소를 f(*p,*q)하여 [t, t+(e-b))에 저장 / p는 저장된 마지막 원소의 반복자 (t+(e-b))- 순차열을 복사할 때, 덮어쓰기와 삽입이 있음
- 디폴트는 덮어쓰기 모드이지만 반복자 어댑터를 사용하면 삽입모드로 사용가능
제거 알고리즘
p = remove(b,e,x) : [b,e)의 순차열을 x원소가 남지 않도록 덮어쓰기로 이동, 동작 후, 순차열은 [b,p)가 됨
p = remove_if(b,e,f) : [b,e)의 순차열을 f(*p)가 참인 원소가 남지 않도록 덮어쓰기, 순차열은 [b,p)
p = remove_copy(b,e,t,x) : [b,e)의 순차열에서 *p==x가 아닌 원소만 순차열 [t,p)에 복사
p = remove_copy_if(b,e,t,f) : [b,e)의 순차열에서 f(*p)가 참이 아닌 원소만 [t,p)에 복사
p = unique(b,e) : [b,e)의 순차열을 인접한 중복원소가 남지 않게 덮어쓰기, 순차열은 [b,p)
p = unique(b,e,f) : [b,e)의 순차열에서 f(*p)가 참인 원소가 남지 않게 덮어쓰기, 순차열은 [b,p)
p = unique_copy(b,e,t) : [b,e)의 순차열에서 인접한 중복원소가 아닌 원소를 순차열 [t,p)에 복사
p = unique_copy(b,e,t,f) : [b,e)의 순차열에서 f(*p)가 참인 인 인접한 중복 원소가 아닌원소를 순차열 [t,p)에 복사- remove는 실제 원소를 제거하지 않고, 다음 원소를 앞으로 이동
- 실제 size는 감소하지 않음
- 실제로 제거를 하고 싶다면 컨테이너의 erase함수를 사용하면 됨
변경 알고리즘
bool = next_permutation(b,e) : [b,e)의 순차열을 사전순 다음 순열이 되도록 변경, 마지막 순열이라면 false
bool = next_permutation(b,e,f) : [b,e)의 순차열을 비교에 f를 사용하여 변경, 마지막 순열이라면 false
bool = prev_permutation(b,e) : [b,e)의 순차열을 사전순 이전 순열이 되도록 변경, 첫 순열이라면 false
bool = prev_permutation(b,e,f) : [b,e)의 순차열을 비교에 f를 사용하여 변경, 첫 순열이라면 false
p = partition(b,e,f) : [b,e)의 순차열 중 f(*p)가 참인 원소는 [b,p)의 순차열 / 거짓인 원소는 [p,e)의 순차열로 분류
random_shuffle(b,e) : [b,e)의 순차열을 랜덤(기본 랜덤기)으로 뒤섞음
random_shuffle(b,e,f) : [b,e)의 순차열을 f를 랜덤기로 뒤섞음
reverse(b,e) : [b,e)의 순차열을 뒤집음
p = reverse_copy(b,e,t) : [b,e)의 순차열을 뒤집어 [t,p)에 복사
rotate(b,m,e) : [b,e)의 순차열을 왼쪽으로 회전, 첫 원소와 마지막 원소가 연결된 것처럼 모든 원소가 왼쪽으로 (m-b)만큼 이동
p = rotate_copy(b,m,e,t) : [b,e)의 순차열을 왼쪽으로 회전시켜 [t,p)에 복사
stalbe_partition(b,e,f) : partition알고리즘과 같고 원소의 상대적인 순서를 유지정렬 알고리즘
p = partition(b,e,f) : 변경 알고리즘과 동일
stable_partition(b,e,f) : 변경 알고리즘과 동일
make_heap(b,e) : 힙을 생성하여 [b,e)를 힙 구조로 변경
make_heap(b,e,f) : 힙을 생성하여 [b,e)를 힙 구조로 변경하며 f는 조건자 비교
push_heap(b,e) : 힙에 원소를 추가, push_back()과 같이 사용되며 [b,e)를 힙 구조가 되게 변경
push_heap(b,e,f) : 힙에 원소를 추가, push_back()과 같이 사용되며 [b,e)를 힙 구조가 되게 변경, f는 조건자 비교
pop_heap(b,e) : 힙에 원소를 제거, [b,e)의 순차열의 가장 큰 원소(첫 원소)를 제거
pop_heap(b,e,f) : 힙에 원소를 제거, [b,e)의 순차열의 가장 큰 원소(첫 원소)를 제거, f는 조건자 비교
sort_heap(b,e) : 힙을 정렬, [b,e)를 힙 구조를 이용해 정렬
sort_heap(b,e,f) : 힙을 정렬, [b,e)를 힙 구조를 이용해 정렬, f는 조건자 비교
nth_element(b,m,e) : [b,e)의 원소 중 m-b개 만큼 선별된 원소를 [b,m)의 순차열에 놓이게 함
nth_element(b,m,e,f) : [b,e)의 원소 중 m-b개 만큼 선별된 원소를 [b,m)의 순차열에 놓이게 함, f는 조건자 비교
sort(b,e) : [b,e)를 퀵 정렬을 기반으로 정렬
sort(b,e,f) : [b,e)를 퀵 정렬을 기반으로 정렬, f는 조건자 비교
stable_sort(b,e) : [b,e)를 머지 정렬을 기반으로 정렬, [b,e)를 정렬하되 같은 원소의 상대적인 순서를 유지
stable_sort(b,e,f) : [b,e)를 머지 정렬을 기반으로 정렬, [b,e)를 정렬하되 같은 원소의 상대적인 순서를 유지, f를 조건자 비교
partial_sort(b,m,e) : 힙 정렬을 기반으로 정렬, [b,e)의 원소 중 m-b개 만큼의 상위 원소를 정렬하여 [b,m)에 놓음
partial_sort(b,m,e,f) : 힙 정렬을 기반으로 정렬, [b,e)의 원소 중 m-b개 만큼의 상위 원소를 정렬하여 [b,m)에 놓음, f는 조건자 비교
partial_sort_copy(b,e,b2,e2) : 힙 정렬을 기반으로 정렬, [b,e)의 원소 중 e2-b2개의 원소 정도만 정렬하여 [b2,e2)로 복사
partial_sort_copy(b,e,b2,e2,f) : 힙 정렬을 기반으로 정렬, [b,e)의 원소 중 e2-b2개의 원소 정도만 정렬하여 [b2,e2)로 복사, f는 조건자 비교- 자료구조 힙 : 트리 내의 모든 원소가 부모 노드보다 큰값(혹은 작은 값)을 갖는 완전 이진 트리
- 아래가 힙 규칙을 만족하는 트리와 아닌 트리의 그림
정렬된 범위 알고리즘
binary_search(b,e,x) : [b,e)에 x와 같은 원소가 있는가?
binary_search(b,e,x,f) : [b,e)에 x와 같은 원소가 있는가? / f는 조건자 비교
includes(b,e,b2,e2) : [b2,e2)애 [b,e)의 모든 원소가 있는가?
includes(b,e,b2,e2,f) : [b2,e2)애 [b,e)의 모든 원소가 있는가? / f는 조건자 비교
p = lower_bound(b,e,x) : [b,e)에서 x와 같은 첫 원소의 반복자를 p
p = lower_bound(b,e,x,f) : [b,e)에서 x와 같은 첫 원소의 반복자를 p / f는 조건자 비교
p = upper_bound(b,e,x) : [b,e)에서 x보다 큰 원소의 반복자를 p
p = upper_bound(b,e,x,f) : [b,e)에서 x보다 큰 원소의 반복자를 p / f는 조건자 비교
pair(p1,p2) = equal_range(b,e,x) : [p1, p2)의 순차열은 [b,e)의 순차열에서 x와 같은 원소의 구간 (lower_bound(), upper_bound()의 순차열과 같음)
pair(p1,p2) = equal_range(b,e,x,f) : [p1, p2)의 순차열은 [b,e)의 순차열에서 x와 같은 원소의 구간 (lower_bound(), upper_bound()의 순차열과 같음) / f는 조건자 비교
p = merge(b,e,b2,e2,t) : [b,e)와 [b2,e2)를 합병해 [t,p)에 저장
p = merge(b,e,b2,e2,t,f) : [b,e)와 [b2,e2)를 합병해 [t,p)에 저장 / f는 조건자 비교
inplace_merge(b,m,e) : 정렬된 [b,m)과 [m,e)의 순차열을 [b,e)로 합병
inplace_merge(b,m,e,f) : 정렬된 [b,m)과 [m,e)의 순차열을 [b,e)로 합병 / f는 조건자 비교
p = set_union(b,e,b2,e2,t) : [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 합집합으로 [t,p)에 저장
p = set_union(b,e,b2,e2,t,f) : [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 합집합으로 [t,p)에 저장 / f는 조건자 비교
p = set_intersection(b,e,b2,e2,t) : [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 교집합으로 [t,p)에 저장
p = set_intersection(b,e,b2,e2,t,f) : [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 교집합으로 [t,p)에 저장 / f는 조건자 비교
p = set_difference(b,2,b2,e2,t) : [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 차집합으로 [t,p)에 저장
p = set_difference(b,2,b2,e2,t,f) : [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 차집합으로 [t,p)에 저장 / f는 조건자 비교
p = set_symmetric_difference(b,e,b2,e2,t) : [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 대칭 차집합으로 [t,p)에 저장
p = set_symmetric_difference(b,e,b2,e2,t,f) : [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 대칭 차집합으로 [t,p)에 저장 / f는 조건자 비교- binary_search() 알고리즘은 a==b연산을 수행하지 않고, !(a < b) && !(b < a)연산을 사용
수치 알고리즘
x2 = accumulate(b,e,x) : x2는 x를 초깃값으로 시작한 구간 [b,e) 순차열 원소의 합
x2 = accumulate(b,e,x, f) : x2는 x를 초깃값으로 시작한 구간 [b,e) 순차열 원소의 합 / f를 누적에 사용
x2 = inner_product(b,e,b2,x) : x2는 x를 초깃값으로 시작한 [b,e)와 [b2,b2+(e-b))의 내적(두 순차열의 곱의 합)
x2 = inner_product(b,e,b2,x,f1, f2) : x2는 x를 초깃값으로 시작한 [b,e)와 [b2,b2+(e-b))의 모든 원소끼리 f2연산 후, f1 연산으로 총 연산한 결과
p = adjacent_difference(b,e,t) : [b,e)의 인접 원소와의 차를 순차열 [t,p)에 저장
p = adjacent_difference(b,e,t,f) : [b,e)의 인접 원소와의 차를 순차열 [t,p)에 저장 / f를 연산에 사용
p = partial_sum(b,e,t) : [b,e)의 현재 원소까지의 합을 [t,p)에 저장
p = partial_sum(b,e,t,f) : [b,e)의 현재 원소까지의 합을 [t,p)에 저장 / f를 연산에 사용