Algorithm : Sorting

참고자료
c++.com : http://cplusplus.com/reference/
일반적프로그래밍과 STL책.

저도 잘 모르는 내용이지만 제 임의대로 제가 기억하려고 올리는 것이므로 태클 환영합니다.

Merge : 두개의 구간을 하나의 정렬된 구간으로 합침. 오름차순으로 정렬함 만약 구간1과 구간2의 값이 같다면, 구간1의 값이 앞에 배치됨. Set_union과 비슷하다. 그러나 set_union은 중복을 제거하고, merge는 제거하지 않음.

template <class InputIterator1, class InputIterator2, class OutputIterator>   OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,                          InputIterator2 first2, InputIterator2 last2,                          OutputIterator result ) {   while (true) {     *result++ = (*first2<*first1)? *first2++ : *first1++;     if (first1==last1) return copy(first2,last2,result);     if (first2==last2) return copy(first1,last1,result);   } }

 

Inplace_merge : 연속된 두 구간이 정렬되어있을 때, 그 둘을 하나의 정렬된 구간으로 만든다. 우선 하나로 합친 뒤, 정렬을 수행함. Compare comp는 optional함.

template <class BidirectionalIterator, class Compare>   void inplace_merge ( BidirectionalIterator first, BidirectionalIterator middle,                        BidirectionalIterator last, Compare comp );

 

 Includes : 정렬된 구간으로 표현되는 두 집합에 대해 한 집합이 다른 집합의 부분집합인지 리턴해줌. (comp는 optional)

template <class InputIterator1, class InputIterator2>   bool includes ( InputIterator1 first1, InputIterator1 last1,                   InputIterator2 first2, InputIterator2 last2 , Compare comp) {   while (first1!=last1)   {     if (*first2<*first1) break;     else if (*first1<*first2) ++first1;     else { ++first1; ++first2; }     if (first2==last2) return true;   }   return false; }

 

 

Set_union : 두 집합의 합집합을 만듦

template <class InputIterator1, class InputIterator2, class OutputIterator>   OutputIterator set_union ( InputIterator1 first1, InputIterator1 last1,                              InputIterator2 first2, InputIterator2 last2,                              OutputIterator result ) {   while (true)   {     if (first1==last1) return copy(first2,last2,result);     if (first2==last2) return copy(first1,last1,result);       if (*first1<*first2) *result++ = *first1++;     else if (*first2<*first1) *result++ = *first2++;     else { *result++ = *first1++; first2++; }   } }

 

Set_intersection : 두 집합의 교집합을 만듦. 교집합은 정렬된 구간임.

template <class InputIterator1, class InputIterator2, class OutputIterator>   OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,                                     InputIterator2 first2, InputIterator2 last2,                                     OutputIterator result ) {   while (first1!=last1 && first2!=last2)   {     if (*first1<*first2) ++first1;     else if (*first2<*first1) ++first2;     else { *result++ = *first1++; first2++; }   }   return result; }