38-1-나.알고리즘의 변형

for_each 함수는 순회 중에 할 일을 결정하기 위해 반드시 함수 객체를 부르도록 되어 있다. 순회만 할 바에야 for_each를 부를 필요가 없으므로 for_each에게 함수 객체는 필수적인 존재라고 할 수 있다. 이처럼 함수 객체를 명시적으로 요구하는 알고리즘도 있고 필요할 때만 함수 객체를 옵션으로 받는 알고리즘도 있다.

컨테이너에서 값을 검색하는 find는 순회중의 반복자 값과 세 번째 인수로 지정한 값(val)을 == 연산자로 비교하여 정확하게 일치하는 요소를 찾아낸다. 그런데 때로는 ==로 정확한 일치를 검색하는 것이 아니라 사용자가 정의하는 방식으로 검색할 요소를 골라야 하는 경우도 있다. 이때 함수 객체로 요소를 직접 비교할 수 있는데 이런 함수는 보통 원래 함수의 이름 끝에 _if가 붙는다. find의 함수 객체 버전은 다음과 같다.

InIt find_if(InIt first, InIt last, UniPred F);

세 번째 인수 F는 () 연산자를 오버로딩하는 함수 객체이며 요소값 하나를 인수로 전달받아 이 값이 원하는 조건이 맞는지 검사하여 bool형을 리턴한다. 찾는 조건에 맞으면 true를 리턴하고 아니면 false를 리턴할 것이다. 이처럼 bool을 리턴하는 함수 객체를 특별히 조건자(Predicate)라고 부르는데 요소가 지정 조건을 만족하는지를 검사하는 역할을 한다. 다음은 find_if를 활용한 검색 예제이다.

예 제 : find_if

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

struct IsKim {

bool operator()(string name) const {

return (strncmp(name.c_str(),"김",2)==0);

}

};

void main()

{

string names[]={"김유신","이순신","성삼문","장보고","조광조",

"신숙주","김홍도","정도전","이성계","정몽주"};

vector<string> vs(&names[0],&names[10]);

vector<string>::iterator it;

it=find_if(vs.begin(),vs.end(),IsKim());

if (it==vs.end()) {

cout << "없다." << endl;

} else {

cout << *it << "이(가) 있다." << endl;

}

}

names 벡터에 사람 이름을 여러 개 나열해 놓고 이 중 김씨성을 가진 사람이 있는지를 검색한다. 전체 이름을 다 검사하는 것이 아니라 이름의 일부만을 검사하므로 find 함수로는 이 검색을 수행할 수 없다. 부분 문자열 검색을 위해 () 연산자를 오버로딩하여 앞 두 글자가 "김"인지를 검사하는 IsKim이라는 함수 객체 클래스를 선언해 놓고 find_if의 세 번째 인수로 이 함수 객체를 전달했다. find_if 호출문은 다음 두 줄로도 표현할 수 있다.

IsKim K;

it=find_if(vs.begin(),vs.end(),K);

지역 객체 K를 선언하고 이 객체를 find_if의 세 번째 인수로 전달했는데 이때 K는 어차피 find_if에서만 사용되므로 임시 객체이면 충분하다. IsKim()은 생성자 호출문이므로 () 괄호는 생략할 수 없다. 또는 다음과 같이 일반 함수를 정의하고 함수 포인터를 전달해도 상관없다.

bool IsKim(string &name)

{

return (strncmp(name.c_str(),"김",2)==0);

}

it=find_if(vs.begin(),vs.end(),IsKim);

이때는 IsKim 다음에 괄호를 적지 말아야 하는데 함수명 자체가 함수 포인터이므로 괄호가 붙을 필요가 없으며 붙어서도 안된다. 함수 포인터를 쓰나 함수 객체를 쓰나 실행 결과는 동일하지만 가급적이면 함수 객체를 쓰는 것이 훨씬 유리하다. 순차 검색을 하는 find_if는 각 요소마다 일일이 비교를 하는데 이때마다 실제 함수가 호출된다면 오버헤드가 너무 커지기 때문이다.

함수 객체로 만들 때와 함수 포인터를 쓸 때 인수의 형태가 조금 달라진다. 함수 포인터는 레퍼런스를 전달받는 것이 좋은데 왜냐하면 string같이 덩치가 큰 객체를 전달할 때 값으로 받으면 복사가 발생하며 이 비용이 무시할 수 없을 정도로 커질 수 있기 때문이다. int같은 단순 타입이라면 물론 값으로 전달하나 레퍼런스로 전달하나 전혀 차이가 없지만 말이다. 반면 함수 객체는 크기에 상관없이 값으로 전달받아야 하는데 왜냐하면 인라인으로 삽입되기 때문에 인수 전달 과정이 필요없기 때문이다.

만약 최초의 김가만 찾는 것이 아니라 컨테이너내의 모든 김가를 다 검색하고 싶다면 다 찾을 때까지 루프를 돌리면 된다. main의 코드를 다음과 같이 수정하면 모든 김가들이 다 검색된다.

void main()

{

....

vector<string>::iterator it;

for (it=vs.begin();;it++) {

it=find_if(it,vs.end(),IsKim());

if (it==vs.end()) break;

cout << *it << "이(가) 있다" << endl;

}

}

함수 객체는 고정된 의미를 가지는 알고리즘에 유연성을 부여하여 활용도를 대폭적으로 향상시킨다. 비교 조건을 직접 작성할 수 있으므로 정확하게 같은 것만 검색하는 것이 아니라 사용자가 원하는 어떤 조건으로도 검색할 수 있다. 사원 명부 컨테이너에서 직급이 과장 이상이고 나이는 45 ~ 49세 사이이며 가불을 한 적이 있고 입사한지 10년 이상 되었고 자택을 소유한 남자 사원을 검색하는 정도의 복잡한 동작까지도 가능해진다.

find는 템플릿으로 되어 있으므로 임의의 컨테이너에 대해 검색을 수행할 수 있는 일반성을 가진다. 검색 대상을 템플릿 인수로 전달받으므로 인수로 검색 대상을 지정할 수 있다. find_if는 여기에 비교 방식까지도 인수로 전달받아 검색 조건이 무엇인가까지도 사용자가 지정할 수 있다. 그래서 find보다 find_if가 훨씬 더 일반적이다.

find뿐만 아니라 대부분의 STL 알고리즘은 함수 객체를 인수로 취하는 버전이 있다. 정렬, 대체, 병합, 계산 등에 사용자가 개입할 여지가 많이 남겨져 있어 STL이 제공하는 기능대로만 사용하지 않아도 된다. 그래서 60개밖에 안되는 알고리즘으로도 엄청나게 많은 일을 처리할 수 있는 것이다. 다음 항에서는 sort 함수에 함수 객체를 사용하여 원하는 바대로 정렬하도록 해 볼 것이다.

다음은 본 주제를 잠시 벗어나 find와 find_if 함수의 이름에 대해 고찰해 보자. 고정 값으로 검색하건 함수 객체를 쓰건 논리적으로 검색이라는 같은 연산을 하므로 두 함수의 이름을 통합하면 좋을 것 같은데 이름이 달라 불편하다. 이렇게 된 원인은 두 함수의 선언문이 사실상 동일하기 때문이다. 두 함수의 원형을 보자.

InIt find(InIt first, InIt last, const T& val);

InIt find_if(InIt first, InIt last, UniPred F);

범위를 지정하는 두 인수의 타입은 완전히 동일하지만 세 번째 인수의 타입이 달라 언뜻 보기에는 오버로딩 조건을 만족하는 것 같다. 값이 전달되는 호출과 함수 객체가 전달되는 호출이 구분될 것처럼 보인다. 그러나 실제로는 구분되지 않는데 왜냐하면 둘 다 템플릿이기 때문이다. 오버로딩은 함수 호출시에 실인수의 타입을 보고 결정되지만 템플릿 구체화는 그보다 훨씬 이전인 컴파일할 때 일어나므로 구체화할 템플릿을 먼저 선택할 수 있어야 한다. 똑같은 이름으로 두 개의 템플릿이 정의되어 있으면 컴파일러는 도대체 어떤 것을 참조하여 구체화해야 하는지를 결정할 수 없는 것이다. 이 상황이 잘 이해가 안가면 다음 코드를 컴파일해 보고 컴파일러의 투덜거림을 읽어 보자.

template<typename IT, typename T>

IT find(IT first, IT last, T val) { return first; }

template<typename IT, typename F>

IT find(IT first, IT last, F Pred) { return first; }

보다시피 완전히 똑같은 템플릿이다. 템플릿 인수의 이름이 T나 F인 것은 컴파일러가 보기에는 아무 의미가 없다. 설사 컴파일러가 템플릿 인수의 이름을 논리적으로 판단하는 인공 지능이 있어 이게 가능하다고 하더라도 다음과 같은 억지스러운 상황이 추가로 발생하는 문제가 있다.

find(vs.begin(),vs.end(),IsKim());

이 호출문의 세 번째 인수가 함수 객체이므로 함수 객체 버전을 호출해야 한다고 확신할 수 있을까? 만약 vs가 함수 객체의 벡터라면 그 중 IsKim() 객체와 같은 요소를 검색하라는 명령이라고 우길 수도 있지 않겠는가? 물론 이건 억지에 불과하다. 이런 억지가 통하지 말아야 하기 때문에 find와 find_if는 하나로 통합되지 못하고 서로 다른 이름을 가질 수밖에 없는 것이다.

그러나 STL의 모든 함수 객체 알고리즘이 항상 if로만 끝나는 것은 또 아니다. sort나 merge같은 알고리즘은 일반 버전과 함수 객체 버전의 인수 개수가 달라 모호함이 없기 때문에 두 버전이 같은 이름으로 정의되어 있다. 일반화를 부르짖는 STL의 알고리즘 함수 이름이 비일반적인 셈인데 기술적인 이유야 분명히 있지만 사용자들이 기억할 게 많아진다는 점에서 바람직하지 못한 설계라고 할 수 있다.

IncludeSin

find_if 예제를 변경하여 이름에 "신"자가 포함된 모든 요소를 검색하도록 수정해 보아라.