[C++] 제네릭 알고리즘 모음

제네릭 알고리즘

표준 라이브러리에서 제공하는 알고리즘은 함수 템플릿으로 구현돼 있어서 다양한 타입의 컨테이네에 적용할 수 있다.
여기서 제네릭 알고리즘을 곧바로 컨테이너에 적용할 수 없다는 점에 주의한다. 대부분 반복자(이터레이터iterator)라 부르는 중간 매체를 거친다. 

※ 이터레이터 <iterator>

begin( ), end( )	첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 non-const 반복자를 리턴한다.
cbegin( ), cend( )	첫 번째 원소부터 마지막 항목의 바로 다음 원소까지 순차적으로(정방향으로) 탐색하는 const 반복자를 리턴한다.
rbegin( ), rend( )	마지막 원소부터 첫 번째 항목의 바로 다음 원소까지 순차적으로(역방향으로) 탐색하는 non-const 반복자를 리턴한다.
crbegin( ), crend( )	마지막 원소부터 첫 번째 항목의 바로 다음 원소까지 순차적으로(역방향으로) 탐색하는 const 반복자를 리턴한다.

※ 탐색 알고리즘

adjacent_find( )
find( ), find_if( )	조건으로 입력한 값과 같거나 조건식의 결과가 true인 원소 중 첫 번째 원소를 찾는다.
find_first_of( )	find()와 비슷하지만 여러 원소를 동시에 찾는다.
find_if_not( )	조건식의 결과가 false인 원소 중 첫번째 원소를 찾는다.
find_end( )	입력한 시퀀스나 조건식에 맞는 시퀀스 중에서 마지막 부분을 찾는다.
search( )	입력한 시퀀스와 일치하거나 입력한 조건식을 기존으로 같다고 판단되는 시퀀스 중에서 첫 번째 항목을 찾는다.
search_n( )	입력한 값과 같거나 입력한 조건식을 기준으로 같다고 판단되는 원소 중 n번 연속해서 일치하는 결과 중 첫 번째 결과를 찾는다.

※ 비교 알고리즘

equal( )	입력한 두 시퀀스가 서로 같거나, 입력한 조건식을 모두 만족하는지 검사한다.
mismatch( )	입력한 시퀀스와 일치하지 않는 지점의 첫 번째 원소를 리턴한다.
lexicographical_compare( )	입력한 두 시퀀스를 사전 나열 순서대로 비교한다. 이 알고리즘은 첫 번째 인수와 두 번째 인수로 입력한 시퀀스의 모든 항목을 하나씩 비교한다. 각 원소를 비교할 때마다 어느 하나가 사전 순으로 더 작다고 판단되면 그 시퀀스가 먼저다. 두 원소가 같으면 그 다음 번째의 원소를 비교한다.

※ 집계 알고리즘

all_of( )	입력 시퀀스에 있는 모든 원소에 대해 조건식이 true를 리턴하거나 입력 시퀀스가 공백이면 true를 리턴한다. 나머지는 false를 리턴한다.
any_of( )	입력 시퀀스에 있는 원소 중 최소 하나에 대해 조건식이 true를 리턴하면 true를 리턴한다. 나머지는 false를 리턴한다.
none_of( )	입력 시퀀스에 있는 모든 원소에 대해 조건식이 fasle를 리턴하거나 입력 시퀀스가 공백이면 truef르 리턴한다. 나머지는 false를 리턴한다.
count( ) count_if( )	입력한 값을 일치하는 원소나 입력한 조건식의 결과가 true가 되는 원소 수를 센다.

※ 가변형 순차 알고리즘

copy( ) copy_backward( )	원본 시퀀스를 대상 시퀀스로 복제한다.
copy_if ( )	원본 시퀀스에서 조건식이 true를 리턴하는 원소를 대상 시퀀스로 복제한다.
copy_n( )	원본 시퀀스에서 n개 원소를 대상 시퀀스로 복제한다.
fill( )	시퀀스의 원소를 모두 새 값으로 설정한다.
fill_n( )	시퀀스에서 n개 원소를 새 값으로 설정한다.
generate ( )	지정한 함수를 호출해서 시퀀스의 원소를 채울 새 값을 생성한다.
generate_n ( )	지정한 함수를 호출해서 시퀀스의 앞부터 n개 원소에 채울 새 값을 생성한다.
move ( ) move_backward ( )	원본 시퀀스의 원소를 대상 시퀀스로 옮긴다. 효율적으로 옮기도록 이동 의미론을 적용한다.
remove ( ) remove_if ( ) remove_copy ( ) remove_copy_if ( )	지정한 값과 일치하거나 지정한 조건식이 true가 되는 원소를 바로 그 자리에서 삭제하거나 다른 시퀀스로 복제해서 삭제한다.
replace ( ) replace_if ( ) replace_copy ( ) replace_copy_if ( )	지정한 값과 일치하거나 지정한 조건이 true가 되는 원소를 모두 그 자리에서 새 원소로 교체하거나 다른 시퀀스로 복제해서 교체한다.
reverse ( ) reverse_copy ( )	원본 시퀀스에 나열된 원소의 순서를 그 자리에서 반대로 바꾸거나 다른 시퀀스에 복제해서 바꾼다.
rotate ( ) rotate_copy ( )	주어진 시퀀스를 두 개로 나눠서 앞부분과 뒷부분의 위치를 그 자리에서 바꾸거나 결과를 다른 시퀀스에 복제한다. 이때 두 시퀀스의 길이는 서로 달라도 된다.
transform ( )	주어진 시퀀스의 각 원소에 대한 단항 함수를 호출하거나 두 시퀀스에서 위치가 같은 원소에 대해 이항 함수를 호출한다.변환은 그 자리에서 수행한다.
unique ( ) unique_copy ( )	주어진 시퀀스에서 연속적으로 중복되는 항목을 그 자리에서 제거하거나 다른 시퀀스로 복제해서 제거한다.
sample ( )	주어진 시퀀스에서 n개 원소를 무작위로 선택하낟.
shuffle ( ) random_shuffle ( )	주어진 시퀀스에 담긴 원소의 순서를 무작위로 바꾼다. 이때 사용할 무작위수 생성지를 직접 지정할 수 있다. random_shuffle( )은 C++14부터 폐기됐고, C++17부터 완전히 삭제됐다.

※ 작업 알고리즘

for_each ( )	주어진 시퀀스에 담긴 원소마다 함수를 실행한다. 시퀀스는 시작 반복자와 끝 반복자로 지정한다.
for_each_n ( )	주어진 시퀀스에서 첫 n개 원소만 처리한다. 시퀀스는 시작 반복자와 원소 수(n)로 지정한다.

※ 교환 알고리즘

iter_swap ( ) swap_ranges ( )	두 원소 또는 시퀀스를 맞바꾼다.
swap ( )	두 값을 맞바꾼다<utility> 헤더 파일에 정의돼 있다.
exchange ( )	지정한 값을 새 값으로 교체하고 기존 값을 리턴한다. <utility>헤더 파일에 정의돼 있다.

※ 분할 알고리즘

is_partitioned ( )	조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있다면 true를 리턴한다.
partition ( )	조건식이 true가 되는 원소가 모두 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지하지 않는다.
stable_partition ( )	조건식이 true가 되는 원소가 모드 조건식이 false가 되는 원소보다 앞에 있도록 시퀀스를 정렬한다. 각 파티션의 원소는 원본 순서를 유지한다.
partition_copy ( )	원본 시퀀스에 있는 원소를 서로 다른 두 시퀀스로 복제한다. 대산 시퀀스는 조건식의 결과가 true인지 false인지에 따라 결정한다.
partition_point ( )	반복자 앞에 나온 원소가 모두 조건식에 대해 true가 되고, 반복자 뒤에 나온 원소가 모두 조건식에 대해 false가 되는 반복자를 리턴한다.

※ 정렬 알고리즘

is_sorted ( ) is_sorted_until ( )

nth_element ( )

partial_sort ( ) partial_sort_copy ( )

sort ( ) stable_sort ( )

※ 이진 탐색 알고리즘

lower_bound ( )	주어진 값보다 작지 않은(크거나 같은) 첫번째 원소를 시퀀스에서 찾는다.
upper_bound ( )	주어진 값보다 큰 첫 번째 원소를 시퀀스에서 찾는다.
equal_bound ( )	lower_bound( )와 upper_bound( )의 결과를 모두 담은 pair를 리턴한다.
binary_search ( )	지정한 값이 시퀀스에 있으면 true, 아니면 false를 리턴한다.

※ 수치 연산 알고리즘 <numeric>

iota ( )	시퀀스를 주어진 값에서 시작해서 연속적으로 증가하는 값으로 채운다.
gcd ( )
lcm ( )
adjacent_difference ( )
partial_sum ( )	주어진 시퀀스의 인접한 두 원소를 골라서 뒤쪽 원소에서 앞쪽 원소를 뺀 결과가 원소가 되는 시퀀스를 생성한다.
exclusive_scan ( ) inclusive_scan ( )	기본 기능은 partial_sum( )과 같지만 inclusive_scan( )은 주어진 합 연산이 결합법직을 만족할때만 partial_sum( )과 같다. 그런데 inclusive_sum( )을 더하는 순서는 일정하지 않은 반면 partial_sum은 항상 왼쪽에서 오른쪽 순서로 더한다. 따라서 결합법칙을 만족하지 않는 합 연산을 적용하면 결과가 일정하지 않다. exclusive_scan ( ) 알고리즘도 합 연산의 순서가 일정하지 않다.  inclusive_scan( )을 수행할때 i 번째 원소는 i번째 합에 포함된다. 이는 partial_sum( )과 같다. 반면 exclusive_scan( )에서는 i번째 원소가 i번째 합에 포함되지 않는다.
transform_exclusive_scan ( ) transform_inclusive_scan ( )	주어진 시퀀스의 각 원소마다 변환을 적용한 다음 exclusive_scan( )또는 inclusive_scan( )를 적용한다.
accumulate ( )	주어진 시퀀스의 모든 원솟값을 누적한다. 기본적으로 원소의 합을 구하지만, 얼마든지 다른 이항 함수를 지정할 수 있다.
inner_product ( )
reduce ( )
tranform_reduce ( )	주어진 시퀀스에 있는 각 원소를 변환한 다음 reduce( )를 수행한다.

※ 순열(permutation) 알고리즘

- is_permutation ( )
- next_permutation ( )
- prev_permutation ( )

※ 추가 알고리즘 

accumulate ( )	<numeric>에 정의 됨.  가장 기본적인 사용법은 지정한 범위에 있는 원소의 합을 구하는 것이다.  알고리즘은 합에 대한 초깃값을 세 번째 매개변수로 받는다.
function ( )

 

※ 출처: 전문가를 위한 C++(개정4판)