20. STL 알고리즘(STL Algorithm)

1. 키워드

STL 알고리즘(STL Algorithm)
함수 객체(Function Object)
functional 헤더 파일
읽기 알고리즘과 algorithm 헤더 파일
find()과 for_each() 함수
변경 알고리즘과 algorithm 헤더 파일
copy(), swap(), transform() 함수
정렬 알고리즘과 algorithm 헤더 파일
sort(), stable_sort(), binary_search()
수치 알고리즘과 numeric 헤더 파일
accumulate() 함수

2. 함수 객체

STL 알고리즘에 데이터를 전달하기 위해서는 다음과 같은 방법을 사용할 수 있다.

1] 함수 포인터

2] 함수 객체

3] 람다 표현식

많은 STL 알고리즘이 데이터를 처리하기 위해 매개변수로 함수 객체를 받아들인다.
펑크터(Functor)라고도 불리는 함수 객체는 ()(호출 연산자)와 함께 사용할 수 있는 객체를 의미한다.
이러한 함수 객체는 우선 타입을 선언하고, 해당 클래스에서 ()를 오버로딩하여 구현하게 된다.

1) 함수 객체의 장점

직접적인 함수 호출과 비교하여 함수 객체를 사용하면 다음과 같은 장점을 가진다.

1] 함수 객체는 상태(State)를 포함할 수 있다.

2] 함수 객체는 타입이므로, 템플릿 인수로 사용할 수 있다.

2) 미리 정의된 함수 객체

STL은 자주 사용할만한 연산에 대해 몇 가지 기본적인 함수 객체를 미리 정의하여 제공하고 있다.
이러한 미리 정의된 함수 객체는 함수를 매개변수로 전달 받는 STL 함수를 지원하기 위해 제공된다.
이러한 함수 객체는 functional 헤더 파일에 정의되어 있다.

STL에서는 다음과 같은 함수 객체를 미리 정의하여 제공하고 있다.

함수 객체	연산자	함수 객체	연산자
`plus`	`+`	`greater`	`>`
`minus`	`-`	`greater_equal`	`>=`
`multiplies`	`*`	`less`	`<`
`divides`	`/`	`less_equal`	`<=`
`modulus`	`%`	`logical_and`	`&&`
`negate`	`-`	`logical_or`	`\|\|`
`equal_to`	`==`	`logical_not`	`!`
`not_equal_to`	`!=`

다음의 코드는 함수 객체를 사용하여 일반적인 산술 연산 및 관계 연산을 구현한 것이다.

#include <functional>
#include <iostream>
using namespace std;

int main(void) {
    plus<int> add;
    equal_to<int> comp;
    greater_equal<int> ge;

    cout << add(7, 3) << endl;
    cout << comp(7, 3) << endl;
    cout << ge(7, 3) << endl;

    return 0;
}

// 10
// 0
// 1

함수 객체는 일반적으로 위와 같이 사용하지는 않으며, 보통 함수의 인수로 전달될 때 사용된다.

다음의 코드는 greater와 less 함수 객체를 각각 sort() 함수의 인수로 전달하여 사용하는 것이다.

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main(void) {
    vector<int> vc = {20, 40, 10, 30};  // vector 객체의 선언 및 초기화

    sort(vc.begin(), vc.end(), greater<int>());
    copy(vc.begin(), vc.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    sort(vc.begin(), vc.end(), less<int>());
    copy(vc.begin(), vc.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

// 40 30 20 10
// 10 20 30 40

3. 알고리즘

1) STL 알고리즘 함수

STL의 목적은 일반적인 알고리즘에 대한 효율적인 구현을 제공하는 것이다.
따라서 STL은 이러한 알고리즘을 STL 알고리즘 함수나 STL 컨테이너의 멤버 함수를 사용하여 구현하고 있다.

STL 컨테이너는 반드시 필요한 기능만을 포함하고 있으며, 동작하는 데 필요한 모든 기능을 가지고 있지는 않다.
따라서 STL 컨테이너는 알고리즘을 제공하는 많은 전역 함수와 함께 사용해야만 제 기능을 발휘할 수 있다.
이렇게 제공되는 STL 알고리즘 함수는 반복자를 통해 임의의 컨테이너에 같은 방법으로 적용된다.

참고로 대부분의 알고리즘 함수는 algorithm과 numeric 헤더 파일에 정의되어 있다.

2) STL 알고리즘의 분류

STL 알고리즘은 기능별로 다음과 같이 구분할 수 있다.

1] 읽기 알고리즘(algorithm 헤더 파일)

2] 변경 알고리즘(algorithm 헤더 파일)

3] 정렬 알고리즘(algorithm 헤더 파일)

4] 수치 알고리즘(numeric 헤더 파일)

(1) 읽기 알고리즘

STL 읽기 알고리즘 함수는 컨테이너를 변경하지 않으며, 컨테이너의 지정된 범위에서 특정 데이터를 읽기만 하는 함수이다.
STL에서 제공하는 대표적인 읽기 알고리즘 함수는 다음과 같다.

1] find()

두 개의 입력 반복자로 지정된 범위에서 특정 값을 가지는 첫 번째 요소를 가리키는 입력 반복자를 반환함

2] for_each()

두 개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입한 후, 대입한 함수 객체를 반환함

(2) 변경 알고리즘

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

1] copy()

두 개의 입력 반복자로 지정된 범위의 모든 요소를 출력 반복자가 가리키는 위치에 복사함

2] swap()

두 개의 참조가 가리키는 위치의 값을 서로 교환함

3] transform()

두 개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입한 후, 출력 반복자가 가리키는 위치에 복사함

(3) 정렬 알고리즘

STL 정렬 알고리즘 함수는 컨테이너의 지정된 범위의 요소들이 정렬되도록 컨테이너를 변경하는 함수이다.
모든 정렬 알고리즘 함수는 올바른 정렬을 위해 임의 접근 반복자를 사용한다.
따라서 임의 접근이 가능한 컨테이너만이 사용할 수 있다.
STL에서 제공하는 대표적인 정렬 알고리즘 함수는 다음과 같다.

1] sort()

두 개의 임의 접근 반복자로 지정된 범위의 모든 요소를 서로 비교하여, 오름차순으로 정렬함

2] stable_sort()

두 개의 임의 접근 반복자로 지정된 범위의 모든 요소를 서로 비교하여, 값이 서로 같은 요소들의 상대적인 순서는 유지하면서 오름차순으로 정렬함

3] binary_search()

sort() 함수를 사용하여 오름차순으로 정렬한 후에, 전달된 값과 같은 값이 있으면 참(true)을 반환하고 없으면 거짓(false)을 반환함

(4) 수치 알고리즘

수치 알고리즘 함수는 다른 알고리즘 함수와는 달리 numeric 헤더 파일에 정의되어 있다.
STL에서 제공하는 대표적인 수치 알고리즘 함수는 다음과 같다.

1] accumulate()

두 개의 입력 반복자로 지정된 범위의 모든 요소의 합을 반환한다.