42-1-나.search

다음 함수들은 반복자 구간에서 다른 구간 전체가 발견되는 지점을 검색한다. 문자열에서 부분 문자열의 최초 위치를 검색하는 strstr 함수와 유사한 동작을 하되 임의 타입에 대해 부분 검색이 가능하다는 점에서 훨씬 더 일반적이다.

 

FwdIt1 search(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2 [, BinPred F]);

FwdIt1 find_end(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2 [,BinPred F]);

FwdIt1 search_n (FwdIt1 first1, FwdIt1 last1, Size count, const Type& val[, BinPred F]);

 

first1~last1 전체 구간에서 first2~last2 구간과 일치하는 패턴을 찾아 그 반복자를 리턴한다. search는 전체 구간의 앞쪽에서부터 검색을 하고 find_end는 전체 구간의 뒤쪽에서부터 검색을 한다. 두 함수가 검색 시작 방향만 틀릴 뿐이다. find_end의 이름을 search_end나 search_reverse로 지었다면 훨씬 더 이해하기 쉬웠을텐데 함수의 이름이 다소 부적절하게 붙여져 있다.

부분 검색이 논리적으로 의미가 있으려면 전체 구간이 부분 구간보다는 더 길어야 한다. 그렇지 않으면 검색은 항상 실패할 것이다. 전체 구간을 끝까지 검색했는데 부분 구간이 발견되지 않으면 last1이 리턴된다. search_n은 반복자 구간에서 val 값이 count번 연속으로 나타나는 지점을 찾는다.

 

: search

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

void main()

{

     int ar1[]={3,1,4,1,5,9,2,6,5,3,5,8,9,9,9,3,2,3,1,5,9,2,6,4,3};

     int ar2[]={1,5,9};

 

     int *p;

     p=search(&ar1[0],&ar1[25],&ar2[0],&ar2[3]);

     if (p!=&ar1[25]) {

          printf("%d번째에서 구간이 발견되었습니다.\n",p-ar1);

     }

     p=find_end(&ar1[0],&ar1[25],&ar2[0],&ar2[3]);

     if (p!=&ar1[25]) {

          printf("%d번째에서 구간이 발견되었습니다.\n",p-ar1);

     }

     p=search_n(&ar1[0],&ar1[25],3,9);

     if (p!=&ar1[25]) {

          printf("%d번째에서 3연속의 9를 발견했습니다.\n",p-ar1);

     }

}

 

정수 배열 ar1에 일련의 정수를 초기화해 놓고 이중 1,5,9가 연속으로 나타나는 구간이 있는지 검색해 보았다.

 

3번째에서 구간이 발견되었습니다.

18번째에서 구간이 발견되었습니다.

12번째에서 3연속의 9를 발견했습니다.

 

ar1에는 1,5,9가 두 번 나타나는데 search는 앞쪽의 1,5,9 구간을 찾고 find_end는 뒤쪽의 1,5,9 구간을 찾는다.

순방향으로 검색한다면 search 함수를 사용하고 역방향으로 검색한다면 find_end 함수를 사용하면 된다. find_end를 문자열에 대해 적용하면 역방향으로 단어 찾기를 수행할 수 있을 것이다. 참고로 요소 하나를 찾는 find 함수는 역방향 검색 함수가 따로 존재하지 않는다. 그렇다고 해서 역방향 검색을 하지 못하는 것은 아니고 역방향 반복자를 사용하면 끝에서부터 앞쪽으로 검색할 수 있다.

search_n은 9가 3번 연속으로 나오는 구간을 찾는다. 조건자를 주면 특정 조건을 연속적으로 만족하는 구간을 찾을 수 있는데 예를 들어 연속적으로 배수 관계를 만족하는 일련의 요소 그룹을 찾을 수 있다.