[C++ STL] '탐색 알고리즘(search algorithm)'

C++ STL에서 제공하는 컨테이너에는 기본적인 기능을 담은 멤버 함수가 있습니다. 그리고 그것과는 별개로, STL에선 알고리즘(algorithm)을 제공합니다. STL algorithm은 algorithm 헤더 파일을 통해 사용할 수 있습니다. 알고리즘과 컨테이너간의 관계를 그림으로 표현하면 다음과 같습니다.

 

 

위의 그림에서 보시는 것처럼 '알고리즘'이라는건 '컨테이너'에 들어있는 원소들을 조작할 수 있는 함수들의 모임이라고 생각하시면 됩니다. '컨테이너'에 들어있는 원소들을 어떤 기준을 가지고 정렬시키고 싶을 수도 있을 것이고, '컨테이너'에 들어있는 원소 집합 중에서 특정한 값이 들어있는지 찾고싶을 때도 있을 것이고, 어떤 조건에 해당하는 원소들을 집합에서 제거시키고 싶을 수도 있을 것이고, '컨테이너'에 들어있는 원소들의 값에 +10을 해주고싶다던가하는 변경 작업을 하고싶을 때도 있을 것입니다. 이렇게 사용하는데 필요할만한 원소 조작 기능들을 모아둔게 '알고리즘'입니다. STL은 100여 개의 알고리즘을 제공합니다. 해당 '알고리즘'들은 iterator라는 공통된 인터페이스를 통해 사용이 가능합니다.

 

제공하는 탐색 알고리즘은 아래와 같습니다. 이런 함수들이 있고 이런 식으로 사용하는구나 정도로 살펴보고 나중에 필요할 때 다시 찾아보고 사용하시다보면 저절로 손에 익을테니 굳이 외우려하지 말기 바랍니다.

알고리즘(algorithm)	p는 해당 순차열 [b, e)의 반복자를 나타냅니다.
adjacent_find(b, e)	순차열 [b, e)의 원소 중 *p == *(p+1)인 첫 원소를 가리키는 반복자를 반환합니다.
adjacent_find(b, e, f)	순차열 [b, e)의 원소 중 f(*p, *(p+1))이 참인 첫 원소를 가리키는 반복자를 반환합니다.
find(b, e, x)	순차열 [b, e)에서 x 값과 같은 첫 원소의 반복자를 반환합니다.
find_end(b, e, b2, e2)	순차열 [b, e) 중에서 [b2, e2)의 순차열과 일치하는 순차열 첫 원소의 반복자를 반환합니다. 단, 일치하는 순차열이 여러 개라면 그 중 마지막번 째의 순차열의 첫 원소를 반환합니다.
find_end(b, e, b2, e2, f)	기능은 위와 동일하며, 이때의 비교 기준은 조건자 함수 f에 따릅니다.
find_first_of(b, e, b2, e2)	순차열 [b, e) 중에서 [b2, e2)의 순차열 중 같은 원소가 단 하나라도 같은게 있는지 찾기 위한 알고리즘. 찾았다면 발견된 첫 번째 원소의 반복자를 반환합니다.
find_first_of(b, e, b2, e2, f)	기능은 위와 동일하며, 이때의 비교 기준은 조건자 함수 f에 따릅니다.
find_if(b, e, f)	순차열 [b, e)에서 f(*p)가 참인 원소를 찾고, 그 첫 번째 원소의 위치를 가리키는 반복자를 반환합니다.
search(b, e, b2, e2)	순차열 [b, e) 중에서 [b2, e2)의 순차열과 일치하는 순차열을 찾습니다. 단, 일치하는 순차열이 여러 개라면 첫 번째 순차열의 첫 원소의 위치를 가리키는 반복자를 반환합니다.
search(b, e, b2, e2, f)	기능은 위와 동일하며, 이때의 비교 기준은 조건자 함수 f에 따릅니다.

 

먼저, adjacent_find() 알고리즘은 간단히 인접한 두 원소의 값이 같은 원소들 중 가장 앞 쪽에 위치한 원소의 반복자(iterator)를 반환합니다. 예제를 살펴보겠습니다.

// 앞으로 헤더 부분과 using 부분은 생략합니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
    vector<int> v;
    v.push_back(10); v.push_back(22); v.push_back(25); v.push_back(30);
    v.push_back(30); v.push_back(40); v.push_back(41);
    
    // 구간 [v.begin(), v.end())에서 인접한 두 원소가 같은 원소를 찾습니다.
    auto iter = adjacent_find(v.begin(), v.end());
    
    if (iter != v.end()) cout << *iter;
}

 

위의 예제에서 인접한 두 원소의 값이 같은 원소는 30입니다. 그런데 '같다'는 것의 기준을 내 맘대로 설정할 순 없을까요? 예를 들면, 인접한 두 원소간의 값이 ±3 정도의 오차범위를 가지더라도 두 원소는 '같다'라고 판단한다와 같이 말이죠. 이 때는 조건자 버전의 adjacent_find() 알고리즘을 사용하면 됩니다. STL에서 제공하는 모든 알고리즘은 위의 예제처럼 디폴트 기준을 적용할 수 있는 버전과 내 맘대로 기준을 설정할 수 있는 '조건자 버전'을 제공합니다. 조건자를 적용시킨 adjacent_find() 알고리즘 예제를 살펴보겠습니다.

// 이항 조건자 (조건자는 '이항', '단항' 2가지입니다.)
bool Pred(int a, int b) {
    return abs(b - a) <= 3;
}

void main() {
    vector<int> v;
    v.push_back(10); v.push_back(22); v.push_back(25); v.push_back(30);
    v.push_back(30); v.push_back(40); v.push_back(41);
    
    // 구간 [v.begin(), v.end())에서 인접한 두 원소가 같은 원소를 찾습니다.
    // 3번째 매개변수는 함수 포인터입니다.
    auto iter = adjacent_find(v.begin(), v.end(), Pred);
    
    if (iter != v.end()) cout << *iter;
}

 

위의 예제를 통해 '조건자'에 대한 2가지 사실을 알 수 있습니다.

   1. '조건자'는 '단항 조건자', '이항 조건자' 2가지가 있다.

   2. '조건자'는 '함수 포인터'로 받는다.(함수, 함수객체 모두 넘길 수 있다.)

'조건자'는 나중에 따로 포스팅하겠습니다.

 

다음으로 find() 알고리즘은 이름에서 알 수 있듯이 특정 원소를 찾을 때 사용하는 함수입니다.

void main() {
    vector<int> v;
    v.push_back(10); v.push_back(20); v.push_back(30);
    v.push_back(40); v.push_back(50);
    
    // 구간 [v.begin(), v.end())에서 원소 '20'을 찾습니다.
    auto iter = find(v.begin(), v.end(), 20);
    
    if (iter != v.end()) cout << *iter;
}

 

해당 find() 알고리즘의 조건자 버전은 find_if() 알고리즘입니다. 조건자를 사용하는 예는 위에서 살펴본 것과 동일하고, 나머지 알고리즘의 사용방법도 지금까지 살펴본 것과 같은 느낌으로 사용됩니다. 따라서 나머지는 생략하겠습니다.