Chapter 9. 알고리즘

*이 포스팅은 개인 학습을 위해 내용을 정리한 것이 목적입니다.

 

9.1 알고리즘 사용시 필요한 헤더 파일

 -<algorithm> : min(), max(), swap(), iter_swap()

 -<numeric> : 수치처리

 -<functional> : 함수객체나 함수어댑터

 

9.2 알고리즘에 대한 전반적인 소개

 9.2.1 알고리즘에 대한 간단한 소개.

  -모든 알고리즘은 하나 이상의 범위에 대해서 원소를 처리한다. 범위에 대해 유효함을 보장하여

   야 한다.

  -알고리즘을 보다 강력하고 유연한 사용을 위해 사용자 정의 조건자를 허락한다.

   1)사용자는 함수나 함수객체를 단항조건자의 형태로 검색 알고리즘의 기준으로 사용가능

   2)사용자는 함수나 함수객체를 이항조건자의 형태로 정렬 알고리즘의 기준으로 사용가능

   3)사용자는 함수나 함수객체를 단항조건자의 형태로 특정원소에 대해서 특정동작 적용가능

   4)사용자는 수치 알고리즘을 위해 수치연산을 제공할 수 있음.

  *모든 조건자들은 함수 호출에 대해 자신의 내부 상태를 변경하면 안됨

 

 9.2.2 알고리즘의 분류

  -알고리즘의 이름에 따른 간단한 표시

   1) _if()접미사

     _if접미사는 두 종류의 알고리즘이 존재하며, 동일한 개수의 인자를 받아들일 때 사용. 단, _if가

   없다면 value가 사용되고, _if가 있으면 함수 또는 함수객체가 사용됨.

   2) _copy()접미사

     _copy접미사는 원소를 변경할 뿐 아니라, 결과를 목적지 범위에 복사하여 전달.

 

 *이후 NOE는 NumberOfElements의 약어로 사용

 

9.4 for_each()알고리즘

 -for_each()알고리즘은 컨테이너의 원소를 다양한 방법으로 액세스,처리,수정하기에 유연하다.

 -UnaryProc for_each(InputIterator beg, InputIterator end, UnaryProc op)

  1) [beg,end)범위의 모든 원소에 대해 op(elem)을 호출

  2) op(내부적으로 수정된)의 복사본을 반환.

  3) op는 원소들을 수정할 수 있다. transform과 작동방식은 다르지만 같은 작업을 할 수 있다.

   * for_each는 원소 수정할 값을 인자로 받는다. 레퍼런스로 받아옴.

     transform은 수정된 값을 반환. value로 받아옴. 조금 더 느리나 더 유연함.(원본보존)

  4) op의 모든 반환값들은 무시된다. 선형 복잡도를 가짐 (NOE만큼 op호출됨)

for_each반환값예제

class MeanValue{  private:     long sum;     long num;  public:     MeanValue() : num(0), sum(0) {}     void operator() (int elem){        num++;        sum += elem;     }     operator double() { //캐스팅 연산자        return static_cast<double>(sum) / static_cast<double>(num);     }     operator int(){ return static_cast<int>(sum); }  };   void main(){     vector<int> col;     initCon(col, 1, 8);     double mv = for_each(col.begin(), col.end(), MeanValue());     cout << "mv : " << mv << endl;     int mv2 = for_each(col.begin(), col.end(), MeanValue()); //int형으로 캐스팅을 한다.     cout << "mv2: " << mv2 << endl; } 결과 mv: 4.5 mv2: 36

    > operator type() : 캐스팅 연산자. 이 캐스팅 연산자를 오버로딩 하면, 해당 타입으로 캐스팅이 일어날 때, 호출된다.   

 

9.5 원소를 수정하지 않는 알고리즘

 9.5.1 원소의 카운트

  *형태

   1) difference_type count(InputIterator beg, InputIterator end, const T& value)

   2) difference_type count_if(InputIterator beg, InputIterator end, UnaryPredicate op)

    - 1)형태의 알고리즘은 [beg,end) 범위 안에서 value와 동일한 값을 가지는 원소의 수 반환

    - 2)형태의 알고리즘은 [beg,end)범위 안에서 op를 만족하는 원소의 수 반환.

    - 반환값의 타입은 반복자의 difference_type.

    - op는 호출되는동안 자신의 상태변경, 전달된 인자수정을 하면 안됨.

    - 선형복잡도(NOE만큼 op호출). 컨테이너의 연관 함수는 count()

예제보기

bool isEven(int elem){ return (elem%2) == 0; } void counttest() {    vector<int> col;    int num;    insert_elems(col, 1,9);    print_elems(col, "col:");    num = count(col.begin(), col.end(), 4);    cout << num << endl;    num = count_if(col.begin(), col.end(), isEven);    cout << " even count " << num << endl;    num = count_if(col.begin(), col.end(), bind2nd(greater<int>(), 4));    cout << "num count " << num << endl; }

 

 

 9.5.2 최대/최소

  *형태

   1) InputIterator min_element(InputIterator beg, InputIterator end)

   2) InputIterator min_element(InputIterator beg, InputIterator end, CompFunc op)

   3) InputIterator max_element(InputIterator beg, InputIterator end)

   4) InputIterator max_element(InputIterator beg, InputIterator end, CompFunc op)

    - 위 알고리즘은 [beg,end)범위안 원소의 최대/최소값 위치를 반환

    - op인자가 없는버전(1,3)은 <를 이용하여 비교. op는 op(elem1, elem2)처럼 두 개의 인자를 받

     고 elem1이 작은경우 true를 반환해야 함

    - 최대/최소 값을 가지는 원소가 하나 이상 존재할 경우, 처음으로 발견된 원소의 위치를 반환

    - op는 전달된 인자를 수정하면 안됨

    - 선형복잡도 (NOE-1만큼 비교와 op호출)

예제)

bool absLess(int elem1, int elem2){ return abs(elem1) < abs(elem2) ; }  void minmaxtest(){     deque<int> col;     insert_elems(col, 2, 8);     insert_elems(col, -3, 5);     print_elems(col, "after init");     //최대최소     cout << "min:" << *min_element(col.begin(), col.end()) << endl;     cout << "max:" << *max_element(col.begin(), col.end()) << endl;     //절대값 최대최소     cout << "absmin:" << *min_element(col.begin(), col.end(), absLess);     cout << "absmax:" << *max_element(col.begin(), col.end(), absLess); }

    > max_element, min_element의 반환값은 반복자이므로 *를 붙여서 값을 얻어온다.

    > 마지막에 들어가는 함수는 이항연산자 함수가 들어가야 한다. (비교가 되어야 함)

 

 9.5.3 원소의 검색

  1) 검색 조건과 매치되는 첫 번째 원소의 검색

   *형태

    i) InputIterator find(InputIterator beg, InputIterator end, const T& value)

    ii) InputIterator find_if(InputIterator beg, InputIterator end, UnaryPredicate op)

     - [beg,end) 에서 i)형태는 value와 같은 값, ii)의 형태는 op의 조건에 맞는 첫 번째 원소의 위

      치를 반환. 없을 경우 end()반환됨

     - op는 호출되는동안 자신의 상태변경, 전달된 인자의 수정을 하면 안됨

     - 범위가 정렬되어 있다면, upper_bound, lower_bound, equal_range, binary_search를 사용

     - 선형복잡도. (NOE만큼 비교와 op호출)

     - 연관컨테이너도 동일한 멤버함수 제공하나 복잡도는 로그복잡도

  예제 

void findtest(){     list<int> col;     insert_elems(col, 1, 9);     insert_elems(col, 1, 9);     print_elems(col, "coll:");     list<int>::iterator pos1;     pos1 = find(col.begin(), col.end(), 10);     list<int>::iterator pos2;     if( pos1 != col.end()){        pos2 = find(++pos1, col.end(), 4);     }     if( pos1 != col.end() && pos2 != col.end()){        copy( --pos1, ++pos2, ostream_iterator<int>(cout, " "));        cout << endl;     } }

      > pos1을 찾지 못하면 잘못된 위치부터 검색을 하므로, pos2를 검색할 필요는 없다.

      > pos1을 찾았을 경우, pos2를 찾기 전에 pos1을 하나 증가해야 한다. (아니면 같은 값을 참조)

  

     find_if예제)

void findiftest()  {     vector<int> col;     vector<int>::iterator pos;     insert_elems(col, 1, 9);     print_elems(col, "init:");     pos = find_if(col.begin(), col.end(), bind2nd(greater<int>(),5));     cout << "the " << distance(col.begin(), pos) + 1 << ". element is first greater then 5" << endl;     pos = find_if(col.begin(), col.end(), not1(bind2nd(modulus<int>(),3)));     cout << "the " << distance(col.begin(), pos) + 1 << ". element is divisible by 3" << endl;  }

 

  2) 검색조건과 매치되는 원소들이 연속적으로 n회 나타나는 경우 검색

   *형태

    i) InputIterator search_n(InputInterator beg,InputIterator end, Size count, const T& value)

    ii) InputIterator search_n(InputInterator beg,InputIterator end, Size count, const T& value,

                                  BinaryPredicate op)

     - [beg,end) 범위에서 i)의 형태는 value와 같은 값이 count회 연속, ii)의 형태는 op의 조건에

      맞는 원소가 count개 연속되는 위치를 반환한다. 없을경우 end()반환

     - op는 호출되는동안 자신의 상태를 변경하면 안되고, 전달된 인자 수정도 안됨

     - 선형복잡도 (많아야 NOE*count만큼 비교와 op호출됨)

    예제

void searchntest()  {     deque<int> col;     insert_elems(col, 1, 9);     print_elems(col, "init:");     deque<int>::iterator pos;     pos = search_n(col.begin(), col.end(), 4, 3);     if( pos != col.end()){        cout << "4times start pos : " << distance(col.begin(),pos) + 1 << endl;     }     else{        cout << "not found" << endl;     }     pos = search_n(col.begin(), col.end(), 3,2, greater<int>()); //2보다 큰 수가 3회이상 나오는 경우     if( pos != col.end()){        cout << "greater then 5, start pos : " << distance(col.begin(),pos) + 1 << endl;     }     else{        cout << "greater then 5, start not found" << endl;     } }

      > 만약 데이터가 1~9까지 있고, search_n( beg, end, 3,5, less<int>()); 로 호출하면, 5보다 작은 수가 3회이상 연속으로 나타나는 지점을 반환받는다. 이 위치는 1부터 시작하므로, 반환값은 1임 

 

  3) 첫 번째 부분 범위의 검색

   *형태

    i) ForwardIterator1 search(ForwardIterator1 beg, ForwardIterator1 end,

                                    ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)

    ii) ForwardIterator1 search(ForwardIterator1 beg, ForwardIterator1 end,

                      ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)

     - [searchBeg,searchEnd)가 [beg,end)에 부분범위가 되는지 검사하고 부분범위가 시작되는 첫

      번째 부분의 위치를 반환. 찾지 못할경우 end()를 반환.

     - i)형태의 경우 원소의 비교는 ==, ii)형태의 경우 원소의 비교는 op(elem,searchElem)을 호출

     - op는 호출되는동안 자신의 상태를 변경하면 안되고, 전달된 인자 수정도 안됨

     - 선형복잡도 (많아야 NOE* NumberOfSearchElements만큼 비교와 op호출)

예제

void searchtest()  {     deque<int> col;     list<int> subcol;     insert_elems(col, 1, 9);     insert_elems(col, 1, 9);     insert_elems(subcol, 3, 6);     print_elems(col, "col:");     print_elems(subcol, "sub:");     deque<int>::iterator pos;     pos = search(col.begin(), col.end(), subcol.begin(), subcol.end());       while( pos != col.end()){        cout << "subcol found start with elem " << distance(col.begin(), pos) + 1 << endl;        ++pos; //subcol이 또 있는지 확인        pos = search(pos, col.end(), subcol.begin(), subcol.end());     } }

 

 

   4) 마지막 부분 범위 검색

    *형태

      i) ForwardIterator find_end(ForwardIterator beg, ForwardIterator end,

                                       ForwardIterator searchBeg, ForwardIterator searchEnd)

      ii) ForwardIterator find_end(ForwardIterator beg, ForwardIterator end,

                       ForwardIterator searchBeg, ForwardIterator searchEnd, BinaryPredicate op)

       - [searchBeg,searchEnd)가 [beg,end)에 부분범위가 되는지 검사하고 마지막 부분범위가 시

        작되는 위치를 반환. 찾지 못할경우 end()를 반환

       - i)형태는 ==, ii)형태는 op(elem,searchElem)이 true인 것을 조건으로 찾음

       - op는 호출되는동안 자신의 상태를 변경하면 안되고, 인자 수정도 안됨

       - 선형복잡도(최대 NOE*NumberOfSearchElements만큼 비교와 op호출)

예제)

void findend(){     deque<int> col;     list<int> subcol;     insert_elems(col, 1, 7);     insert_elems(col, 1, 7);     insert_elems(subcol, 3,6);     print_elems(col, "col");     print_elems(subcol, "subcol");     deque<int>::iterator pos;     pos = find_end(col.begin(), col.end(), subcol.begin(), subcol.end());     deque<int>::iterator end(col.end());     while( pos != end){       cout << "subcoll found at " << distance(col.begin(), pos) + 1 << endl;       end = pos;       pos = find_end(col.begin(), end, subcol.begin(), subcol.end());    } }

 

   5) 여러 개의 원소 검색

    *형태

      i) ForwardIterator find_first_of(ForwardIterator1 beg, ForwardIterator1 end,

                                           ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)

      ii) ForwardIterator find_first_of(ForwardIterator1 beg, ForwardIterator1 end,

                    ForwardIterator2 searchBeg, ForwardIterator2 searchEnd, BinaryPredicate op)

      - [beg,end) 범위 안에서 [searchBeg,searchEnd)범위에 속하는 값들을 검색. (find와 유사하

        나 값이 아닌 범위를 검색). 검색되지 않으면 end()반환

      - i)형태는 ==, ii)형태는 op(elem,searchElem)이 true를 조건으로 원하는 원소를 찾음.

      - op는 호출되는동안 자신의 상태의 변경, 전달된 인자의 변경이 허용되지 않음

      - 역방향 반복자를 사용하여 검색된 결과의 마지막 위치를 찾아낼 수 있음.

      - 선형복잡도(최대 NOE*NumberOfSearchElements만큼 비교와 op호출)

예제)

void findfirstoftest(){    vector<int> col;    list<int> scol;    insert_elems(col, 1, 11);    insert_elems(col, 1, 11);    insert_elems(scol, 3, 5);    print_elems(col, "col");    print_elems(scol, "scol");    vector<int>::iterator pos;    pos = find_first_of(col.begin(), col.end(), scol.begin(), scol.end());    cout << " pos : " << distance(col.begin(), pos) + 1 << endl;    vector<int>::reverse_iterator rpos;    rpos = find_first_of( col.rbegin(), col.rend(), scol.begin(), scol.end());    cout << " last pos : " << distance(col.begin(), rpos.base()) << endl; }

   > find_first_of는 역방향 반복자를 통해 검색을 할 수 있다. (뒤에서부터 검색). 역방향의 경우 마지막 포지션이 반환됨

 

   6) 연속 중복 원소의 검색

    *형태

      i) InputIterator adjacent_find(InputIterator beg, InputIterator end)

      ii) InputIterator adjacent_find(InputIterator beg, InputIterator end, BinaryPredicate op)

       - [beg, end)범위에서 i)형태는 첫 번째 연속 중복 원소의 위치를 반환하고, ii)의 형태는 op

        (elem,nextElem)이 true를 반환하는 원소가 연속적으로 나타나는 위치의 첫 번째 위치를 반

        환. 찾지 못할 경우 end()호출됨

      - op는 호출되는 동안 자신의 상태의 변경, 전달된 인자의 변경이 허용되지 않음

      - 선형복잡도.(최대 NOE만큼 비교)

예제

bool doubled(int elem1, int elem2){    return (elem2 == elem1*2);  }  void adjacentfindtest(){    vector<int> col;    col.push_back(1);    col.push_back(7);    col.push_back(3);    col.push_back(8);    col.push_back(8);    col.push_back(0);     col.push_back(2);     col.push_back(4);     col.push_back(5);    print_elems(col, "init");    vector<int>::iterator pos;    pos = adjacent_find(col.begin(), col.end());    if( pos !=col.end()){       cout << "duplicate at " << distance(col.begin(), pos) + 1 << endl;    }    pos = adjacent_find(col.begin(), col.end(), doubled);    if( pos != col.end()){       cout << "2times at " << distance(col.begin(), pos) + 1 << endl;    } }

    > adjacent_find의 경우 이항연산자 결과가 true인 경우의 위치를 반환. 다만, 기본으로 설정된 이항연산자가 '=='인것.

  

 9.5.4 범위 비교

  1)동일성 검사

   *형태

    i) bool equal(InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)

    ii) bool equal(InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg,

                    BinaryPredicate op)

     - [beg,end)범위에서, i)의 경우 cmdBeg위치에서 시작하는 범위의 원소가 같은지를 판단, ii)의

      경우에는 cmpbeg에서 시작하는 원소가 같은지 판단

     - op가 호출되는 동안 자신의 상태변경, 전달된 인자의 변경  허용안됨

     - 두 시퀀스가 다름을 판단하기 위해서는 mismatch()알고리즘 사용

     - 선형복잡도(최대 NOE만큼 비교와 op호출)

예제)

void equaltest(){     vector<int> col1;     list<int> col2;     insert_elems(col1, 1,7);     insert_elems(col2, 3,9);     print_elems(col1, "col1");     print_elems(col2, "col2");     if( equal(col1.begin(), col1.end(), col2.begin())){        cout << "same" << endl;     }     else{        cout << "not same" << endl;     }     if( equal(col1.begin(), col1.end(), col2.begin(), bothEvenOdd) ){        cout << "even, odd elems correspond" << endl;     }     else{        cout << "even, odd elems not correspond" << endl;     } }

    > 다음과 같은 실행 결과가 나왔다.

col1범위	col2범위	equal결과	equal+evenodd결과
1,7	3,9	not same	correspond
1,11	1,9	not same	not correspond
1,7	1,9	same	correspond
3,7	1,9	not same	correspond

     col1과 col2가 시작이 같고, col2의 범위가 같거나 넓으면 equal의 결과는 same. equal + evenodd는 홀,짝 범위가 교대로 나타나면 correspond이다. 단, col1의 범위가 col2의 범위보다 클 경우 둘 다 not.

 

  2) 두 범위에서 다른 값의 존재 여부 검색

   *형태

     i) pair<InpuIterator1,InputIterator2> mismatch(InputIterator1 beg, InputIterator1 end,

                                                             InputIterator2 cmpBeg)

     ii) pair<InpuIterator1,InputIterator2> mismatch(InputIterator1 beg, InputIterator1 end,

                                                             InputIterator2 cmpBeg, BinaryPredicate op)

     - i)형태는 두 범위에 속하는 원소들을 서로 대응하는 원소끼리 비교하여 서로 일치하지 않는

     첫 번째 pair를 반환. ii)형태는 두 범위에 속하는 원소들을 비교하여 서로 일치하지 않는 첫

     pair를 반환.

     - 다른점이 없으면 pair의 first는 첫 범위의 end, second는 첫 범위의 end에 대응되는 위치를

     반환. 그러나 이것이 두 시퀀스가 동일함을 의미하지는 않음.

     - op는 호출되는 동안 자신의 상태변경, 전달된 인자의 수정은 안된다.

     - 호출자는 cmpBeg로 시작되는 컨테이너가 하나 이상의 원소를 가지고 있다는 사실을 보장해

      야함. 두 시퀀스의 같음을 판단하기 위해서는 equal을 사용

     - 선형복잡도(최대 NOE만큼 비교와 op호출)

예제

void mismatchtest(){     vector<int> col1;     list<int> col2;     insert_elems(col1, 1,6);     for( int i = 1 ; i <= 16 ; i *= 2){        col2.push_back(i);     }     col2.push_back(3);     print_elems(col1, "col1");     print_elems(col2, "col2");     pair<vector<int>::iterator, list<int>::iterator> values;     values = mismatch(col1.begin(), col1.end(), col2.begin());     if( values.first == col1.end()){        cout << "no mismatch" << endl;     }     else{        cout << "mismatch found " << *values.first << ",and " << *values.second << endl;     }     values = mismatch(col1.begin(), col1.end(), col2.begin(), less_equal<int>());     if( values.first == col1.end()){        cout << "always less-equal" << endl;     }     else{        cout << "not less-or-equal " << *values.first << ",and " << *values.second << endl;     } }

     > mismatch의 경우 조건에 맞지 않는 경우의 위치(index를 pair로 반환한다.)

     > 여기서 범위의 경우. col1의 범위보다 col2의 범위가 같거나 커야 한다. mismatch조건을 찾지 못하고 다음으로 넘어갈 때, col2에 원소가 없는 경우 예상치 못한 비교 결과가 나온다.

 

  3) 사전식 방법으로 적은지를 판단

   *형태

     i) bool lexicographical_compare(InputIterator1 beg1, InputIterator1 end1,

                                            InputIterator2 beg2, InputIterator2 end2)

     ii) bool lexicographical_compare(InputIterator1 beg1, InputIterator1 end1,

                                            InputIterator2 beg2, InputIterator2 end2, CompFunc op)

     - [beg1,end1) 범위의 원소들이 [beg2,end2)범위의 원소보다 사전식으로 비교했을 때, 적은지

     판단. i)형태는 <비교, ii)형태는 op(elem1, elem2)를 사용(elem1이 작으면 true)

     - 사전식 비교 : 다음과 같은 상황에서 계속하여 시퀀스를 원소대 원소로 비교하는 것을 의미

      a) 두 개의 원소가 같지 않다면, 이 비교의 결과는 전체 비교의 결과가 된다.

      b) 하나의 시퀀스에 더 이상의 원소가 없으면 이 시퀀스는 다른 시퀀스보다 작은 원소가 더 

        이상 없음. 따라서, 첫번째 시퀀스가 더 이상 원소를 가지고 있지 않으면 비교는 true

      c) 두 시퀀스 모두 더 이상의 원소가 없으면 동일한 것. 이경우는 false

     - op는 함수가 호출되는 동안 자신의 상태변경, 전달된 인자의 수정은 안됨

     - 선형복잡도(최대 2*min(NOE1, NOE2)만큼 비교와 op호출

예제)

void printCollection(const list<int>& l){     print_elems(l);  }  bool lessForCollection(const list<int>& l1, const list<int>& l2){     return lexicographical_compare(l1.begin(), l1.end(), l2.begin(), l2.end());  }  void lexicographicaltest(){     list<int> c1, c2, c3, c4;     insert_elems(c1, 1,5);     c4 = c3 = c2 = c1;     c1.push_back(7);     c2.push_back(2);     c3.push_back(0);     c4.push_back(2);     vector<list<int> > cc;     cc.push_back(c1);     cc.push_back(c2);     cc.push_back(c3);     cc.push_back(c4);     cc.push_back(c3);     cc.push_back(c1);     cc.push_back(c4);     cc.push_back(c2);     for_each(cc.begin(), cc.end(), printCollection);      cout << endl;     sort(cc.begin(), cc.end(), lessForCollection);     for_each(cc.begin(), cc.end(), printCollection); }  결과  1 2 3 4 5 7                  1 2 3 4 5 0  1 2 3 4 5 2                  1 2 3 4 5 0  1 2 3 4 5 0                  1 2 3 4 5 2  1 2 3 4 5 2 2         ->   1 2 3 4 5 2  1 2 3 4 5 7                  1 2 3 4 5 2 2  1 2 3 4 5 2                  1 2 3 4 5 2 2  1 2 3 4 5 0                  1 2 3 4 5 7  1 2 3 4 5 2 2               1 2 3 4 5 7

     > printCollection을 추가로 만든 이유 : for_each문에 들어갈 함수는, 인자로 list<int>가 필요하기에 만들었다. 템플릿은 함수 인자로 사용이 안됨 (error C2896발생)

     > vector<list<int> > : 벡터안에 리스트가 올라갈 수 있다. (컨테이너는 컨테이너를 얹을 수 있다.) 주의할 사항은 >가 붙어있지 않아야 한다.

     > lexicographical은 사전식 정렬을 한다. (결과 참조)

 

9.6 원소를 수정하는 알고리즘

 원소를 수정하는 방법에는 다음과 같이 2가지가 있음

  i)시퀀스를 순회하면서 직접 수정

  ii)소스 범위에서 목적지 범위로 복사하는 동안 수정

 

 9.6.1 원소의 복사

  *형태

   i) OutputIterator copy(InputIterator srcBeg, InputIterator srcEnd, OutputIterator dstBeg)

   ii) BidirectionalIterator1 copy_backward(BidirectionalIterator1 srcBeg,

                                       BidirectionalIterator1 srcEnd, BidirectionalIterator2 dstEnd)

    - [srcBeg,srcEnd)의 모든 원소를 목적지 범위로 복사. i)은 dstBeg에서 시작하고 ii)는 dstEnd로

    끝남. 반환값은 마지막 원소가 복사된 이후의 위치를 반환.

      [first1,last1)에서 [first2,last2)로 복사된다면, i)은 last2 반환, ii)는 first2를 반환함

    - dstBeg나 dstEnd는 [srcBeg, srcEnd)에 속하면 안된다. 소스 범위와 목적지 범위가 중복되지

     않도록 해야한다. copy()알고리즘은 정방향 순회, copy_backward()는 역방향 순회.

     *범위가 중복 될 경우, 소스가 목적지보다 뒤쪽에 존재하면 copy를, 소스가 목적지보다 앞에

     존재하면 copy_backward를 사용하자. 즉, 3번째 인자가 1,2번째 인자 사이에 없도록 할 것.

    - 만약 3번째 인자가 1,2번째 인자사이에 있을 경우 다른 알고리즘을 사용한다.

      i) copy_if()는 존재하지 않는다. 조건에 맞는 원소만 복사하기를 원하면 remove_copy_if()사용

      ii) 소스 원소의 순서를 반대로 하여 복사하려면 reverse_copy()를 사용

    - 호출자는 목적지 범위가 충분히 크거나 삽입반복자를 사용하는 것을 보장

    - 컨테이너 모든 원소의 할당을 위해 할당연산자나 assign() 멤버함수가 사용됨

    - 복사하는 동안 원소를 제거하고 싶으면 remove_copy(), remove_copy_if()를 사용

    - 복사하는 동안 원소를 수정하고 싶으면 transform()이나 replace_copy()를 사용

    - 선형복잡도(최대 NOE만큼 할당)

예제) copy

void copytest(){     vector<int> col1;     list<int> col2;     insert_elems(col1, 1,9);     copy(col1.begin(), col1.end(), back_inserter(col2));     print_elems(col2);     copy(col1.rbegin(), col1.rend(), col2.begin() );     print_elems(col2); }

 

 

  예제) copy_backward

void copybackward(){     vector<char> source(10, '.');     for( int i = 'a' ; i <= 'f' ; i++){       source.push_back(i);     }     source.insert(source.end(), 10, '.');     print_elems(source, "sr");     vector<char> c1(source.begin(), source.end());     copy(c1.begin()+10, c1.begin() + 16, c1.begin()+7);     print_elems(c1, "c1");     vector<char>c2(source.begin(), source.end());     copy_backward(c2.begin() + 10, c2.begin() + 16, c2.begin()+19);     print_elems(c2, "c2"); }

    > copy_backward나 copy나 목적지범위와 소스범위가 일부 겹치는 것은 괜찮다. (동작한다.) 단, 일부 겹칠 경우, 겹쳐지 않는 영역은 기존의 값이 남아있음에 유의.

    > copy_backward는 뒤에서 부터 앞쪽으로 n칸 떨어진 위치에 복사하는 것.  복사 기준 점은 역방향으로 첫 번째 위치가 리턴된다. 위의 예를 들면 메인  col에 a - f가 포함되어있고 이를 copy하면 a~f가 복사된다. c2.begin() + 19위치는 f위치가 들어갈 위치를 의미하다.

 

 9.6.2 원소의 변경 또는 결합

   transform()알고리즘은 두 가지 형태를 가진다.

    i) 4개의 인자, 소스범위의 원소를 목적지 범위로 이동. 복사와 수정이 한번에 이루어짐

    ii) 5개의 인자, 두 소스 시퀀스에서 원소를 조합하고 목적지 범위에 결과 기록

   1)원소의 변경

    *형태

     OutputIterator transform(InputIterator srcBeg, InputIterator srcEnd, OutputIterator dstBeg,

                                   UnaryFunc op)

     - [srcBeg, srcEnd)의 각각의 원소에 대해 op(elem)이 호출됨. op의 결과를 목적지 범위에 기록

     - 마지막 이동된 원소 이후의 위치를 반환.

     - 호출자는 목적지 범위가 충분한 공간을 가지거나 삽입 반복자를 사용하는 것을 보장해야함

     - srcBeg, dstBeg의 범위는 동일할 수 있다. 따라서 for_each()와 같이 시퀀스안에서 원소를 수

      정하는데 사용 가능하다. 특정 기준에 매치되는 원소만 변경하고 싶으면 replace()사용

     - 선형복잡도(최대 NOE만큼 op호출)

   예제)

void transformtest1(){    vector<int> col1;    list<int> col2;    insert_elems(col1, 1,9);    print_elems(col1, "col1");    transform(col1.begin(), col1.end(), col1.begin(), negate<int>());    print_elems(col1, "negate");    transform(col1.begin(), col1.end(), back_inserter(col2), bind2nd(multiplies<int>(),10));    //col2.begin()반복자를 주면 삽입이 안됨.    print_elems(col2, "multiplies");    transform(col2.rbegin(), col2.rend(), ostream_iterator<int>(cout, " "), negate<int>());    cout << endl;  }

   2) 두 시퀀스 원소의 결합

    *형태

     OutputIterator transform(InputIterator1 src1Beg, InputIterator1 src1End,

                                     InputIterator2 src2Beg, OutputIterator dstEnd, BinaryFunc op)

     - 첫 번째 소스범위 [src1Beg, src1End)와 두 번째 소스범위 src2Beg부터 대응되는 모든 원소

      에 대해 op(src1Elem, src2Elem)을 호출. 목적지에서 마지막으로 이동된 원소이후의 위치 반환

     - 호출자는 두 번째 소스 범위가 충분한 공간을 가짐, 목적지가 충분한 공간을 가지거나 삽입

      반복자를 사용한다는 사실을 보장해야 함

     - src1Beg, src2Beg, dstBeg의 범위는 동일할 수 있음. 자기자신의 원소를 op로 수정하여 자기

      자신의 범위에 덮어쓸 수 있음.

     - 선형복잡도 (최대 NOE만큼 op호출)

예제)

void squaretest(){    vector<int> col1;    list<int> col2;    insert_elems(col1, 1, 9);    print_elems(col1, "col1");    transform( col1.begin(), col1.end(), col1.begin(),col1.begin(), multiplies<int>() );    print_elems(col1, "squared");    transform(col1.begin(), col1.end(), col1.rbegin(), back_inserter(col2), plus<int>());    print_elems(col2, "col2");    cout<< "diff:";    transform(col1.begin(), col1.end(), col2.begin(), ostream_iterator<int>(cout," "), minus<int>());    cout << endl; }

   > op가 BinaryFunc여야 에러가 발생하지 않는다.

 

 9.6.3 원소의 교체

  *형태

    ForwardIterator2 swap_ranges(ForwardIterator1 beg1, ForwardIterator1 end1, 

                                         ForwardIterator2 beg2)

     - [beg1, end1)의 범위의 원소들을 beg2로 시작하는 원소들과 교체한다.

     - 두 번째 범위에서 마지막으로 교체된 원소 이후의 위치를 반환한다.

     - 호출자는 두 번째 소스 범위가 충분한 공간을 가지고 있음을 보장해야 함

     - 범위는 중복되지 않아야 함. 컨테이너 타입이 동일하면 swap멤버함수를 사용 (상수복잡도)

     - 선형복잡도(NOE만큼 교체)

 예제)

void swaptest(){    vector<int> col1;    deque<int> col2;    insert_elems(col1, 1, 9);    insert_elems(col2, 11, 23);    print_elems(col1,"col1");    print_elems(col2, "col2");    deque<int>::iterator pos;    pos = swap_ranges(col1.begin(), col1.end(), col2.begin());    print_elems(col1, "sw col1");    print_elems(col2, "sw col2");    if( pos != col2.end()){      cout << "1st elem not modified " << *pos << endl;    }      swap_ranges(col2.begin(), col2.begin() + 3, col2.rbegin());    print_elems(col2, "col2 sw"); }

     > col1의 [beg,end)까지의 구간과 대상의 구간을 swap. col2는 col1보다 같거나 큰 범위를 가져야 함. (반대일 경우 swap후 이상한 값이 들어감). 또한, 마지막 swap에서 rbegin이 시작인데 rbegin()++은 rbegin보다 하나 앞의 원소를 가리키므로 역순으로 3개 swap함

 

 9.6.4 새로운 값의 할당

  1) 동일한 값의 할당

    *형태

     i) void fill(ForwardIterator beg, ForwardIterator end, const T& newValue)

     ii) void fill_n(OutputIterator beg, Size num, const T& newValue)

       - fill알고리즘은 [beg,end)범위, fill_n알고리즘은 [beg,beg+num)범위의 모든 원소에

        newValue를 할당함. 호출자는 목적지 범위가 충분한 공간을 가지고 있다는 것을 보장할 것

       - 선형복잡도(NOE또는 num만큼 할당이 일어남)

    예제)

void filltest(){     fill_n(ostream_iterator<int>(cout, " "), 10, 7.7);     cout << endl;     list<string> col;     fill_n(back_inserter(col), 9, "hello");     print_elems(col, "col");     fill(col.begin(), col.end(), "again");     print_elems(col, "col ag");     fill_n(col.begin(), col.size()-2, "hi");     print_elems(col, "col");     list<string>::iterator pos1, pos2;     pos1 = col.begin();     pos2 = col.end();     fill( ++pos1, --pos2, "hmm");     print_elems(col, "last");  }

    > fill 및 fill_n 소스와 목적지 범위가 일치해도 괜찮다. (transform과 비슷하다.)

    > 목적지 범위가 제대로 보장이 안될 경우 예상하지 못한 결과를 만들 수 있다. (end를 몇 iter넘기니까 결과값이 이상해짐.

 

  2) 생성된 값을 할당

    *형태

     i) void generate(ForwardIterator beg, ForwardIterator end, Func op)

     ii) void generate_n(OutputIterator beg, Size num, Func op)

       - op에 의해 생성된 값을, generate는 [beg,end)범위, generate_n은 [beg, beg_num)범위의

       모든 원소에 할당.

       - 호출자는 목적지에 충분한 공간이 있거나 삽입반복자를 사용함을 보장해야 함

       - 선형복잡도(NOE또는 num만큼 할당 일어남)

 

 9.6.5 원소의 교체

  1)시퀀스 안의 원소들의 값을 교체

   *형태

    i) void replace(ForwardIterator beg, ForwardIterator end, const T& oldVal,

                     const T& newVal)

    ii) void replace_if(ForwardIterator beg, ForwardIterator end, UnaryPredicate op,

                     const T& newVal)

     - [beg,end)범위에서 replace는 oldVal값을 가지는 모든 원소에, replace_if는 op가 true가되는 

     모든 원소에 newVal을 할당.

     - op는 호출되는 동안 자신의 상태를 변경해서는 안됨

     - 선형복잡도(NOE만큼 비교와 op호출)

 

예제

void replacetest(){     list<int> col;     insert_elems(col, 2,7);     insert_elems(col, 4, 9);     print_elems(col, "col");     replace_if(col.begin(), col.end(), bind2nd(less<int>(),5),0);      print_elems(col, "replaces"); }

 

 

  2)원소의 복사 후 교체

   *형태

    i)OutputIterator replace_copy(InputIterator srcBeg, InputIterator srcEnd,

                                        OutputIterator dstBeg, const T& oldVal, const T& newVal)

    ii)OutputIterator replace_copy_if(InputIterator srcBeg, InputIterator srcEnd,

                                      OutputIterator dstBeg, UnaryPredicate op, const T& newVal)

     - replace_copy()는 replace()와 copy()를 합친 것, [beg,end)범위에서 oldVal과 같은 값을 가지

      는 원소를 newVal로 교체. 단 원소들은 dstBeg의 목적지 범위에 기록됨

     - replace_copy_if()는 replace_if()와 copy()를 합친 것, [beg,end)범위에서 op가 true인 원소를

      newVal로 교체. 원소들은 dstBeg의 목적지 범위에 기록됨.

     - 반환값은 마지막 복사된 원소 이후의 위치. 호출자는 목적지 범위가 충분한 공간을 가지고

      있거나 삽입 반복자를 사용함을 보장.

     - op는 호출되는 동안 자신의 상태를 변경하면 안됨

     - 선형복잡도(NOE만큼 비교와 io호출, 할당)

   예제)

void repcopy(){     list<int> col;     insert_elems(col, 2, 6);     insert_elems(col, 4,9);     print_elems(col);     replace_copy(col.begin(), col.end(), ostream_iterator<int>(cout," "),5,55);     cout << endl;     replace_copy_if(col.begin(), col.end(), ostream_iterator<int>(cout, " "), bind2nd(less<int>(), 5), 42);     cout << endl;     replace_copy_if(col.begin(), col.end(), ostream_iterator<int>(cout, " "), bind2nd(modulus<int>(),2), 0);     cout << endl;  }

   > replace_copy의 경우 원본을 바로 조작한 후 복사하는 것이 아님. 원본은 유지됨 

 

9.7 제거 알고리즘

 9.7.1 특정 값을 지닌 원소의 제거

  1) 시퀀스 안의 원소들을 제거

   *형태

    i) ForwardIterator remove(ForwardIterator beg, ForwardIterator end, const T& value)

    ii) ForwardIterator remove_if(ForwardIterator beg, ForwardIterator end, UnaryPredicate op)

     - [beg, end)범위에서 remove는 value와 같은 값을 가지는 원소, remove_if는 op가 true인 원

     소를 제거하고, 수정된 시퀀스의 논리적 마지막 위치를 반환한다. 또한 제거된 원소들을 제거

     되지 않은 다음의 원소로 덮어쓴다.

     - 제거되지 않은 원소의 순서는 동일하게 유지된다.

     - 원래 컨테이너의 끝 위치는 변하지 않음. 따라서 논리적인 끝을 사용하는 것은 호출자의 몫

     - op는 함수가 호출되는동안 자신의 상태를 변경하면 안됨.

     - remove_if()는 대부분의 경우 알고리즘 안에서 단항조건자를 복사하여 사용함.

     - 연관컨테이너와 사용할 수 없음(원소가 수정되므로), 대신 erase()멤버함수를 제공함. list의

       경우 remove()멤버함수로 더 좋은 성능을 보장함

     - 선형복잡도.( NOE만큼 비교 또는 op호출)

예제)

void removetest() {    vector<int> col;    insert_elems(col, 2,6);    insert_elems(col, 4,9);    insert_elems(col, 1,7);    print_elems(col, "col");    vector<int>::iterator pos;    pos = remove(col.begin(), col.end(), 5);    print_elems(col, "size not changed");    col.erase(pos, col.end());    print_elems(col, "size change");    col.erase(remove_if(col.begin(), col.end(), bind2nd(less<int>(), 4)), col.end());    print_elems(col, "removed");  }

 

  2)원소의 제거 결과를 복사하여 전달

   *형태

     i) OutputIterator remove_copy(InputIterator srcBeg, InputIterator srcEnd,

                                         OutputIterator dstBeg, const T& value)

     ii) OutputIterator remove_copy_if(InputIterator srcBeg, InputIterator srcEnd,

                                         OutputIterator dstBeg, UnaryPredicate op)

      - remove_copy()는 copy()와 remove()를 결합. [beg, end)범위에서 value와 동일한 값을 가지

       는 원소를 제거하고, 결과는 dstBeg로 시작되는 범위에 복사되어 기록됨

      - remove_copy_if()는 copy()와 remove_if()를 결합. [beg, end)범위에서 op가 true인 원소를

       제거하고, 결과는 dstBeg로 시작되는 범위에 복사되어 기록됨

      - 목적지 범위에서 마지막으로 복사된 원소의 다음 위치를 반환. 호출자는 목적지에 충분한

       공간이 있거나 삽입 반복자를 사용함을 보장할 것

      - op는 호출되는 동안 자신의 상태를 변경해서는 안됨

      - 선형복잡도(NOE만큼 비교또는 op호출,그리고 할당이 이루어짐)

예제)

void removecopy(){    list<int> col1;    insert_elems(col1, 1,6);    insert_elems(col1, 1,9);    print_elems(col1);    remove_copy(col1.begin(), col1.end(), ostream_iterator<int>(cout, " "), 3);    cout << endl;    remove_copy_if(col1.begin(), col1.end(), ostream_iterator<int>(cout, " "), bind2nd(greater<int>(),4));    cout << endl;    multiset<int> col2;    remove_copy_if(col1.begin(), col1.end(), inserter(col2, col2.end()), bind2nd(less<int>(),3));    print_elems(col2); }

 

 9.7.2 중복된 원소의 제거

  1)연속 중복된 원소의 제거

    *형태

     i) ForwardIterator unique(ForwardIterator beg, ForwardIterator end)

     ii) ForwardIterator unique(ForwardIterator beg, ForwardIterator end, BinaryPredicate op)

       - unique()알고리즘은 [beg,end)범위에서 연속 중복인 원소를 제거한다. i)형태는 ==연산자

        로, ii)형태는 op(elem,e)==true인 원소를 제거한다. ii)형태는 조건자는 선행작업에 사용된 

        원소와 비교하지 않고, 제거되지 않은 전 원소와 비교된다. 수정된 시퀀스의 논리적 끝 위치

        반환.

       - 제거된 원소들을 제거되지 않은 다음의 원소로 덮어씀. 제거되지 않은 원소의 순서는 유지

        됨. 물리적으로 삭제되지 않았기에 논리적 끝 위치를 사용하는 것은 호출자의 몫임

       - list의 경우 unique()멤버함수가 더 좋음. 이 알고리즘은 연관컨테이너와 사용 못함.

       - 선형복잡도(NOE만큼 비교 또는 op가 호출됨)

     예제)   

void uniquetest(){     int source[] = { 1, 4, 4, 6, 1, 2, 2, 3, 1, 6, 6, 6, 5, 7, 5, 4, 4 };     int sourceNum = sizeof(source) / sizeof(source[0]);     list<int> col;     copy(source, source +sourceNum, back_inserter(col));     print_elems(col, "init");     list<int>::iterator pos;     pos = unique(col.begin(), col.end()); //실제 삭제는 안됨.     copy(col.begin(), pos, ostream_iterator<int>(cout, " "));     cout << endl;     copy(source, source+sourceNum, col.begin());     print_elems(col, "copy");     col.erase(unique(col.begin(), col.end(), greater<int>()), col.end());     print_elems(col); }

      > unique는 remove처럼 실제 데이터 삭제가 아닌 논리 데이터 삭제만 발생

 

  2)중복 원소의 제거 결과를 복사하여 전달

    *형태

     i)OutputIterator unique_copy(InputIterator srcBeg, InputIterator srcEnd,

                                        OutputIterator dstBeg)

     ii)OutputIterator unique_copy(InputIterator srcBeg, InputIterator srcEnd,

                                        OutputIterator dstBeg, BinaryPredicate op)

      - 둘 다 copy()와 unique()를 결합. [srcBeg, srcEnd)의 모든 원소를 dstBeg의 목적지 범위에

       복사한다. 단, 연속중복은 제거됨. 마지막복사된 원소 이후의 위치를 반환

      - 호출자는 목적지 범위가 충분한 공간을 가지고 있음을 보장해야함

      - 선형복잡도(NOE만큼 비교 또는 op호출, 그리고 할당이 이루어짐)

예제)

void uniqcopytest(){     int src[] = {1,4,4,6,1,2,2,3,1,6,6,6,5,7,5,4,4};     int srcNum = sizeof(src)/sizeof(src[0]);     list<int> col;     copy(src, src+srcNum,back_inserter(col));     print_elems(col, "src");     unique_copy(col.begin(), col.end(), ostream_iterator<int>(cout, " "));     cout << endl;     unique_copy(col.begin(), col.end(), ostream_iterator<int>(cout, " "), differenceOne);     cout << endl;  } 결과  1 4 4 6 1 2 2 3 1 6 6 6 5 7 5 4 4  1 4 6 1 2 3 1 6 5 7 5 4  1 4 4 6 1 3 1 6 6 6 4 4

   > 두번째 unique의 결과에서 주의할 점은, 6 1 2 2 3 1 6 구간. 여기서 6과 1은 차이가 1이상이어서 남아있으나, 1과 2는 1이 차이나서 제거된다. 그리고나서 다음번에 나오는 2의 비교는 앞의 제거된 2가 아닌 1과 비교를 하여 제거되고, 그 다음 나타나는 3은 다시 1과 비교하여 차이가 1이상이어 1이 남게 된다. (이후는 3과의 비교를 수행)

 

9.8 변경 알고리즘

 9.8.1 원소의 순서를 반전

  *형태

    i) void reverse(BidirectionalIterator beg, BidirectionalIterator end)

    ii) OutputIterator reverse_copy(BidirectionalIterator srcBeg, BidirectionalIterator srcEnd,

                                        OutputIterator dstBeg)

      - reverse()는 [beg,end)범위 안의 원소들을 뒤집는다. reverse_copy()는 [srcBeg, srcEnd)범위

       안의 원소들을 뒤집어 dstBeg로 시작하는 목적지 범위에 복사함

      - reverse_copy()는 마지막 복사된 원소 이후의 위치를 반환.

      - 호출자는 목적지 범위가 충분한 공간을 가지고 있거나 삽입 반복자를 사용함을 보장할 것

      - 선형복잡도.( NOE/2만큼 교환이 이루어지거나 NOE만큼 할당이 이루어짐)

      - list의 경우 reverse()멤버함수가 더 좋은 성능을 냄

예제)

void reversetest(){     vector<int> col;     insert_elems(col, 1,9);     print_elems(col, "col");     reverse(col.begin(), col.end());     print_elems(col, "rev");     reverse(col.begin() +1, col.end()-1);     print_elems(col, "rv2");     reverse_copy(col.begin(), col.end(), ostream_iterator<int>(cout," "));     cout << endl;     reverse(col.begin(), col.end());     copy( col.begin(), col.end(), ostream_iterator<int>(cout, " "));     cout << endl; }

   > reverse는 범위 안의 데이터들을 순서를 반전. reverse_copy는 반전된 순서를 특정 지역에 복사한다. 단, reverse는 원본의 순서가 변경되지만, reverse_copy는 원본의 순서는 유지된다. 그리고 reverse_copy는 reverse후 copy를 수행한 것과 동일한 결과

 

 9.8.2원소의 회전

  1)시퀀스 안의 원소들을 회전

   *형태

    void rotate(ForwardIterator beg,ForwardIterator newBeg, ForwardIterator end)

     - [beg,end)범위 안의 원소들을 회전시킴. newBeg이 새로운 첫번째 원소가 됨

     - 호출자는 newBeg이 [beg,end)범위에 유효함을 보장해야 함.

     - 선형복잡도(최대 NOE만큼 교체가 일어남)

예) rotate

 

void rotatetest(){     vector<int> col;     insert_elems(col, 1, 9);     print_elems(col, "init ");     rotate(col.begin(), col.begin()+1, col.end());     print_elems(col, "left1");     rotate(col.begin(), col.end()-2, col.end());     print_elems(col, "2rght");     rotate(col.begin(), find(col.begin(),col.end(), 4), col.end());     print_elems(col, "1st.4");  }

   > rotate에서는 기준되는 index를 기준으로 회전. (기준 앞은 뒤로 이동)

 

 

  2)회전된 원소의 결과를 복사하여 전달

   *형태

    OutputIterator rotate_copy(ForwardIterator srcBeg, ForwardIterator newBeg,

                                    ForwardIterator srcEnd, OutputIterator dstBeg)

     - rotate()와 copy()가 결합된 것. [srcBeg, srcEnd)범위 안에 원소들을 회전, 결과는 dstBeg에

      복사된다. 마지막으로 복사된 원소의 다음 위치를 반환함.

     - 호출자는 newBeg이 [srcBeg,srcEnd)범위 안에서 유효한 위치라는 사실을 보장해야함. 또한,

      목적지 범위가 충분한 공간을 가지고 있거나, 삽입 반복자를 사용하는 것을 보장해야함.

     - 소스 범위와 목적지 범위는 중복되면 안됨.

     - 선형복잡도(NOE만큼 할당이 일어남)

예제) rotate_copy

void rotatecopytest(){     set<int> col;     insert_elems(col, 1, 9);     print_elems(col);     set<int>::iterator pos = col.begin();     advance(pos, 1);     rotate_copy(col.begin(), pos, col.end(), ostream_iterator<int>(cout," "));     cout << endl;     pos = col.end();     advance(pos, -2);     rotate_copy(col.begin(), pos, col.end(), ostream_iterator<int>(cout, " "));     cout<< endl;  }

    > rotate_copy는 unique_copy처럼 복사본을 목적지 영역에 회전하여 집어넣는다. 즉, 원본은 보존됨. 또한 remove후 copy를 한 것과 같은 동작을 한다. (원본의 보존여부만 다름)

 

 9.8.3 원소의 순열 계산

  *형태

   i) bool prev_permutation(BidirectionalIterator beg, BidirectionalIterator end)

   ii) bool next_permutation(BidirectionalIterator beg, BidirectionalIterator end)

    - [beg,end)범위안에 있는 원소들의 순서를, next_permutation은 다음 순열에 따라,

     prev_permutation은 지난 순열에 따라 변경함

    - 두 알고리즘 모두 원소가 사전식 순서를 가지고 있다면 false를 반환. (즉, next_permutation에

     대해 오름차순, prev_permutation에 대해 내림차순 정렬시 false반환). 가능한 모든 순열을 알

     아보기 위해서는 모든 원소가 사전식으로 정렬되어야 하며, 반환값이 true면 계속 루프를 수행.

    - 선형복잡도 (NOE/2 만큼 교체가 일어남)

   예제)

void permutationtest(){     vector<int> col;     insert_elems(col, 1, 3);     print_elems(col, "on entry");     while(next_permutation(col.begin(), col.end())){        print_elems(col," ");     }     print_elems(col, "afterward");     while(prev_permutation(col.begin(), col.end())){        print_elems(col, " ");     }     print_elems(col, "now");     while(prev_permutation(col.begin(), col.end())){       print_elems(col, " ");     }     print_elems(col, "afterward");  }

 > next_permutation의 경우 오름차순으로 정렬을, prev_permutation의 경우 내림차순으로의 정렬을 수행한다. 단, next_permutation의 경우 오름차순으로 정렬되어있다면 (prev_permutation의 경우 내림차순) 조합가능한 순열을 모두 보여준다.

 

 9.8.4 원소를 뒤섞음

  *형태

   i) void random_shuffle(RandomAccessIterator beg, RandomAccessIterator end)

   ii) void random_shuffle(RandomAccessIterator beg, RandomAccessIterator end,

                               RandomFunc& op)

   - [beg,end)안의 원소들의 순서를 i)은 난수생성기를 이용하여, ii)는 op를 이용하여 무작위로 재

    배치. op는 0보다는 크고, max보다는 작은 난수를 반환해야 함.

   - op는 비상수 레퍼런스. 따라서 임시값이나 일반적인 함수들을 전달할 수 없음

   - 선형복잡도 (NOE - 1만큼 교체발생)

 예제)

class MyRandom{  public:     std::ptrdiff_t operator() (std::ptrdiff_t max){        double tmp;        tmp = static_cast<double>(rand()) / static_cast<double>(RAND_MAX);        return static_cast<std::ptrdiff_t>(tmp*max);     }  };    void rshuffletest()  {     using namespace RSHUFLIB;     vector<int> col;     insert_elems(col, 1, 9);     print_elems(col, "col     ");     random_shuffle(col.begin(), col.end());     print_elems(col, "shuffled");     sort(col.begin(), col.end());     print_elems(col, "sorted  ");     MyRandom rd;     random_shuffle(col.begin(), col.end(), rd);     print_elems(col, "rshuffld");  }

   > 난수발생을 이용한 shuffle호출 예제. QueryPerformanceCounter를 이용하여 측정한 결과.

    전체적으로 함수객체를 사용한(MyRandom) 경우가 전체적으로 수행시간이 더 짧았다. 그러나, 간헐적으로 함수객체를 사용하는 경우가 훨씬 느린 경우가 발생.

 

 9.8.5조건을 만족하는 원소를 앞쪽으로 이동하기

  *형태

   i) BidirectionalIterator partition(BidirectionalIterator beg, BidirectionalIterator end,

                                        UnaryPredicate op)

   ii) BidirectionalIterator stable_partition(BidirectionalIterator beg, BidirectionalIterator end,

                                        UnaryPredicate op)

   - [beg,end)범위 안에서 단항 조건자 op(elem)가 true를 반환하는 원소를 그렇지 않은 원소보다

    앞쪽으로 배치. 반환값은 마지막으로 이동한 원소 다음위치 (처음으로 op가 false를 반환하는

    위치)를 반환한다.

   - stable_partition()과 partition()의 차이는 원소들의 상대적인 순서가 유지되는지 여부

   - 정렬 기준에 따라 원소를 두 부분으로 나누는 용도로 사용가능. 이 경우 nth_element에서도 동

    일한 기능을 제공한다.

   - op는 호출되는 동안 자신의 상태를 변경해서는 안된다.

   - 복잡도

     i) partition() : 선형복잡도. (NOE만큼 op가 호출된다. 최대 NOE/2만큼 교체가 일어남)

     ii) stable_partition() : 여분의 메모리가 충분하면 선형복잡도 (NOE만큼 op와 교체가 일어남)

       그렇지 않을 경우 n-log-n복잡도를 가진다.(NOE * log(NOE)만큼 op가 호출됨)

예제)

void parttest(){     vector<int> col1;     vector<int> col2;     insert_elems(col1, 1,7);     insert_elems(col2, 1, 7);     print_elems(col1, "col1");     print_elems(col2, "col2");     cout << endl;     vector<int>::iterator pos1, pos2;     pos1 = partition(col1.begin(), col1.end(), not1(bind2nd(modulus<int>(),2)));     pos2 = stable_partition(col2.begin(), col2.end(), not1(bind2nd(modulus<int>(),2)));     print_elems(col1,"col1");     cout << "first odd " << *pos1 << endl;     print_elems(col2, "col2");     cout << "first odd " << *pos2 << endl;  } 결과 org : 1 2 3 4 5 6 7 part : 6 2 4 3 5 1 7 stpt : 2 4 6 1 3 5 7

    > stable_partition은 원소들의 상대적 순서가 유지된다. 그러나 partition의 경우 다음과 같이 변환한다.

    짝수가 앞으로 오는 경우 (modulues(2)의 결과가 0인경우가 앞)

   step 1 ) 1이 홀수이므로, 뒷부분에서 하나씩 검사한다. (홀/짝여부). 제일 먼저 등장하는 item은 6. 따라서, 1과 6이 swap된다. -> 6 2 3 4 5 1 7

   step 2 ) 2는 짝수이므로 바로 다음의 3을 대상으로 홀짝 검사를 한다.

   step 3) 3은 홀수이다. 이제 다시 뒤에서부터(또는 아까 마지막 교환한 위치로부터) 짝수를 검색한다. 이번에 검색된 결과는 4, 따라서 4와 3을 swap. -> 6 2 4 3 5 1 7. 이제 좌우로 나누기 끝.

 

9.9 정렬 알고리즘

 STL에서 원소를 정렬하는 여러 알고리즘을 제공함. 또한, 원소 정렬을 위해서 연관 컨테이너를 사용할 수 있으나, 한번에 정렬하는 것이 더 빠름.

 

 9.9.1 모든 원소의 정렬

  *형태

   i) void sort(RandomAccessIterator beg, RandomAccessIterator end)

   ii) void sort(RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)

   iii) void stable_sort(RandomAccessIterator beg, RandomAccessIterator end)

   iv) void stable_sort(RandomAccessIterator beg, RandomAccessIterator end,

                          BinaryPredicate op)

    - [beg,end)범위 안의 모든 원소를 i)과 iii)형태는 <조건으로, ii)와 iv)형태는 op의 조건을 이용하

     여 정렬한다.

    - op는 호출되는 동안 자신의 상태를 변경해서는 안됨

    - sort()와 stable_sort()의 차이

      i) sort(): 퀵소트 기반. 동등 원소의 상대적 위치 보장 안함. 복잡도는 n-log-n(NOE*log(NOE)).

        최악의경우 이차복잡도

      ii) stable_sort(): 머지소트 기반. 동등 원소의 상대적 위치 보장. 복잡도는 n-log-n(NOE*log

       (NOE)), 여분의메모리가 충분하지 않으면 n-log-n * log-n (NOE*(log(NOE)^2))임. 평균적으

       로 sort()보다 느리지만 최악의 경우에는 sort()가 더 느림

    - 랜덤액세스 반복자를 요구하므로 list에서 사용이 불가능. 그러나 list는 멤버함수로 제공함

    - sort()는 평균적으로 좋은 성능을 보장하나, 최악의 경우를 피하는 것이 중요하다면

     stable_sort()나 partial_sort()를 사용해야 함.

예제)

bool lessLen(const string& s1, const string& s2){     return s1.length() < s2.length();  }  void sorttest(){     vector<string> col1;     vector<string> col2;     col1.push_back("1xxx");     col1.push_back("2x");     col1.push_back("3x");     col1.push_back("4x");     col1.push_back("5xx");     col1.push_back("6xxx");     col1.push_back("7xx");     col1.push_back("8xxx");     col1.push_back("9xx");     col1.push_back("10xxx");     col1.push_back("11");     col1.push_back("12");     col1.push_back("13");     col1.push_back("14xx");     col1.push_back("15");     col1.push_back("16");     col1.push_back("17");     col2 = col1;     print_elems(col1, "on entry");     sort(col1.begin(), col1.end(), lessLen);     stable_sort(col2.begin(), col2.end(), lessLen);     print_elems(col1, "sort    ");     print_elems(col2, "stablest");  }

    > stable_sort는 원소의 상대적 순서가 유지되지만, sort는 유지되지 않는다.

  

 9.9.2 부분 정렬

  1) partial_sort

   *형태

    i) void partial_sort(RandomAccessIterator beg, RandomAccessIterator sortEnd,

                          RandomAccessIterator end)

    ii) void partial_sort(RandomAccessIterator beg, RandomAccessIterator sortEnd,

                          RandomAccessIterator end, BinaryPredicate op)

     - [beg,end)범위 안에서 i)은 <연산자를 이용하여, ii)는 op(elem1,elem2)를 이용하여 정렬한다.

      단, 정렬되는 범위는 [beg, sortEnd)임. 힙소트기반

     - op는 호출되는 동안 자신의 상태를 변경해서는 안됨

     - 만약 sortEnd와 end가 동일하면 partial_sort()는 전체 시퀀스를 정렬. sort()대비 평균적으로

      느리지만 sort()의 최악의 경우보다는 좋은 성능을 보장

     - 선형복잡도와 n-log-n사이 (대체로 NOE*log(NumberOfSortedElements)만큼 비교발생)

   예제)

void partialsorttest(){     deque<int> col;     insert_elems(col, 3,7);     insert_elems(col, 2,6);     insert_elems(col, 1,5);     print_elems(col, "org  ");     partial_sort(col.begin(), col.begin()+5, col.end());     print_elems(col, "part1");     partial_sort(col.begin(), col.begin()+5, col.end(), greater<int>());     print_elems(col, "part2");     partial_sort(col.begin(), col.end(), col.end());     print_elems(col, "part3");  }

   partial_sort에서 범위가 일부일 경우. 제일 앞에서부터 정한 구간의 끝까지(col.begin()+5인 경우 앞에서 5개까지) 원소들을 정렬한다. partial_sort는 정해진 구간까지만 정렬하고 나머지 원소는 순서가 변경된다.

 

  2) partial_sort_copy

   *형태

    i) RandomAccessIterator partial_sort_copy(InputIterator srcBeg, InputIterator srcEnd,

                                       RandomAccessIterator dstBeg, RandomAccessIterator dstEnd)

    ii) RandomAccessIterator partial_ sort_copy(InputIterator srcBeg, InputIterator srcEnd,

               RandomAccessIterator dstBeg, RandomAccessIterator dstEnd, BinaryPredicate op)

     - copy()와 partial_sort()가 결합된 형태

     - 소스범위 [srcBeg, srcEnd)에서 목적지범위 [dstBeg,dstEnd)로 원소들을 정렬 후 복사.

     - 정렬후 복사된 원소들의 개수는 소스범위와 목적지범위의 개수 중 더 작은쪽의 개수

     - 마지막으로 복사된 원소 이후의 위치를 반환함.

     - [dstBeg,dstEnd)범위가 [srcBeg,srcEnd)범위보다 같거나 많은 원소를 가지고 있을 경우, 소스

      는 정렬된 후 복사된다.

     - 선형과 n-log-n사이 (대체로 NOE*log(NOE)만큼 비교가 일어난다)

    예제)

void partsortcopy(){     deque<int> col1;     vector<int> col6(6);     vector<int> col30(30);     insert_elems(col1,3,7);     insert_elems(col1,2,6);     insert_elems(col1,1,5);     print_elems(col1);     vector<int>::iterator pos6;     pos6 = partial_sort_copy(col1.begin(), col1.end(), col6.begin(), col6.end());     copy(col6.begin(), pos6, ostream_iterator<int>(cout," "));     cout<< endl;     vector<int>::iterator pos30;     pos30 = partial_sort_copy(col1.begin(), col1.end(), col30.begin(), col30.end(), greater<int>());     copy(col30.begin(), pos30, ostream_iterator<int>(cout," "));     cout << endl;  }

      > pos1의 범위가 pos2범위보다 클 경우, pos2범위만큼만 정렬되어 들어간다. (첫 partial copy에는 6개만 정렬되어 들어감). pos1의 범위가 pos2보다 작을경우, pos1범위 전체가 정렬되어 들어간다. 그리고, partial_sort_copy는, 원본을 보존한다.

 

 9.9.3 n번째 원소까지 정렬

  * 형태

   i) void nth_element(RandomAccessIterator beg, RandomAccessIterator nth,

                          RandomAccessIterator end)

   ii) void nth_element(RandomAccessIterator beg, RandomAccessIterator nth,

                          RandomAccessIterator end, BinaryPredicate op)

    - nth를 중심으로 좌측에는 좌측에는 우측의 원소보다 같거나 작도록 정렬한다. i)형태는 정렬

      기준으로 <를, ii)는 op를 기준으로 정렬한다.

    - op는 호출 중에 자신의 상태를 변경하면 안됨

    - 복잡도 : 평균적으로 선형

예제)

void nthelemtest(){     deque<int> col;     insert_elems(col,3,7);     insert_elems(col,2,6);     insert_elems(col,1,5);     print_elems(col, "org");     nth_element(col.begin(), col.begin()+3, col.end());     cout << "4 lowest elems : " ;     copy(col.begin(), col.begin()+4,ostream_iterator<int>(cout, " "));     cout << endl;     nth_element(col.begin(), col.end()-4, col.end());     cout << "4 highest elems : ";     copy(col.end()-4, col.end(), ostream_iterator<int>(cout," "));     cout << endl;     nth_element(col.begin(), col.begin()+3, col.end(), greater<int>());     cout << "4 highest elems : ";     copy(col.begin(), col.begin()+4, ostream_iterator<int>(cout, " "));     cout << endl;     print_elems(col, "last"); }

  - 최대 n개의 원소를 찾아내는 함수라고 되어있는데 vc6에서는 아예 정렬을 다 해준다. 다른버전에서도 돌려봐야 확실할 것으로 보임

 

 9.9.4 힙 알고리즘

  *heap : 원소를 특별한 방법으로 정렬하는 곳에 사용되는 시퀀스

  - 두 가지 특징

   i) 첫 번째 원소의 값은 범위에 속하는 원소들 중 가장 큰 값

   ii) 원소의 추가와 삭제를 로그 시간으로 할 수 있음

  - 힙은 priority queue를 구현하는데 있어 이상적인 방법. 따라서 이 알고리즘은 priority queue

   컨테이너에 의해 사용됨. STL에서의 지원

   i) make_heap() : 지정된 범위의 원소들을 재배치하여 힙으로 구성

   ii) push_heap() : 힙에 새로운 원소를 추가

   iii) pop_heap() : 힙에서 다음 원소를 제거

   iv) sort_heap() : 지정된 범위의 원소를 정렬. (정렬 후에는 힙이 아님)

 

  *힙 알고리즘에 대해서

   1) make_heap

    *형태

     i) void make_heap(RandomAccessIterator beg, RandomAccessIterator end)

     ii) void make_heap(RandomAccessIterator beg, RandomAccessIterator end,

                            BinaryPredicate op)

      - [beg, end)범위의 원소들을 재배치하여 힙으로 구성. i)은 <를 기준으로, ii)는 op를 기준으로

       정렬한다.

      - 하나 이상의 원소들에 힙 연산 하려고 할 때 사용

      - 선형복잡도 (최대 NOE*3만큼 비교 발생)

 

   2) push_heap

    *형태

     i) void push_heap(RandomAccessIterator beg, RandomAccessIterator end)

     ii) void push_heap(RandomAccessIterator beg, RandomAccessIterator end,

                            BinaryPredicate op)

       - 기존에 존재하는 힙 범위 [beg, end-1)에서 마지막 원소를 추가. 전체범위인 [beg,end)는

        힙이 됨. i)은 <를, ii)는 op를 정렬 기준으로 함.

       - 호출자는 [beg,end-1)범위가 힙이라는 사실을 보장해야함. ( ii)는 같은 정렬기준) 새로 추가

        된 원소는 범위의 바로 뒤에 추가되어야 함

       - 로그복잡도 (최대 log(NOE)만큼 비교가 일어난다)

 

   3) pop_heap

     *형태

      i) void pop_heap(RandomAccessIterator beg, RandomAccessIterator end)

      ii) void pop_heap(RandomAccessIterator beg, RandomAccessIterator end,

                           BinaryPredicate op)

       - [beg, end)범위에서 가장 큰 값을 가지는 첫 번째 원소를 마지막 위치로 보낸 후, [beg,

         end-1)범위에 남은 원소를 가지고 새로이 힙을 구성함. i)은 <를, ii)는 op를 정렬 기준으로

         사용

       - [beg, end)범위의 원소들이 힙이라는 사실을 보장해야 함. ( ii)는 같은 정렬기준).

       - 로그복잡도 (최대 2 * log(NOE)만큼 비교가 이루어짐)

 

   4) sort_heap

     *형태

       i) void sort_heap(RandomAccessIterator beg, RandomAccessIterator end)

       ii) void sort_heap(RandomAccessIterator beg, RandomAccessIterator end,

                            BinaryPredicate op)

        - [beg, end)범위의 원소들을 정렬한다. i)은 <를, ii)는 op를 정렬 기준으로 사용

        - [beg, end)범위의 원소들이 힙이라는 사실을 보장해야 함. ( ii)는 같은 정렬기준).

        - 그러나 호출 후에는 더 이상 힙이 아님

        - n-log-n복잡도 (최대 NOE * log(NOE)만큼 비교가 이루어짐)

 

   예제)

void heaptest(){     vector<int> col;     insert_elems(col, 3,7);     insert_elems(col, 5,9);     insert_elems(col, 1,4);     print_elems(col, "on entry         ");     make_heap(col.begin(), col.end()); //힙 구성     print_elems(col, "after make heap  ");     pop_heap(col.begin(), col.end()); //힙에서 벗어난 원소를 제거     col.pop_back();     print_elems(col, "after pop heap   ");     col.push_back(17);     push_heap(col.begin(), col.end());     print_elems(col, "after push heap  ");     sort_heap(col.begin(), col.end());     print_elems(col, "after sort heap  ");  }

    

  

9.10 정렬된 범위 알고리즘

 - 정렬된 범위 알고리즘은 소스 범위가 정렬되었다는 가정을 바탕으로 함. 이런 알고리즘들은 좋

  은 성능을 바탕으로 함.

 

 9.10.1 원소의 검색

  1) 원소의 존재여부 판단

   *형태

    i) bool binary_search(ForwardIterator beg, ForwardIterator end, const T& value)

    ii) bool binary_search(ForwardIterator beg, ForwardIterator end, const T& value,

                              BinaryPredicate op)

     - [beg, end)안에 value와 같은 값이 있는지 검색. ii)에서 op는 이항조건자로 정렬기준으로 사

      용.

     - 검색한 원소의 위치는 upper_bound(), lower_bound(), 또는 equal_range()로 얻음

     - 호출자는 소스 범위가 정렬되어 있음을 보장해야 함

     - 랜덤액세스반복자: 로그복잡도. 다른경우는 선형 (최대 log(NOE)+2만큼 비교가 일어나

      나 랜덤액세스반복자가 아닌이상 순회연산 횟수는 선형적이며, 총 수행시간도 선형적이 됨)

    예제)

void binarysearch(){     list<int> col;     insert_elems(col, 1, 9);     print_elems(col);     if( binary_search(col.begin(), col.end(), 5)){        cout << " 5 exist" << endl;     }else{        cout << "5 not exist" << endl;     }     if( binary_search(col.begin(), col.end(), 15)){        cout << " 15 exist" << endl;     }else{        cout << "15 not exist" << endl;     } }

 

  2) 여러 개의 원소가 존재하는지 판단

   *형태

    i) bool includes( InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg,

                        InputIterator2 searchEnd)

    ii) bool includes(InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg,

                        InputIterator2 searchEnd, BinaryPredicate op)

     - 정렬된 범위 [beg,end)가 정렬된 범위인 [searchBeg, searchEnd)의 모든 원소를 포함하는지 

      판단. true일 경우, [searchBeg, searchEnd)는 [beg,end)안에 포함된다 (부분집합이다)

     - op는 이항조건자로 정렬조건임

     - 호출자는 두 범위 모두 정렬기준에 따라 정렬되었음을 보장해야 함

     - 선형복잡도 (최대 2*(NOE+SearchElement) -1만큼 비교가 일어남)

예제)

void includetest(){     list<int> col;     vector<int> search;     insert_elems(col,1,7);     print_elems(col, "col");     search.push_back(3);     search.push_back(4);     search.push_back(7);     print_elems(search, "search");     if(includes(col.begin(), col.end(), search.begin(), search.end())){        cout << "all in coll" << endl;     }     else     {        cout << "not in col" << endl;     } }

   > search의 모든 원소가 col에 포함되어 있을 때에만, all in col 조건이 성립된다. (범위무관. 다 포함되어야함)

 

  3) 정렬상태가 깨지지 않는 첫 번째 또는 마지막 위치 검색

   *형태

    i) ForwardIterator lower_bound(ForwardIterator beg, ForwardIterator end, const T& value)

    ii) ForwardIterator lower_bound(ForwardIterator beg, ForwardIterator end, const T& value,

                                           BinaryPredicate op)

    iii) ForwardIterator upper_bound(ForwardIterator beg, ForwardIterator end, const T& value)

    iv) ForwardIterator upper_bound(ForwardIterator beg, ForwardIterator end, const T& value,

                                           BinaryPredicate op)

      - lower_bound()는 value로 들어온 값 보다 크거나 같은 값을 가지는 원소의 위치를 반환. 이

       위치는 [beg, end)에서 정렬상태를 깨지 않고 원소를 삽입할 수 있는 첫 번째 위치

      - upper_bound()는 value로 들어온 값 보다 큰 값을 가지는 원소의 위치를 반환. 이 위치는

       [beg, end)에서 정렬상태를 깨지 않고 원소를 삽입할 수 있는 마지막 위치

      - 둘다 찾지 못하면 end()반환

      - 호출자는 소스 범위가 정렬되어 있음을 보장해야 함

      - op는 이항조건자로 정렬기준으로 사용됨

      - lower_bound()와 upper_bound()를 동시에 얻고 싶으면 equal_range()를 사용.

      - 연관컨테이너는 더 좋은 성능의 멤버함수를 제공

      - 랜덤액세스반복자는 로그복잡도. 이외의 경우 선형(최대 log(NOE)+1만큼 비교가 발생)

 

  4) 정렬상태가 깨지지 않는 첫번째 또는 마지막 위치의 검색

   *형태

    i) pair<ForwardIterator, ForwardIterator > equal_range(ForwardIterator beg,

                                                                    ForwardIterator  end, const T& value)

    ii) pair<ForwardIterator, ForwardIterator > equal_range(ForwardIterator beg,

                                             ForwardIterator end, const T& value, BinaryPredicate op)

     - lower_bound()와 upper_bound()가 반환하는 반복자로 구성된 pair를 반환. 정렬을 깨트리지

      않고 원소를 삽입할 수 있는 첫 번째와 마지막 위치.

     - make_pair(lower_bound(), upper_bound())와 같음

     - op는 이항조건자로 정렬기준으로 사용됨

     - 호출자는 소스 범위가 정렬되어 있음을 보장할 것

     - 연관 컨테이너는 멤버함수로 더 좋은 성능을 냄

     - 랜덤액세스반복자는 로그복잡도. 이외의 경우 선형 (최대 2*log(NOE)+1만큼 비교 일어남)

 

 9.10.2 원소의 병합

  1) 정렬된 두 범위 합치기

    *형태

     i) OutputIterator merge(InputIterator src1beg, InputIterator src1end, InputIterator src2beg,

                                 InputIterator src2end, OutputIterator dstbeg)

     ii) OutputIterator merge(InputIterator src1beg, InputIterator src1end, InputIterator src2beg,

                                   InputIterator src2end, OutputIterator dstbeg, BinaryPredicate op)

      - 정렬된 소스 범위 [src1beg,src1end)와 [src2beg,src2end)의 원소를 하나로 합치고 그 결과

       를 dstbeg으로 시작하는 목적지에 기록. 기록된 결과는 정렬되어있음. 기록된 마지막 원소

       다음 원소를 반환함. op는 이항조건자로 정렬기준에 사용. 소스범위 수정되지 않음

      - 호출자는 두개의 소스범위가 정렬되었음을 보장(표준내용. 실제로는 아님). 목적지에 충분한

       공간이 있거나 삽입 반복자를 사용하는 것을 보장해야 함

      - 목적지 범위는 소스 범위와 겹치지 않아야 함.

      - 두 범위 원소의 합집합은 set_union(), 교집합은 set_intersection()을 사용하여 구함. list의 경

       우 merge()멤버함수를 제공한다.

      - 선형복잡도 (최대 (NOE1+NOE2)-1 비교가 일어남)

예제)

void merge(){     list<int> col1;     set<int> col2;     insert_elems(col1,1,6);     insert_elems(col2,3,8);     print_elems(col1,"col1");     print_elems(col2,"col2");     merge(col1.begin(), col1.end(), col2.begin(), col2.end(), ostream_iterator<int>(cout, " "));     cout << endl;  }

     > 병합하면서 정렬이 수행된다.

 

  2) 정렬된 두 범위의 합집합 계산

    *형태

     i) OutputIterator set_union(InputIterator src1Beg, InputIterator src1End,

                                  InputIterator src2Beg, InputIterator src2End, OutputIterator dstBeg)

     ii) OutputIterator set_union(InputIterator src1Beg, InputIterator src1End,

          InputIterator src2Beg, InputIterator src2End, OutputIterator dstBeg, BinaryPredicate op)

      - 정렬된 소스범위 [src1Beg, src1End)와 [src2Beg, src2End)의 원소를 합치고, 그 결과를 dst

       로 시작하는 목적지 범위에 기록. 기록된 결과는 정렬된 순서를 가짐

      - 두 소스 범위 중, 어느 한 범위에서 한 개 이상의 중복된 값이 존재한다면 목적지 범위는 중

       복된 값을 가질 수 있다.

        ex) 범위1 : 1,2,2,2,3,4를 가지고 범위2 : 1,2,2,2,2,3를 가지고 있으면 set_union후에는

           1,2,2,2,2,3,4가 된다. (2,2,2와 2,2,2,2의 합집합은 2,2,2,2임)

      - 마지막으로 복사된 원소 이후의 위치를 반환

      - op는 이항조건자로 정렬 기준으로 사용됨

      - 소스 범위는 수정되지 않음

      - 호출자는 범위가 정렬기준에 따라 정렬되어 있음을, 목적지 범위가 충분히 크거나 삽입반복

       자를 사용하는 것을 보장할 것

      - 목적지 범위는 소스 범위와 겹치지 않아야 함. 소스 범위의 합을 얻으려면 merge()사용

      - 선형복잡도 (최대 2*(NOE1+NOE2)-1만큼 비교 일어남)

 

  3) 정렬된 두 범위의 교집합 계산

    *형태

     i) OutputIterator set_intersection(InputIterator src1Beg, InputIterator src1End,

                                  InputIterator src2Beg, InputIterator src2End, OutputIterator dstBeg)

     ii) OutputIterator set_intersection(InputIterator src1Beg,InputIterator src1End,

            InputIterator src2Beg,InputIterator src2End,OutputIterator dstBeg, BinaryPredicate op)

      - 정렬된 두 범위 [src1Beg, src1End)와 [src2Beg, src2End)의 원소의 교집합을 dstBeg로 시

       작하는 목적지 범위에 기록한다. 기록된 순서는 정렬되어있다.

      - 목적지 범위에서 중복된 값이 발생하는 경우는 두 소스 범위 모두 2개이상의 같은 원소를

       지닌경우이다.

          ex) 범위1: 1,2,2,3,4,5 범위2: 2,2,2,2,3,4,6 일 경우 set_intersecion의 결과는 2,2,3,4임

      - 마지막으로 합쳐진 원소 이후의 위치를 반환

      - op는 이항조건자로 정렬 기준으로 사용됨

      - 소스범위는 수정되지 않는다. 또한, 소스 범위는 목적지 범위와 중복되지 않아야함

      - 호출자는 호출자는 범위가 정렬기준에 따라 정렬되어 있음을, 목적지 범위가 충분히 크거나

       삽입반복자를 사용하는 것을 보장할 것.

      - 선형복잡도 (최대 2*(NOE1+NOE2)-1만큼 비교가 일어남)

 

  4) 정렬된 두 범위의 차집합 계산

    4-1) set_difference

     *형태

        i) OutputIterator set_difference(InputIterator src1Beg, InputIterator src1End,

                                 InputIterator src2Beg, InputIterator src2End, OutputIterator dstBeg)

        ii) OutputIterator set_difference(InputIterator src1Beg,InputIterator src1End,

           InputIterator src2Beg,InputIterator src2End, OutputIterator dstBeg, BinaryPredicate op)

         - 정렬된 두 범위 [src1Beg, src1End)와 [src2Beg, src2End)의 원소의 차집합(범위 1에는 있

          으나 범위2에는 없는 원소의 집합)을 dstBeg로 시작하는 목적지 범위에 기록한다. 기록된

          순서는 정렬되어있다.

         - 목적지 범위에 중복된 값이 나타나는 경우는 첫 번째 범위와 두 번째 범위에 동일한 값이

          등장하고 첫 번째 범위에 동일한 값이 더 많이 존재할 경우에 나타남.

         - 마지막으로 합쳐진 원소 이후의 위치를 반환함

         - op는 이항조건자로 정렬 기준임

         - 소스 범위는 수정되지 않음. 소스 범위와 목적지 범위는 중복되지 않아야 함

         - 호출자는 호출자는 범위가 정렬기준에 따라 정렬되어 있음을, 목적지 범위가 충분히 크거

          나 삽입반복자를 사용하는 것을 보장할 것.

         - 선형복잡도 (최대 2*(NOE1+NOE2)-1만큼 비교가 일어남)

 

    4-2) set_symmetric_difference

     *형태

        i) OutputIterator set_symmetric_difference(InputIterator src1Beg, InputIterator src1End,

                                InputIterator src2Beg, InputIterator src2End, OutputIterator dstBeg)

        ii) OutputIterator set_symmetric_difference(InputIterator src1 Beg, InputIterator src1End,

          InputIterator src2Beg, InputIterator src2End, OutputIterator dstBeg, BinaryPredicate op)

          - 정렬된 두 범위 [src1Beg, src1End)와 [src2Beg, src2End)의 원소의 대칭 차집합을 구한

           다. (범위1과 2를 합치고, 그 안에서 중복되는 것을 제거한 집합). 그 결과는 dstBeg로 시

           작하는 목적지 범위에 기록되고, 그 순서는 정렬되어 있음.

          - 목적지 범위에 중복된 값이 나타나는 경우는, 두개의 소스 범위 중 하나의 범위에서 두개

           이상의 동일한 값이 존재하는 경우.

             ex) 범위1 : 1,2,2,4,6,7와 범위2: 2,2,2,3,4,8을 set_intersection하면, 범위2의 2,2,2,중 마지

               막원소 2는 두번째 범위에만 존재하므로 목적지 범위에 기록된다. 결과는 1,2,3,6,7,8

          - 마지막으로 합쳐진 원소 이후의 위치를 반환함

          - op는 이항조건자로 정렬의 기준이 됨

          - 소스 범위는 수정되지 않는다. 소스 범위는 목적지범위와 중복되서는 안됨.

          - 호출자는 호출자는 범위가 정렬기준에 따라 정렬되어 있음을, 목적지 범위가 충분히 크

           거나 삽입반복자를 사용하는 것을 보장할 것.

          - 선형복잡도 (최대 2*(NOE1+NOE2)-1만큼 비교가 일어남)

   예제) 

void setalgotest() {    int c1[] = {1,2,2,4,6,7,7,9};    int num1 = sizeof(c1)/sizeof(int);    int c2[] = { 2,2,2,3,6,6,8,9};    int num2 = sizeof(c2)/sizeof(int);    cout << "c1       : " ;    copy (c1, c1+num1, ostream_iterator<int>(cout, " "));    cout << endl;    cout << "c2       : " ;    copy (c2, c2+num2, ostream_iterator<int>(cout, " "));    cout << endl;    cout << "setunioin: " ;  //합집합    set_union(c1,c1+num1,c2,c2+num2,ostream_iterator<int>(cout, " "));    cout << endl;    cout << "setinters: "; //교집합    set_intersection(c1,c1+num1,c2,c2+num2,ostream_iterator<int>(cout, " "));    cout << endl;    cout << "setdiffer: "; //차집합    set_difference(c1,c1+num1,c2,c2+num2,ostream_iterator<int>(cout, " "));    cout << endl;    cout << "setsymdif: "; //대칭차집합    set_symmetric_difference(c1,c1+num1,c2,c2+num2,ostream_iterator<int>(cout, " "));    cout << endl; }

 

  5) 연속적으로 정렬된 범위의 병합

     *형태

      i) void inplace_merge(BidirectionalIterator beg1, BidirectionalIterator end1beg2,

                                 BidirectionalIterator end2)

      ii) void inplace_merge(BidirectionalIterator beg1, BidirectionalIterator end1beg2,

                                 BidirectionalIterator end2, BinaryPredicate op)

        - 붙어있는 두 개의 정렬범위인 [beg1, end1beg2), [end1beg2, end2)를 합쳐서

         [beg1,end2)에 그 결과를 놓는다.

        - 복잡도 : 여분의 메모리가 충분하면 선형(NOE-1만큼 비교), 그렇지 않을 경우 n-log-n복잡

         도(NOE*log(NOE)만큼의 비교)

예제)

void inplacemerge(){     list<int> col;     insert_elems(col,1,7);     insert_elems(col,1,8);     print_elems(col,"init");      list<int>::iterator pos;     pos = find(col.begin(), col.end(), 7);     ++pos;     inplace_merge(col.begin(), pos, col.end());     print_elems(col, "merged"); }

   > 하나의 컨테이너에서 연속적으로 정렬된 두개의 범위를 정렬하는데 사용.

 

9.11 수치 알고리즘

 사용을 위해서는 <numeric>을 포함하면 됨

 9.11.1 결과 값 처리

  1) 한 시퀀스의 결과 계산

   *형태

     i) T accumulate(InputIterator beg, InputIterator end, T initVal)

     ii) T accumulate(InputIterator beg, InputIterator end, T initVal, BinaryFunc op)

       - [beg,end)범위에서 i)는 initVal = initVal + elem을, ii)는 initVal = op(initVal, elem)을 호출

        하여 계산한다. 그리고 initVal의 최종 합을 반환함.

       - 만약 beg==end (비어있다면) initVal을 반환

       - op는 전달된 인자를 변경해서는 안됨

       - 선형복잡도 (NOE만큼의 +또는 op호출)

  

  2) 두 시퀀스의 내적 계산

    *형태

      i) T inner_product(InputIterator beg1, InputIterator end1, InputIterator beg2, T initVal)

      ii) T inner_product(InputIterator beg1, InputIterator end1, InputIterator beg2, T initVal,

                             BinaryFunc op1, BinaryFunc op2)

        - [beg1, end1)범위의 각각의 원소와 beg2로 시작하는 두 번째 범위에 대해서,

         i)는 initVal = initVal + elem1 * elem2를, ii)는 initVal = op1(initVal, op2(elem1,elem2))를

         호출하여 계산한 후, initVal의 최종 내적값을 반환한다. 첫 번째 범위가 비어있다면

         (beg1 == end1), initVal을 반환함. op1과 op2는 인자로 들어온 값을 변경하면 안됨

        - 호출자는 beg2로 시작하는 범위에 충분한 원소를 가지고 있음을 보장해야 한다.

        - 선형복잡도 (NOE만큼 연산자와 op호출됨)

 예제)

#include <numeric>  void accum(){    vector<int> col;    insert_elems(col,1,6);    print_elems(col, "init");    cout << "sum :" << accumulate(col.begin(), col.end(), 0) << endl;    cout << "sum2:" << accumulate(col.begin(), col.end(), -100) << endl;    cout << "mul :" << accumulate(col.begin(), col.end(), 1, multiplies<int>()) << endl;    cout << "innerproduct:" << inner_product(col.begin(), col.end(), col.begin(), 0) << endl;    cout << "innerrprod  :" << inner_product(col.begin(), col.end(), col.rbegin(), 0) << endl; }

  > accumulate : 기본 연산은 +. [beg,end)를 모두 더한 후 그 값과 초기값을 더한 결과 반환. 곱셈의 경우 모두 곱한 후 초기값과 곱한 결과 반환. 내적 연산은 모든 1 * 1 + 2* 2 ... + 6*6의 합을 반환 (마지막은 1*6 + 2*5 + ... + 6*1)

 

 9.11.2 절대적인 값과 상대적인 값으로의 변경

   1) 상대적인 값을 절대적인 값으로 변경

    *형태

      i) OutputIterator partial_sum(InputIterator srcBeg, InputIterator srcEnd,

                                        OutputIterator dstBeg)

      ii) OutputIterator partial_sum(InputIterator srcBeg, InputIterator srcEnd,

                                        OutputIterator dstBeg, BinaryFunc op)

        - [srcBeg, srcEnd)범위에 대해서 i)는 각 원소에 대한 부분합을 계산하고, ii)는 op를 호출하

         여 dstBeg로 시작하는 목적지 범위에 대해 결과를 기록한다.

           ex) 만약 원소가 a1 a2 a3… 일 경우

              i) : a1, a1 + a2, a1 + a2 + a3, …

              ii) : a1, a1 op a2, a1 op a2 op a3, …

        - 목적지에 마지막으로 쓰여진 값의 위치 다음을 반환한다.

        - i)의 형태는 상대적인 값의 시퀀스에서 절대적인 값의 시퀀스로 변화하는 것과 동일

        - 소스 범위와 목적지 범위는 동일할 수 있다.

        - 호출자는 목적지 범위가 충분히 크거나 삽입 반복자를 사용하는 것을 보장해야함

        - op는 전달된 인자를 변경해서는 안된다.

        - 선형복잡도 (NOE만큼 +나 op호출)

 

   2) 상대적인 값을 절대적인 값으로 변경

    *형태

      i) OutputIterator adjacent_difference(InputIterator srcBeg, InputIterator srcEnd,

                                                  OutputIterator dstBeg)

      ii) OutputIterator adjacent_difference(InputIterator srcBeg, InputIterator srcEnd,

                                                  OutputIterator dstBeg, BinaryFunc op)

        - [srcBeg, srcEnd) 범위에서 i)는 각 원소에 대한 차이를, ii)는 각 원소에 대해 op를 호출하

        여 그 결과를 dstBeg로 시작하는 목적지 범위에 기록된다. 첫 번째 원소만이 복사된다.

          ex) a1, a2, a3, a4…

            i) a1, a2-a1, a3-a2, a4 –a3,…

            ii) a1, a2 op a1, a3 op a2, a4 op a3, …

        - 마지막으로 쓰여진 값의 다음 위치를 반환함

        - i)형태는 절대적인 값의 시퀀스에서 상대적인 시퀀스로 변화하는 것과 동일함

        - 소스 범위와 목적지 범위는 동일할 수 있음.

        - 호출자는 목적지 범위가 충분히 크거나 삽입 반복자를 사용하는 것을 보장해야 함.

        - op는 전달된 인자를 변경해서는 안됨

        - 선형복잡도( NOE-1만큼 –연산자나 op호출)

 

 예제)

void abstest(){     vector<int> col;     insert_elems(col,1,6);     print_elems(col, "init");     partial_sum(col.begin(), col.end(), ostream_iterator<int>(cout," ")); //상대적인 값을 절대값으로     cout << endl;     partial_sum(col.begin(), col.end(), ostream_iterator<int>(cout," "), multiplies<int>());     cout << endl;     adjacent_difference(col.begin(), col.end(), ostream_iterator<int>(cout," ")); //절대값을 상대값으로     cout << endl;     adjacent_difference(col.begin(), col.end(), ostream_iterator<int>(cout," "), multiplies<int>());     cout << endl; }  결과 :   1  2  3   4   5    6   1  3  6 10  15   21   1  2  6 24 120 720    1  1  1  1    1    1   1  2  6  12  20  30

   > partial_sum : 각 원소에 대해 op (기본은 plus)연산을 수행한 결과를 가지고 있다.

 

참조 : C++ Standard Library - A tutorial and Reference