[C++] STL - 변경 알고리즘 함수 (copy, swap, transform, next_permutation)

변경 알고리즘 함수는 컨테이너를 변경하지 않으며, 컨테이너의 지정된 범위에서 요소의 값만을 변경할 수 있는 함수이다. STL에서 제공하는 대표적인 변경 알고리즘 함수에는 copy(), swap(), transform()이 있다.

 

copy()

#include <algorithm>

template <class InputIt, class OutputIt>
OutputIt copy(InputIt first, InputIt last, OutputIt d_first);

first부터 last 전까지의 모든 원소들을 d_first부터 시작하는 곳에 복사한다. 

 

swap(), swap_range()

#include <algorithm>

template <class T>
void swap (T& a, T& b)

swap의 경우 해당 변수에 있는 값들을 서로 바꿔주는 역할을 한다.

#include <algorithm>

template< class ForwardIt1, class ForwardIt2 >
ForwardIt2 swap_ranges( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );

swap_ranges는 특정 범위의 값들을 다른 연속된 메모리 공간의 값들과 바꾸어 주는 역할을 한다.

first부터 last 전까지의 원소들을 first2부터 시작하는 곳에 복사한다.

 

transform()

#include <algorithm>

template <class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first, UnaryOperation unary_op);  // (1)

template <class InputIt1, class InputIt2, class OutputIt, class BinaryOperation>
OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2, OutputIt d_first, BinaryOperation binary_op);  // (2)

범위 내의 원소들 각각에 대해 인자로 전달할 함수를 실행한 후, 그 결과를 d_first에서부터 쭉 기록한다.

 

for_each 함수와 하는 일이 거의 동일한데, 다른 점은

• for_each의 경우 원소를 수정하지 않는다. 함수의 리턴값 역시 무시된다.
• transform의 경우 원소를 수정하게 된다. 함수의 리턴값으로 해당 원소가 바뀐다.

 

next_permutation()

#include <algorithm>

template< class BidirIt > bool next_permutation( BidirIt first, BidirIt last );
template< class BidirIt, class Compare > bool next_permutation( BidirIt first, BidirIt last, Compare comp );

해당 컨테이너에 다음 순열이 존재한다면 그 컨테이너의 원소를 해당 순열 순서로 바꾸고 true를 반환하고, 다음 순열이 없다면 false를 반환한다. 

next_permutation을 사용할 때 주의할 점은

1. 오름차순으로 정렬된 값을 가진 컨테이너로만 사용가능하다.
2. defalt로 <를 사용해 순열을 생성한다. 즉 오름차순으로 순열을 생성한다.
3. 중복이 있는 원소들은 중복을 제외하고 순열을 만든다.

 

※ 순열을 이용한 조합 구하기

조합에서는 원소 r개를 뽑기만 하면 되기 때문에 순서가 중요하지 않다.

배열 s의 n개의 원소 중에서 r개의 원소를 택하는 방법은 다음과 같다.

1. 크기가 n인 배열 temp를 만들어 r개의 원소는 1로, (n - r)개의 원소는 0으로 초기화한다.
2. temp의 모든 순열을 구한다.
3. temp의 순열에서 원소값이 1인 인덱스만 배열 s에서 가져온다.

temp에서 1이 있는 자리의 원소는 포함하고 0이 있는 자리의 원소는 미포함하는 것이다.

next_permutation을 사용하면 오름차순으로 정렬되기 때문에, 조합은 내림차순으로 출력된다. 하지만 prev_permutation을 쓰면 모든 조합의 경우의 수를 오름차순으로 출력할 수 있다.