[ 혼연 정리 ] STL 알고리즘 - 2 [ 읽기 알고리즘 ]

◎ search에 관련된 알고리즘

ㅇ 반복자 구간에서 다른 구간 전체가 발견되는 지점을 검색

- first1 ~ last1 전체 구간에서 first2 ~ last2구간과 일치하는 패턴을 찾아 그 반복자를 리턴한다.

  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]);

 - search : 전체 구간의 앞쪽에서 부터 검색
 - find_end : 전체구간의 뒤쪽 부터 검색
 - serarch_n  : 반복자 구간에서 val rkqtdl count번 연속으로 나타나는 지점을 찾는다.

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 void main()
8 {
9     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};
10     int ar2[]={1,5,9};
11
12     int *p;
13
14     p=search(&ar1[0],&ar1[25],&ar2[0],&ar2[3]);
15
16     if (p!=&ar1[25])
17     {
18         printf("%d번째에서구간이발견되었습니다.\n",p-ar1);
19     }
20
21     p=find_end(&ar1[0],&ar1[25],&ar2[0],&ar2[3]);
22
23     if (p!=&ar1[25])
24     {
25         printf("%d번째에서구간이발견되었습니다.\n",p-ar1);
26     }
27
28     p=search_n(&ar1[0],&ar1[25],3,9);
29     if (p!=&ar1[25])
30     {
31         printf("%d번째에서3연속의9를발견했습니다.\n",p-ar1);
32     }
33 }

ㅇ for_each

- 지정 구간을 반복하면서 지정한 작업을 수행한다.

UniOp for_each(InIt first, InIt last, UniOp op);

- first ~ last 사이의 구간을 순회하면서 op 함수 객체를 호출한다. 리턴값은 함수 객체인데 보통 무시한다.
- 루프를 돌리는 역할만 한다. 구체적인 동작을 하는 함수 객체가 반드시 필요하다.

 1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <algorithm>
5
6 using namespace std;
7
8 void func(string str)
9 {
10 cout << str << endl;
11 }
12
13 void main()
14 {
15 vector<string> vs;
16      vs.push_back("로보트태권브이");
17      vs.push_back("들장미소녀캔디");
18      vs.push_back("바보온달과평강공주");
19      vs.push_back("독수리오형제");
20
21      for_each(vs.begin(),vs.end(),func);
22 }

- for_earch가 특수화된 다른 알고리즘과 다른점이라면 일단 순회를 시작하면 멈출방법이 없다는 것이다.
- 검색으로는 적당하지 않음, 원하는걸 찾았으면 즉시 중단해야 하기 때문이다.


ㅇ equal

 - 두 개의 반복자 구간을 비교하여 두 구간이 완전히 일치하는지 아닌지를 검사한다.

 - bool equal(InIt1 first1, InIt1 last1, InIt2 first2 [, BinPred F]);

 - first1 ~ last1 사이의 구간과 first2 이후의 구간에 있는 요소들을 일대일로 비교해 보고 모든 요소가 일치하면 ture를 리턴하고 하나라도 틀리면 false를 리턴한다.
 - 두번째  구간은 시작 위치를 지정하는 반복자만 전달되고 끝 반복자는 전달되지 않는데 두 번째 구간도 첫 번째 구간과 길이가 같다고 가정한다.

 - 두 반복자 구간은 반드시 같은 컨테이너에 소속될 필요는 없으며 컨테이너의 타입이 달라도 상관없다.
 - 벡터와 리스트끼리도 비교 가능하다
 - 반복자 구간의 대응되는 요소끼리 비교할  디폴트로 == 연산자를 사용한다.
 - 특별한 비교 방식을 사용하고 싶다면 이항 조건자 F를 제공한다.
 - 두 요소가 같으면 true를 리턴한다. 틀리면 false를 리턴
 - 객체의 일부 멤버만 비교 할수 있고 어느 정도의 오차를 무시할 수도 있다.

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 void main()
8 {
9      int ari[]={8,9,0,6,2,9,9};
10      vector<int> vi(&ari[0],&ari[7]);
11
12      if (equal(&ari[0],&ari[7],vi.begin()))
13      {
14           puts("두구간은동일하다");
15      }
16      else
17      {
18           puts("두구간은틀리다.");
19      }
20
21 }

 - 함수 객체를 지정하면 두 요소가 같다는 조건을 마음대로 변경가능

 1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 bool compare(double a,double b)
8 {
9      return ((int)a == (int)b);
10 }
11
12 void main()
13 {
14
15      double af1[]={ 45.34, 77.84, 96.22, 91.04, 85.24 };
16      double af2[]={ 45.99, 77.25, 96.86, 91.23, 86.13 };
17
18       if (equal(&af1[0],&af1[4],&af2[0],compare))
19       {
20
21           puts("지정구간의정수부가모두같다.");
22
23       }
24       else
25       {
26           puts("지정구간의정수부중일부가일치하지않는다.");
27      }
28 }

ㅇ mismatch
 - equal 의 반대 함수이다.
 - 두 반복자 구간 중 최초로 틀린 부분이 어디인가를 찾는 다.
 - equal은 같다. 다르다만 조사하는데 비해 이 함수는 틀리면 어디쯤이 틀린지도 조사한다.

    pair<InIt1, InIt2> mismatch(InIt1 first1, InIt1 last1, InIt2 first2 [,BinPred F]);

-  리턴값은 두 구간이 최초로 달라진 지점의 반복자 쌍을 pair 객체로 묶어서 리턴한다.


1 include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 void main()
8 {
9      int ari[]={8,9,0,6,2,9,9};
10      vector<int> vi(&ari[0],&ari[7]);
11      vi[3]=7;
12
13      pair<int *,vector<int>::iterator> p;
14      p=mismatch(&ari[0],&ari[7],vi.begin());
15      if (p.first != &ari[7]) {
16           printf("%d번째자리(%d,%d)부터다르다.\n",
17               p.first-ari,*(p.first),*(p.second));
18      } else {
19           puts("두컨테이너가일치한다.");
20      }
21 }

- 정답과 학생이 작성한 답안지의 각 요소를 비교하여 오답들을 검색한다.

 1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 void main()
8 {
9     int answer[]={1,1,4,3,2,4,3,2,3,4,1,2,4,4,3,2,1,3,2,4};
10     int paper[]= {1,1,4,3,3,4,3,1,3,4,1,2,4,4,3,4,1,3,2,2};
11
12     pair<int *,int *> p;
13     int i;
14     for (i=0;;)
15     {
16         p=mismatch(&answer[i],&answer[20],&paper[i]);

17         if (p.first == &answer[20]) break;
18         printf("%d번틀림, 정답=%d, 니가쓴답=%d\n",
19             p.first-answer+1,*(p.first),*(p.second));
20         i=p.first-answer+1;
21     }
22
23 }

ㅇ count

 - 반복자 구간에서 지정한 값과 일치하는 요소의 개수를 센다.

size_t count(InIt first, InIt last, const T& val);
size_t count_if(InIt first, InIt last, UniPred F);

 - 리턴값은 조건을 만족하는 요소의 개수이며 일치하는 요소가 없으면 0이 리턴된다.
- == 연산으로 일치 조건을 판단


1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 void main()
7 {
8
9      const char *str="Oh baby baby,How was I supposed to know "
10           "That something wasn't right here";
11
12      size_t num;
13
14      num=count(&str[0],&str[strlen(str)+1],'a');
15
16      printf("이문장에는a가%d개있습니다.\n",num);
17 }

ㅇ count_if
 - 단항 조건자 객체가일치 조건을 판단하여 다양한 조건을 점검할 수 있다.

1 #include <iostream>
2 #include <algorithm>
3 #include <functional>
4
5 using namespace std;
6
7
8 void main()
9 {
10      const char *str="Oh baby baby,How was I supposed to know "
11           "That something wasn't right here";
12      size_t num;
13
14      num=count_if(&str[0],&str[strlen(str)+1],bind2nd(greater<char>(),'t'));
15      printf("이문장에는t보다더큰문자가%d개있습니다.\n",num);
16 }

ps : 출처 및 자세한 내용은  www.WinAPI.co.kr 참고