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

- STL 라이브러리는 객체 지향 기법의 일부 기능만 사용한다.
- 상속은 거의 사용하지 않으며 다형성은 느리다는 이유로 완전히 배제한다.
-  컨테이너 클래스는 내부적인 관리에 반드시 필요한 기능만을 가지며 필요한 모든 기능을 완벽하게 캡슐화하지 않는다.
- 컨테이너들은 알고리즘을 제공하는 전역 함수와 결합되어야 제 기능을 발휘할 수 있다.
-  알고리즘은 기능에 따라 읽기, 변경, 정렬, 수치 4가지로 크게 분류된다.

ㅇ 읽기 알고리즘
 - 컨테이너를 변경하지 않으며 컨테이너로부터 원하는 정보를 구하기만 하는 알고리즘

ㅇ find
- 가장 기본적인 알고리즘인 검색 기능을 제공
InIt find(InIt first, InIt last, const T& val);
- 입력반복자 두개로 검색 대상을 지정, 세번째로 인수로 검색하고자하는 값
- first ~ list 구간에서 val값을 가지는 요소가 있는지 검색하여 그 반복자를 리턴한다.
- val값을 발견되지 않으면 last가 리턴된다.

1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <algorithm>
5
6 using namespace std;
7
8 bool HasYoung(string who)
9 {
10      return (who.find("영") != string::npos);
11 }
12
13 void main()
14 {
15      string names[]={"김정수","구홍녀","문병대",
16           "김영주","임재임","박미영","박윤자"};
17
18      vector<string> as(&names[0],&names[7]);
19
20      vector<string>::iterator it;
21
22      for (it=as.begin();;it++)
23      {
24           it=find_if(it,as.end(),HasYoung);
25           if (it==as.end()) break;
26           cout << *it << "이(가) 있다." << endl;
27      }
28 }

 - find는 구간을 순차 검색하며 요소를 비교할 때는 요소 타입의 == 연산자로 비교한다. 따라서  검색을 위한 특별한 조건은 필요 없지만 컨테이너에
  요소가 많으면 검색 속도는 느려진다.
 - find는 최초로 조건을 만족하는 요소 하나만 검색하는데 만약 구간내에 일치하는 모든 요소를 검색하고 싶다면 다음과 같이 루프를 돌리면된다.

1 vector<string>::iterator it;
2 for (it=as.begin();;it++)
3 {
4     it=find(it,as.end(),"김정수");
5     if (it==as.end()) break;
6     cout << *it << "이(가) 있다." << endl;
7 }

ㅇ find_if
 - 완전히 일치하는 요소뿐만 아니라 원하는 조건을 만족하는 요소를 검색할 수 있다
InIt find_if(InIt first, InIt last, UniPred F);
 - find_if는 요소의 비교를 사용자가 지정한 단항 함수 객체 F로 비교한다.
 - 완전히 일치하는 것뿐만 아니라 부분 일치나 포함 여부 등으로도 검색 가능하다.
 - 다음 예제는 "영"자가 포함된 사람들을 검색한다.

1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <algorithm>
5
6 using namespace std;
7
8 bool HasYoung(string who)
9 {
10     return (who.find("영") != string::npos);
11 }
12
13 void main()
14 {
15     string names[]={"김정수","구홍녀","문병대",
16         "김영주","임재임","박미영","박윤자"};
17     vector<string> as(&names[0],&names[7]);
18
19     vector<string>::iterator it;
20     for (it=as.begin();;it++)
21     {
22         it=find_if(it,as.end(),HasYoung);
23
24         if (it==as.end()) break;
25         cout << *it << "이(가) 있다." << endl;
26     }
27 }

 - 함수 포인터 대신 ()연산자를 정의하는 함수 객체를 사용할 수도 있다

1 struct HasYoung
2 {
3     bool operator()   (string who) const
4     {
5         return (who.find("영") != string::npos);
6     }
7 };
8
9 it=find_if(it,as.end(),HasYoung());

ㅇ  adjacent_find()

 - 반복자 구간에서 인접한 두 요소가 같은 값을 가지는 위치를 검색한다.
 
 -  FwdIt adjacent_find(FwdIt first, FwdIt last [, BinPred F]);

 1 #include <iostream>
2 #include <vector>
3 #include <algorithm>n
4
5 using namespace std;
6
7 void main()
8 {
9      int ari[]={1,9,3,6,7,5,5,8,1,4};
10      vector<int> vi(&ari[0],&ari[9]);
11
12      vector<int>::iterator it;
13      it=adjacent_find(vi.begin(),vi.end());
14      if (it != vi.end())
15      {
16           printf("두요소가인접한값은%d입니다.\n",*it);
17      }
18 }

- adjacent_find로 검색한 결과 앞쪽 5의 반복자가 리턴될 것이다.

- 조건자가 있는 함수를 사용하면 == 연산자 대신 조건자 함수 객체를 사용하여 두 요소의 조건을 점검하는데 이 함수의 비교 방식에 따라 앞쪽 요소가 더 큰 최초의 쌍,
 인접한 값이 2 배되는 쌍, 서로소인 쌍 등을 검색할수 있다.
1 bool divisor(int a, int b)
2 {
3      return (a%b == 0);
4 }
5 .... 6      it=adjacent_find(vi.begin(),vi.end(),divisor);
7      if (it != vi.end()) {
8           printf("최초로발견된약수관계는%d,%d입니다.\n",*it,*(it+1));
9      }

- 이중 문자열을 찾는 예제

1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 bool doublespace(char a, char b)
7 {
8      return (a==' ' && b== ' ');
9 }
10
11 void main()
12 {
13      const char *str="기다림은 만남을목적으로하지않아도 좋다.";
14
15      const char *p,*pend=&str[strlen(str)];
16      for (p=str;;p++) {
17           p=adjacent_find(p,pend,doublespace);
18           if (p==pend) break;
19           cout << p-str << "위치에이중공백이있습니다." << endl;
20      }
21 }

ㅇ find_first_of
 - 첫 구간의 모든 요소와 두번째 구간의 모든 요소에 대해 이중 루프를 돌며 두값이 조건을 만족하는지 검사한다.
 - 디폴트 조건은 == 이다.
 - 마지막인로 이항 연항 조건자를 지정하면 원하는 조건을 지정가능

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

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,7,9,3,2,3,8,4,6,2,6,4,3};
10     int ar2[]={2,4,6,8,0};
11
12     int *p=find_first_of(&ar1[0],&ar1[25],&ar2[0],&ar2[4]);
13     if (p!=&ar1[25])
14     {
15 printf("최초의짝수는%d번째의%d입니다.\n",p-ar1,*p);
16     }
17 }

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