algorithm 4 merge, heap, min, max

cpp algorithm

++merge

+merge() ; 정렬된 범위를 합친다. 자동 정렬됨.

merge(first1, last1, first2, last2, result (,comp) )

std::merge( first, first+5, second, second+5, v.begin()) ;    // first와 second는 이미 sort 상태여야 함. 둘 을 합쳐 오름차순으로 v에 기록.

+includes() ; 범위 [first1, last1)내에 범위[fisrt2, last2)를 포함하는지 테스트. 둘 다 정렬된 상태여야 함.

bool includes(first1, last1, first2, last2 (,comp)) ;

+set_union ; 합집합. 두 개의 소팅된 범위를 합친다. 중복 제거.

std::sort(first, first+5) ;

std::sort(second, second+5) ;

it = std::set_union(first, first+5, second, second+5, v.begin()) ;

v.resize( it-v.begin() ) ;

+set_intersection ; 교집합. 두 개의 영역에 모두 해당되는 값들을 추출. (정렬상태)

it = std::set_intersection(first, first+5, second, second+5, v.begin()) ;

v.resize(it-v.begin()) ;

+set_difference ; 차 집합. A-B. (정렬상태)

 상동

+set_symmetric_difference ; 차이 집합 (A-B , B-A). 다른 것들로 구성

상동 

++heap ; 정렬된 컨테이너. 검색이나 추가가 빠르다.

+make_heap(first, last (,comp)) ; 요소들을 재배열한다. first가 항상 최대값이 오게 한다.

std::make_heap(v.begin(), v.end()) ;

v.front() ==> 최대값.

+push_heap() ; 요소를 힙에 푸시함. [first, last-1)이 힙인데, last의 값을 힙에 포함시킨다. [first, last) 로 구간이 확장됨.

데이터 추가시

v.push_back(99) ;

std::push_heap(v.begin(), v.end()) ;    // 마지막에 추가한 99를 힙 영역에 넣는다.

+pop_heap() ; first가 가리키는 값을 힙에서 뺀다. first의 값은 가장 뒤로 가게 되고, 힙은 재구성됨.

데이터 제거시

std::pop_heap(v.begin(), v.end()) ;

v.pop_back() ;

+sort_heap() ;오름차순으로 힙을 소팅한다.

std::sort_heap(v.begin(), v.end()) ;

++min/max

+min() ; 작은값을 찾는다.

const T & min(const T&a, const T&b) 

const T & min(const T&a, const T&b, Compare comp)

std::min(1,2) ;

std::min('a','z') ;

+max() ; 큰값을 찾는다.

상동

+min_element() ; 범위에서 최소값을 찾는다. 이터레이터 리턴 주의

iterator min_element(first, last, (comp)) ;

*std::min_element(v.begin(), v.end()) ;    // 최소값

+max_element() ; 범위에서 최대값을 찾는다.

상동

+minmax() ; c++11 , 최소값, 최대값 결과를 pair로 리턴. 리스트도 가능.

auto result = std::minmax({5,4,3,2,1}) ;

result.first => 1

result.second => 5

+minmax_element() ; c++11 ; 최소위치, 최대위치 결과를 pair로 리턴. pair의 요소는 이터레이터

auto result = std::minmax_element( foo.begin(), foo.end() ) ;

*result.first => 최소값.  *result.second=>최대값.

+lexicographical_compare(first1, last1, first2, last2 (,comp)) ; 사전식 비교

char foo[]="Apple" ;

char bar[]="apartment" ;

std::lexicographical_compare(foo, foo+5, bar, bar+9);         // => true ; foo < bar

std::lexicographical_compare(foo, foo+5, bar, bar+9, mycomp);         // => false ; foo > bar

bool mycomp(char c1, char c2) { return std::tolower(c1)<std::tolower(c2) ; }     // case-insensitive compare

+next_permutation(first, last) ; 

lexicographically 큰 다음 순열로 재배열한다.

// myints; 1 2 3

std::next_permutation(myints, myints+3) ;

// 1 3 2 로 변경. 마지막 두 개를 변경.

// 게속 permutation 반복시 

// 2 1 3 ,  2 3 1,    3 1 2,  3 2 1,    1 2 3 (처음으로 다시 환원됨). n! 개의 순열

반대 방향은 prev_permutation()