[ 혼연 정리 ] STL 개요 - 4 [알고리즘]

ㅇ 알고리즘
 
STL의 알고리즘 함수들은 전역함수로 작성되어 있다. STL은 일반화된 알고리즘을 제공하므로 캡슐화를 적극적으로 사용하지 않는다.
컨테이너 클래스들은 표현하고자 하는 구조를 위한 데이터 멤버와 연산자만 정의하며 알고리즘 구현은 반복자와 전역 함수에 맡긴다.
알고리즘 함수들은 대부분 algorithm 헤더 파일에 정의되어 있다. ==> 시간이 나면 한번 봐두자

- find 함수
 가장 흔하게 사용된다. 원형은 다음과 같다.

template<typename InIt, class T>
 InIt find(InIt first, InIt last, const T& val);

InIt : 반복자
const T& val : 탬플릿

임의의 모든 타입에 대해 동작할 수 있어야 하므로 STL 알고리즘 함수들은 예외 없이 탬플릿으로 구성

C 함수들은 검색에 실패할 경우 NULL을 리턴하지만 STL은 검색 실패하면 반복자를 리턴한다.
반복자만으로 요소를 읽을 수 있고, 이 요소를 val과 비교할 수 있으며 비교 범위도 명확하게 전달되었으므로 find가 컨테이너에 대한 정보를 전달받을 필요 없다.
컨테이너가 어떤 식의 구조를 가지는지 모르므로 find는 가장 간단하고 어떤 형태의 자료에나 사용할 수 있는 순차 검색 방법을 사용한다.

예제 : find
1 #include <iostream>
 2 #include <vector>
3 #include <list>
4 #include <algorithm>
5 using namespace std;
6
7 void main()
8 {
9     int ari[]={1,2,3,4,5};
10 vector<int> vi(&ari[0],&ari[5]);
11     list<int> li(&ari[0],&ari[5]);
12
13     puts(find(vi.begin(),vi.end(),4)==vi.end() ? "없다.":"있다.");
14     puts(find(li.begin(),li.end(),8)==li.end() ? "없다.":"있다.");
15     puts(find(&ari[0],&ari[5],3)==&ari[5] ? "없다.":"있다.");
16 }

- sort
 정렬 함수 , 원형은 다음과 같다.퀵 소틑 알고리즘을 사용

void sort(RanIt first, RanIt last);

sort 함수는 정렬 중에 < 연산자로 요소의 순위를 판단 ==> 정렬 대상 요소들은 < 연산자를 반드시 정의해야 한다.
사용자가 정의한 클래스도 < 연산자가 오버로딩되어 있으면 이 함수로 정렬 가능

예제 : sort

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 void main()
7 {
8     int ari[]={2,8,5,1,9};
9 vector<int> vi(&ari[0],&ari[5]);
10
11     sort(vi.begin(),vi.end());
12     vector<int>::iterator it;
13     for (it=vi.begin();it!=vi.end();it++) {
14         printf("%d\n",*it);
15     }
16 }

- reverse
 지정한 구간의요소들 순서를 반대로 뒤집는다.

void reverse(BiIt first, BiIt last);

예제 : reverse

1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4
5 void main()
6 {
7     int ari[]={1,2,3,4,5,6,7,8,9};
8     int i;
9
10     for (i=0;i<9;i++) printf("%d ",ari[i]);puts("");
11     reverse(&ari[2],&ari[6]);
12     for (i=0;i<9;i++) printf("%d ",ari[i]);puts("");
13 }

- random
 컨테이너의 구간내 요소를 무작위로 마구 섞는다.

void random_shuffle(RanIt first, RanIt last);

예제 : shuffle
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 #include <time.h>
5 using namespace std;
6
7 void main()
8 {
9     int i;
10 vector<int> vi(20);
11     vector<int>::iterator it;
12    
13     for (i=0;i<20;i++) vi[i]=i;
14     srand(time(NULL));
15     random_shuffle(vi.begin(),vi.end());
16     for (it=vi.begin();it!=vi.end();it++) {
17         cout << *it << ' ';
18     }
19     cout << endl;
20 }

 - 자주 사용하는 함수 목록

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