더북(TheBook)

1.7 | 알고리즘

 

알고리즘은 반복자 쌍으로 지정한 객체의 범위에 적용할 수 있는 계산 함수와 알고리즘 함수로 되어 있다. 반복자 쌍은 범위의 첫 번째 원소를 가리키는 시작 반복자와 마지막 원소에서 하나 더 뒤를 가리키는 끝 반복자로 되어 있다. 알고리즘은 데이터 원소들을 반복자로 접근하기 때문에 알고리즘은 데이터가 저장되는 위치에 관여하지 않는다. 알고리즘별로 필요한 반복자만 있으면 어떤 유형의 순차열에도 알고리즘을 적용할 수 있다. 다시 말해 알고리즘 적용을 컨테이너에 있는 원소, string 객체의 문자, 표준 배열 원소, 스트림에 할 수 있으며 반복자만 지원한다면 직접 구현한 클래스 타입의 컨테이너에 저장된 순차열에도 알고리즘을 적용할 수 있다.

알고리즘은 STL에서 가장 큰 도구 모음이다. 알고리즘에 정의된 상당수 도구는 폭넓게 응용되지만, 일부 도구는 매우 한정된 분야에서만 쓰인다. 알고리즘은 크게 나누면 다음과 같이 분류할 수 있다.

1. 변경 불가 순차열 연산(non-mutating sequence operation)은 대상 순차열의 내용을 변경하지 못한다. 주어진 값과 일치하는 원소를 찾는 알고리즘이 원본 데이터를 변경할 필요는 없다. inner_product()accumulate() 같은 수치 알고리즘은 순차열을 변경하지 않고 순차열만 처리해서 결과를 생성하므로 변경 불가 순차열 연산으로 분류한다. 이 분류에 해당하는 알고리즘에는 find(), count(), mismatch(), search(), equal()이 있다.

2. 변경 가능 순차열 연산(mutating sequence operation)은 순차열의 내용을 변경한다. 이 분류에 해당하는 알고리즘에는 swap(), copy(), transform(), replace(), remove(), reverse(), rotate(), fill(), shuffle()이 있다. 힙 연산도 이 카테고리로 분류한다.

3. 정렬, 병합, 이와 관련된 알고리즘은 순차열의 순서를 변경한다. 이 분류에 속하는 알고리즘에는 sort(), stable_sort(), binary_search(), merge(min(), max()가 있다.

물론, 이 카테고리에 정리한 알고리즘이 이용할 수 있는 알고리즘의 전체 목록은 아니며 이어지는 장에서 더 많이 배우고 어떻게 사용하는지 살펴볼 것이다. transform() 같은 일부 알고리즘에는 범위로 지정한 원소들에 적용할 함수를 인수로 전달해야 한다. 원소들을 빈번하게 재정렬하는 알고리즘에는 원소들을 비교하는 서술어(predicate)를 제공할지 선택할 수 있다. 함수의 인수에 함수를 전달하는 것에 대해 살펴보자.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.