42.1 읽기 알고리즘
42.1.1 find
원하는 정보를 구하기만 하는 알고리즘
-
find 함수 원형
Init find( Init first, Init last, const T& val ) ;
입력 반복자 두 개로 검색 대상 구간을 지정, 검색하고자하는 값을 세번째 인수로 전달
값이 있으면 그 반복자 리턴, 없으면 last 리턴
- 예제 find
|
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std ;
void main ( void ) { string name[] = { "김정수", "구홍녀", "문병대", "김영주", "임재임", "박미영", "박윤자" } ;
vector<string> as( &name[0], &name[7] ) ;
vector<string>::iterator it ; it = find( as.begin(), as.end(), "안순자" ) ; if ( it == as.end() ) { cout << "없다" << endl ; } else { cout << "있다" << endl ; } } |
-
find_if 함수 원형
Init find_if ( Init first, Init last, UniPred F ) ;
원하는 조건을 만족하는 요소를 검색
find는 요소를 비교할 때 == 연산자를 사용하지만 find_if는 사용자가 지정한 단항 함수 객체 F로 비교
- 예제 find_if
|
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std ;
bool hasYoung(string who) { return (who.find("영") != string::npos) ; }
void main ( void ) { string name[] = { "김정수", "구홍녀", "문병대", "김영주", "임재임", "박미영", "박윤자" } ;
vector<string> as( &name[0], &name[7] ) ; vector<string>::iterator it ;
for ( it = as.begin() ; ; it++ ) { it = find_if( it, as.end(), hasYoung ) ; if ( it == as.end() ) { break ; } cout << *it << "이(가) 있다." << endl ; } } |
함수 포인터 대신 () 연산자를 정의하는 함수 객체를 사용할 수 있음
- 변경
|
struct hasYoung { bool operator() (string who) const { return (who.find("영") != string::npos) ; } } ; it = find_if( it, as.end(), hasYoung() ) ; |
-
adjacent_find 함수 원형
Fwdlt adjacent_find(Fwdlt first, Fwdlt last [, BinPred F]) ;
반복자 구간에서 인접한 두 요소가 같은 값을 가지는 위치를 검색
앞쪽 반복자의 위치를 리턴
인접한 두 요소가 같은 것이 없으면 last 리턴
- 예제 adjacent_find
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
void main ( void ) { int ari[] = { 1, 9, 3, 6, 7, 5, 5, 8, 1, 4 } ;
vector<int> vi( &ari[0], &ari[9] ) ; vector<int>::iterator it ;
it = adjacent_find( vi.begin(), vi.end() ) ; if ( it != vi.end() ) { cout << "인접한 값은 " << *it << "입니다." << endl ; } } |
조건자가 있는 함수를 사용하면 == 연산자 사용
== 연산자 대신 조건자 함수 객체를 사용하여 두 요소의 조건을 점검함
이 함수의 조건을 바꿔 2배 큰 값, 3배 큰 값 등 제작 가능
두 요소의 어떠한 관계든지 검색 가능
- 변경
|
bool divisor ( int a, int b ) { return ( a%b == 0 ) ; } ..... it = adjacent_find(vi.begin(), vi.end(), divisor) ; if ( it != vi.end() ) { cout << "최초로 발견된 약수 관계는" << *it << " " << *(it+1) << endl ; } |
divisor 함수는 두 정수 a,b를 전달받아 a가 b로 나누어 떨어지는지를 검사
앞 요소가 뒷 요소의 배수인 최초의 쌍을 검색
- 예제 adjacent_find2
|
#include <iostream> #include <algorithm> using namespace std ;
bool doublespace(char a, char b) { return ( a == ' ' && b == ' ' ) ; }
void main ( void ) { const char *str = "기다림은 만남을 목적으로 하지 않아도 좋다." ;
const char *p, *pend = &str[strlen(str)] ; for ( p = str ; ; p++ ) { p = adjacent_find(p, pend, doublespace) ; if ( p == pend ) { break ; } cout << p-str << "위치에 이중 공백 존재" << endl ; } } |
-
find_first_of 함수 원형
Fwdlt1 find_first_of(Fwdlt1 first1, Fwdlt1 last1, Fwdlt2 first2, Fwdlt2 last2 [, BinPred F]) ;
첫 번째 반복자 구간에서 두 번째 반복자 구간 중 하나가 최초로 발견되는 지점을 검색
첫 구간의 모든 요소와 두 번째 구간의 모든 요소에 대해 이중 루프를 돌며 두 값이 조건을 만족하는지 검사
디폴트 조건은 ==
first1 ~ ( first2 ~ last2 ) 까지 돌며 비교, 같으면 리턴
- 예제 find_first_of
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
void main ( void ) { 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 } ; int ar2[] = { 2, 4, 6, 8, 0 } ;
int *p = find_first_of( &ar1[0], &ar1[25], &ar2[0], &ar2[4] ) ; if ( p != &ar1[25] ) { printf("최초의 짝수는 %d 번째의 %d입니다.\n", p-ar1, *p ) ; } } |
42.1.2 search
반복자 구간에서 다른 구간 전체가 발견되는 지점을 검색
Fwdlt1 search ( Fwdlt1 first1, Fwdlt1 last1, Fwdlt2 first2, Fwdlt2 last2 [, BinPred F] ) ;
Fwdlt1 find_end ( Fwdlt1 first1, Fwdlt1 last1, Fwdlt2 first2, Fwdlt2 last2 [, BinPred F] ) ;
Fwdlt1 search_n ( Fwdlt1 first1, fwdlt1 last1, Size cout, const Type& val [, BinPred F] ) ;
first1 ~ last1 구간에서 first2~last2 구간과 일치하는 패턴을 찾아 그 반복자를 리턴
search : 전체 구간의 앞쪽에서부터 검색
find_end : 전체 구간의 뒤쪽에서 부터 검색
search_n : 구간에서 val 값이 count 번 연속으로 나타나는 지점을 찾음
- 예제 search
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
void main ( void ) { 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) ; } } |
42.1.3 for_each
지정 구간을 반복하면서 지정한 작업을 수행
UniOp for_each( Init first, Init last, UniOp op ) ;
first ~ last 사이의 구간을 순회하면서 op 함수 객체를 호출
구체적인 동작을 하는 함수 객체가 반드시 필요
find, find_if, count 등등 순회하면서 어떤일을 하는 대부분의 알고리즘을 이 함수로 구현 가능
순회 중에 요소값을 바꾼다거나 요소를 가리키는 대상체를 삭제 할 수 있음
포인터의 컨테이너에서 요소의 메모리를 정리할 때 흔히 사용됨
- 예제 for_each
|
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std ;
void func(string str) { cout << str << endl ; }
void main ( void ) { vector<string> vs ; vs.push_back("a") ; vs.push_back("b") ; vs.push_back("c") ; vs.push_back("d") ;
for_each(vs.begin(), vs.end(), func) ; } |
42.1.4 equal
두 개의 반복자 구간을 비교하여 두 구간이 완전히 일치하는지 아닌지를 검사
bool equal ( Init1 first1, Init1 last1, Ini2 first2, [, BinPred F] ) ;
first1 ~ last1 사이의 구간과 first2 이후의 구간에 있는 요소들을 일대일로 비교하여 모든 요소가 일치하면 true 리턴, 하나라도 틀리면 false 리턴
특별한 비교 방식을 사용하고 싶다면 이항 조건자 F 사용
- 예제 equal
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
void main ( void ) { int ari[] = {8,9,0,6,2,9,9} ; vector<int> vi(&ari[0], &ari[7]) ;
if ( equal( &ari[0], &ari[7], vi.begin() )) { puts("두 구간 동일") ; } else { puts("두 구간 틀림") ; } } |
- 예제 equal2
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
bool compare(double a, double b) { return ((int)a == (int)b) ; }
void main ( void ) { double af1[] = { 45.34, 77.84, 96.22, 91.04, 85.24 } ; double af2[] = { 45.99, 77.25, 96.86, 91.23, 86.13 } ;
if ( equal( &af1[0], &af1[4], &af2[0], compare )) { puts("지정 구간 정부수 동일") ; } else { puts("지정 구간 정수부 불일치") ; } } |
mismatch 함수
equal의 반대 함수, 두 반복자 구간 중 최초로 틀린 부분을 검색
pair<Init1, Init2> mismatch( Init1 first1, Init1 last1, Init2 first2 [, BinPred F] ) ;
- 예제 mstmatch
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
void main ( void ) { int ari[] = {8,9,0,6,2,9,9} ; vector<int> vi(&ari[0], &ari[7]) ; vi[3] = 7 ;
pair<int *, vector<int>::iterator> p ; p = mismatch(&ari[0], &ari[7], vi.begin() ) ; if(p.first != &ari[7]) { printf("%d번째 자리 (%d,%d)부터 다르다.\n", p.first-ari, *(p.first), *(p.second)) ; } else { puts("두 컨테이너가 일치한다.") ; } } |
- 예제 mstmatch2
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
void main ( void ) { int answer[] = {1,1,4,3,2,4,3,2,3,4,1,2,4,4,3,2,1,3,2,4} ; int paper[] = {1,1,4,3,3,4,3,1,3,4,1,2,4,4,3,4,1,3,2,2} ;
pair<int *, int*> p ; int i;
for ( i = 0 ; ; ) { p = mismatch( &answer[i], &answer[20], &paper[i] ) ; if ( p.first == &answer[20] ) { break ; } printf("%d 번 틀림, 정답 = %d, 니가 쓴답 = %d\n", p.first-answer+1, *(p.first), *(p.second)) ; i = p.first-answer+1 ; } } |
42.1.5 count
반복자 구간에서 지정한 값과 일치하는 요소의 개수를 셈
size_t count (Init first, Init last, const t& val) ;
size_t count_if (Init first, Init last, UniPred F) ;
- 예제 count
|
#include <iostream> #include <algorithm> using namespace std ;
void main ( void ) { const char *str = "Oh baby baby, How was I supposed to know" "that something wasn't right here" ; size_t num ;
num = count ( &str[0], &str[strlen(str)+1], 'a' ) ; printf("이 문장에는 a가 %d개 있습니다.\n", num ) ; } |
- 예제 count_if
|
#include <iostream> #include <algorithm> #include <functional> using namespace std ;
void main ( void ) { const char *str = "Oh baby baby, How was I supposed to know" "that something wasn't right here" ; size_t num ;
num = count_if( &str[0], &str[strlen(str)+1], bind2nd( greater<char>(),'t' )) ; printf("이 문장에는 t보다 큰 문자가 %d개 있습니다.\n", num) ; } |
- 예제 count2
|
#include <iostream> #include <ctime> #include <vector> #include <algorithm> using namespace std ;
const int NUM = 2000 ; const int RANGE = 10 ;
void makerand(int &i) { i = rand() % RANGE ; }
void main ( void ) { vector<int> num(NUM) ; vector<int>::iterator it ; int i ;
srand((unsigned int)time(NULL)) ; for_each(num.begin(), num.end(), makerand) ; for ( i = 0 ; i < RANGE ; i++ ) { printf("%02d의 출현 회수 : %d\n", i, count(num.begin(), num.end(), i)) ; } } |
42.2 변경 알고리즘
42.2.1 copy
지정한 구간을 복사
일부 요소들을 다른 컨테이너로 복사하고 싶을 때 사용
outIt copy ( Init first, Init last, outit result ) ;
bilt copy_backward( Bilt first, Bilt last, Bilt result ) ;
- 예제 copy
|
#include <iostream> #include <algorithm> using namespace std ;
void main ( void ) { char src[] = "1234567890" ; char dest[] = "abcdefghij" ;
copy( &src[3], &src[8], &dest[5] ) ; puts(dest) ; } |
- 예제 copy2
|
#include <iostream> #include <list> #include <algorithm> using namespace std ;
template <typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { char src[] = "1234567890" ; list<char> li ;
copy(&src[3], &src[7], back_inserter(li)) ; dump("list", li) ; } |
- 예제 copy_backward
|
#include <iostream> #include <list> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int i ; list<int> li, li2 ; list<int>::iterator first, last, result, it ;
for ( i = 0 ; i < 10 ; i++ ) { li.push_back(i) ; } li2 = li ;
dump("복사 전", li) ; first = find(li.begin(), li.end(), 2) ; last = find(li.begin(), li.end(), 7) ; result = find(li.begin(), li.end(), 3 ) ; copy(first, last, result) ; dump("copy", li) ;
first = find(li2.begin(), li2.end(), 2) ; last = find(li2.begin(), li2.end(), 7) ; result = find(li2.begin(), li2.end(), 8) ; copy_backward(first, last, result) ; dump("back", li2) ; } |
- 예제 copy_backward2
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int i ; vector<int> vi, vi2 ; for ( i = 0 ; i < 10 ; i++ ) { vi.push_back(i) ; } vi2 = vi ;
dump("복사전", vi) ; copy(vi.begin()+2, vi.begin()+7, vi.begin()+3) ; dump("copy", vi) ; copy_backward(vi2.begin()+2, vi2.begin()+7, vi2.begin()+8) ; dump("back", vi2) ; } |
-
교환 함수
void swap( T& x, T& y ) ;
Fwdit2 swap_ranges(Fwdit1 first1, Fwdit1 last1, Fwdit2 first2) ;
42.2.2 요소 생성
새로운 요소를 만들어 지정한 위치에 대입
void fill(Fwdit first, Fwdit last, const T& val) ;
void fill_n(Outit first, Size n, const T& val) ;
- 예제 fill
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int ari[]= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} ; vector<int> vi(&ari[0], &ari[16]) ;
fill(vi.begin()+2, vi.end()-5, 99 ) ; dump("vi", vi) ; } |
- 예제 random_shuffle
|
#include <iostream> #include <ctime> #include <algorithm> using namespace std ;
void main ( void ) { char str[] = "abcdefghijklmnopqrstuvwxyz" ;
srand((unsigned int)time(NULL)) ; puts(str) ; random_shuffle(&str[0], &str[strlen(str)]) ; puts(str) ; random_shuffle(&str[0], &str[strlen(str)]) ; puts(str) ; random_shuffle(&str[0], &str[strlen(str)]) ; puts(str) ; } |
- 예제 generate
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
int fibo( void ) { static int i1 = 1, i2 = 1 ; int t ; t = i1 + i2 ; i1 = i2 ; i2 = t ; return t ; }
void main ( void ) { vector<int> vi(10) ;
generate(vi.begin(), vi.end(), fibo) ; dump("vi", vi) ; } |
- 변경
|
struct fibo { private : int i1, i2 ; public : fibo() : i1(1), i2(1) {} int operator()() { int t ; t = i1 + i2 ; i1 = i2 ; i2 = t ; return t ; } } ; generate(vi.begin(), vi.end(), fibo()) ; |
42.2.3 요소 제거
Fwdit remove(Fwdit first, Fwdit last, const Type& val) ;
Fwdit remove_if(Fwdit first, Fwdit last, UniPred F) ;
Outit remove_copy(Fwdit first, Fwdit last, Outit result, const type& val) ;
Outit Remove_copy_if(Fwdit first, Fwdit last, outit result, UniPred F) ;
- 예제 remove
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int ari[] = {3,1,4,1,5,9,2,6,5} ; vector<int> vi(&ari[0], &ari[sizeof(ari)/sizeof(ari[0])]) ; vector<int>::iterator it ;
dump("원본", vi) ; it = remove(vi.begin(), vi.end(), 1) ; dump("remove", vi) ; vi.erase(it, vi.end()) ; dump("erase", vi) ; } |
- 예제 remove_copy
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int ari[] = {3,1,4,1,5,9,2,6,5} ; vector<int> vi(&ari[0], &ari[sizeof(ari)/sizeof(ari[0])]) ; vector<int> vi2;
remove_copy(vi.begin(), vi.end(), back_inserter(vi2), 1) ; dump("vi", vi) ; dump("vi2", vi2) ; } |
- 예제 unique
|
#include <iostream> #include <algorithm> using namespace std ;
void main ( void ) { char str[] = "abcccddefggghi" ; char *p ;
puts(str) ; p = unique( &str[0], &str[strlen(str)]) ; *p = 0 ; puts(str) ; } |
42.2.4 요소 재배치
- 예제 replace
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { const char *str = "Notebook Computer" ; vector<char> vc(&str[0], &str[strlen(str)]) ;
dump("원본", vc) ; replace(vc.begin(), vc.end(), 'o', 'a') ; dump("replace", vc) ; rotate(vc.begin(), vc.begin()+2, vc.end()) ; dump("rotate", vc) ; reverse(vc.begin(), vc.end()) ; dump("reverse", vc) ; } |
- 예제 partition
|
#include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int ari[] = {3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8} ; vector<int> vi(&ari[0], &ari[sizeof(ari)/sizeof(ari[0])]) ;
dump("원본", vi) ; partition(vi.begin(), vi.end(), bind2nd(greater<int>(), 5)) ; dump("partition", vi) ;
vector<int> ar2(&ari[0], &ari[sizeof(ari)/sizeof(ari[0])]) ; stable_partition(ar2.begin(), ar2.end(), bind2nd(greater<int>(), 5)) ; dump("stable", ar2) ; } |
42.2.5 요소 변경
- 예제 transform
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
int multi2(int a) { return a*2 ; }
int add(int a, int b) { return a+b ; }
void main ( void ) { vector<int> src(5), dest(5), sum ; int i ;
for ( i = 0 ; i < 5 ; i++ ) { src[i] = i ; } transform(src.begin(), src.end(), dest.begin(), multi2) ; dump("src", src) ; dump("dest", dest) ; transform(src.begin(), src.end(), dest.begin(), back_inserter(sum), add) ; dump("sum", sum) ; } |
42.3 정렬 알고리즘
42.3.1 sort
- 예제 sort
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int ari[] = {49,26,19,77,34,52,84,34,92,69} ;
vector<int> vi(&ari[0], &ari[10]) ; dump("원본", vi) ;
sort(vi.begin(), vi.end()) ; dump("sort", vi) ; vector<int> vi2(&ari[0], &ari[10]) ; stable_sort(vi2.begin(), vi2.end()) ; dump("stable_sort", vi2) ;
vector<int> vi3(&ari[0], &ari[10]) ; partial_sort(vi3.begin(), vi3.begin()+5, vi3.end()) ; dump("partial_sort", vi3) ;
vector<int> vi4(&ari[0], &ari[10]) ; nth_element(vi4.begin(), vi4.begin()+5, vi4.end()) ; dump("nth_element", vi4) ; } |
42.3.2 binary_search
- 예제 lower_bound
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int ari[] = {49,26,19,77,34,52,84,34,92,69} ; vector<int> vi(&ari[0], &ari[10]) ; vector<int>::iterator it ;
dump("원본", vi) ; sort(vi.begin(), vi.end()) ; it = lower_bound(vi.begin(), vi.end(), 50) ; if ( *it == 50 ) { cout << "찾는 값이 존재합니다." << endl ; } else { vi.insert(it, 50) ; dump("삽입 후", vi) ; } } |
42.3.3 merge
- 예제 merge
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int i ; vector<int> vi1, vi2, vi3 ; for ( i = 1 ; i < 5 ; i++ ) { vi1.push_back(i) ; } for ( i = 3 ; i < 9 ; i++ ) { vi2.push_back(i) ; } merge(vi1.begin(), vi1.end(), vi2.begin(), vi2.end(), back_inserter(vi3)) ; dump("merge", vi3) ;
vector<int> vi4 ; for ( i = 1 ; i < 5 ; i++ ) { vi4.push_back(i) ; } for ( i = 3 ; i < 9 ; i++ ) { vi4.push_back(i) ; } inplace_merge(vi4.begin(), vi4.begin()+4, vi4.end()) ; dump("inplace_merge", vi4) ; } |
42.3.4 min, max
- 예제 minmax
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
void main ( void ) { int i = 3, j = 5 ; printf("둘 중 작은 값은 %d이고 큰 값은 %d이다\n", min(i,j),max(i,j));
int ari[] = {49,26,19,77,34,52,84,34,92,69} ; vector<int> vi(&ari[0], &ari[10]) ; printf("벡터에서 가장 작은 값은 %d이고 가장 큰 값은 %d이다.\n", *min_element(vi.begin(), vi.end()), *max_element(vi.begin(), vi.end())) ; } |
42.4 수치 알고리즘
42.4.1 accumulate
- 예제 accumulate
|
#include <iostream> #include <vector> #include <numeric> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int ar1[] = {49,26,19,77,34,52,84,34,92,69} ; vector<int> vi1(&ar1[0], &ar1[10]) ; printf("벡터의 총합은 %d이다.\n", accumulate(vi1.begin(), vi1.end(), 0)) ;
int ar2[] = {1,2,3,4,5,6,7,8,9,10} ; vector<int> vi2(&ar2[0], &ar2[10]) ; vector<int> vi3 ; partial_sum(vi2.begin(), vi2.end(), back_inserter(vi3)) ; dump("부분합", vi3) ; } |
- 예제 adjacent_difference
|
#include <iostream> #include <vector> #include <numeric> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int ar[] = {1,2,5,10,15,12,20} ; vector<int> vi(&ar[0], &ar[7]) ; vector<int> vi2 ; adjacent_difference(vi.begin(), vi.end(), back_inserter(vi2)) ; dump("부분차", vi2) ; } |
42.4.2 순열 생성기
- 예제 next_permutation
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int i ; vector<int> vi ; vi.push_back(1) ; vi.push_back(2) ; vi.push_back(3) ; dump("원본", vi) ; for( i = 0 ; i < 6 ; i++ ) { next_permutation(vi.begin(), vi.end()) ; dump("다음", vi) ; } } |
42.4.3 inner_product
- 예제 inner_product
|
#include <iostream> #include <vector> #include <numeric> #include <algorithm> using namespace std ;
void main ( void ) { int inp ; vector<int> vi1, vi2 ; vi1.push_back(2) ; vi1.push_back(3) ; vi1.push_back(4) ; vi2.push_back(5) ; vi2.push_back(6) ; vi2.push_back(7) ; inp = inner_product(vi1.begin(), vi1.end(), vi2.begin(), 0) ; printf("내적 = %d\n", inp) ; } |
- 예제 lexicographical
|
#include <iostream> #include <vector> #include <numeric> #include <algorithm> using namespace std ;
void main ( void ) { vector<int> vi1, vi2 ; for ( int i = 8 ; i < 16 ; i++ ) { vi1.push_back(i) ; vi2.push_back(i) ; } // vi1[5] = 0 ; if ( lexicographical_compare(vi1.begin(), vi1.end(), vi2.begin(), vi2.end())) { cout << "v1이 더 작다" << endl ; } else { cout << "v1이 더 작지 않다." << endl ; } } |
42.4.4 힙 연산
- 예제 make_heap
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { int ar[] = {5,3,2,9,6} ; vector<int> vi(&ar[0], &ar[5]) ; dump("원본", vi) ; make_heap(vi.begin(), vi.end()) ; dump("make_heap", vi) ; vi.push_back(10) ; push_heap(vi.begin(), vi.end()) ; dump("push_heap", vi) ; pop_heap(vi.begin(), vi.end()) ; dump("pop_heap", vi) ; vi.pop_back() ; sort_heap(vi.begin(), vi.end()) ; dump("sort_heap", vi) ; } |
'책정리 > 혼자 연구하는 C,C++ 2' 카테고리의 다른 글
| 41장 연관 컨테이너 (0) | 2015.03.17 |
|---|---|
| 40장 시퀀스 컨테이너 (0) | 2015.03.16 |
| 39장 반복자 (0) | 2015.03.14 |
| 38장 함수 객체 (0) | 2015.03.13 |
| 37장 STL 개요 (0) | 2015.03.12 |