chapter 7-9. 내용정리

1. 반복자

 반복자 카테고리와 기능

카테고리	기능	제공자
입력반복자	전방향 읽기	istream
출력반복자	전방향 쓰기	ostream, inserter
전방향반복자	전방향 읽기/쓰기
양방향반복자	전/역방향 읽기/쓰기	list, set, multiset, map, multimap
랜덤액세스반복자	랜덤액세스	deque, vector, string, array

 전방향 반복자는 입력/출력반복자의 기능을 포함하고, 양방향 반복자는, 전방향반복자 + 역방향 지원, 랜덤 액세스 반복자는 양방향 반복자에, 랜덤 액세스까지 지원하는 반복자.

 

   * 반복자에서 증가/감소 연산자 사용시, 전위증가(감소)연산자를 사용하는 것이 더 유리하다. 후위증가(감소)연산자의 경우 임시객체를 생성하기에 상대적으로 더 느리다.

 

 1) 보조반복자 함수

   - 랜덤 액세스 반복자만 지원하는 기능을 다른 반복자에서도 사용할 수 있게 지원하는 함수

   i) advance : 반복자 위치 변경에 사용

     advance(pos, dist n)

     n의 값 만큼 반복자를 이동한다. (n이 양수이면 뒤로, 음수이면 앞으로 이동)

    예제)

void advance(){    list<int> col;      initCon(col,1,9);      list<int>::iterator pos = col.begin();    cout << *pos <<endl;    advance(pos, 3);    cout << *pos <<endl;    advance(pos, -1);    cout << *pos <<endl; }  > advance에서의 거리가 양수이면 뒤로, 음수이면 앞으로 이동. begin의 위치를 넘어서서 -로 advance하니까 다시 한바퀴돌아왔다. (반대는 앞으로 돌아옴. VC6에서만 그런지 확인 필요)

 

   ii) distance : 두 반복자 사이의 거리를 계산하는데 쓰임

    distance(pos1, pos2);

    두 반복자 모두 같은 컨테이너에 존재하는 원소를 가리켜야 함.

    예제) 

void distance(){     list<int> col;     initCon(col, -3, 9);     list<int>::iterator pos = col.begin();     pos = find(col.begin(), col.end(), 3);     print_elems(col, "list");     cout << "dist:" << distance(col.end(), pos) << endl;     cout << "dist:" << distance(pos, col.end()) << endl; }

   > 랜덤액세스 반복자가 아니라면 pos2는 pos1보다 커야한다는데, VC6에서 수행시, 순서는 무관했다. (pos2가 pos1보다 작아도 거리 측정에는 문제가 없었다.)

 

   iii) iter_swap : 두 반복자가 가리키고 있는 값을 교체한다

    iter_swap(pos1, pos2)

    pos1과 pos2의 값을 교체한다. 반복자는 같은 타입일 필요 없지만, 서로 할당 가능하여야 한다.

  예제 

void itrswap(){    list<int> col;    list<float> col2;    initCon(col,1,9);    initCon(col2, 10,20);    print_elems(col, "init");    iter_swap(col.begin(), ++col.begin());    print_elems(col, "swap");    iter_swap(col1.begin(), col2.begin()); //동작한다. 문제없이 swap됨 }

  > int, float간에도 문제없이 swap된다.

 

 2) 역방향 반복자

   역순모드로 동작을 위해 기존의 증가/감소를 재정의한 반복자. 역방향 반복자의 경우 위치에서 하나 앞의 값을 가리킨다. 반복자 변환시 문제가 없기 위해서.

   역방향 반복자를 얻기 위해서는 컨테이너에서 rbegin(), rend()를 이용하여 반복자를 얻어오거나, 정방향 반복자를 역방향 반복자로 변환하려면 container::reverse_iterator rpos(pos); 를 이용하여 얻어온다.

   반대로 역방향 반복자를 정방향으로 변환하기 위해서는 rpos.base() 함수를 이용하여 변환한다.

  예제) 

void revitr2(){     list<int> col;     initCon(col,1,9);     list<int>::iterator pos1;     pos1 = find(col.begin(), col.end(), 3);     list<int>::reverse_iterator rpos1(pos1);     cout << "rpos : " << *rpos1 << endl;     list<int>::iterator rrpos;     rrpos = rpos1.base();     cout << "rrpos : " << *rrpos << endl;     cout << "pos : " << *pos1 << endl; }

 

 

  3) 삽입반복자

    전위삽입반복자, 후위삽입반복자, 삽입반복자가 있음.

    front_inserter(원소) : 컨테이너의 앞에 원소를 삽입

    back_inserter(원소) : 컨테이너의 뒤에 원소를 삽입

    inserter(pos, 원소) : 정한 위치에 원소를 삽입.

 

  4) 스트림 반복자

   - 알고리즘의 목적지나 소스에 스트림을 허용하는 반복자. 입/출력시 사용한다.

     출력스트림 예제

예제

void ostream1(){     ostream_iterator<int> intWriter(cout,"\n");     *intWriter = 42;     intWriter++;     *intWriter = 88;     intWriter++;     *intWriter = -5;     *intWriter = -10;     vector<int> col;     initCon(col, 1,9);     copy(col.begin(), col.end(), ostream_iterator<int>(cout));     cout << endl;     copy(col.begin(), col.end(), ostream_iterator<int>(cout, "<")); }

  > intWriter에서 ++을 하고 값을 기록하나, 안하고 기록하나 둘 다 출력된다. 즉, 영향을 받지 않음

 

   입력스트림 예제

   예제

void istream1(){     istream_iterator<int> intReader(cin);     istream_iterator<int> intReaderEOF;     while( intReader != intReaderEOF){       cout << "once: " << *intReader << endl;       cout << "once again: " << *intReader << endl;       ++intReader;  //intReader를 ++해주지 않으면 첫번째값만 무한출력       } }

 

   5) 사용자정의 반복자

    '반복자 특성 템플릿' (value_type, difference_type, iterator_category, pointer, reference)의 정의를 제공한다.

   반복자정의 예 

//assoiter.hpp #include <iterator>   template <class Container> class asso_insert_iterator : public std::iterator <std::output_iterator_tag, void /*, void, void, void*/>                                                                                                     //VC6.0은 void가 하나 { protected:    Container& container; public:    explicit asso_insert_iterator(Container& c) : container(c){}    asso_insert_iterator<Container>& operator= (const typename Container::value_type& value){       container.insert(value);       return *this;    }      asso_insert_iterator<Container>& operator* (){       return *this;    }      asso_insert_iterator<Container>& operator++ (){       return *this;    }    asso_insert_iterator<Container>& operator++ (int){       return *this;    } };   template<class Container> inline asso_insert_iterator<Container> asso_inserter(Container& c){     return asso_insert_iterator<Container>(c); }

 

    반복자 사용

 예제

#include "assoiter.hpp" using namespace std; void customiter(){    set<int> col;    asso_insert_iterator<set<int> > iter(col);    *iter = 1;    iter++;    *iter = 2;    iter++;    *iter = 3;    *iter = 4;      print_elems(col, "init");    asso_inserter(col) = 44;    asso_inserter(col) = 55;    print_elems(col, "use inserter");      int vals[] = {33, 67, -4, 13, 5, 2};    copy(vals, vals+(sizeof(vals)/sizeof(vals[0])), asso_inserter(col));    print_elems(col, "after copy"); }

 

2. 함수객체

 - 함수 객체는 ()연산자를 정의한 객체. 가지는 장점은 다음과 같다.

  1) 함수객체는 상태를 가질 수 있다. 같은 함수 객체에 대해 동시에 다른 상태를 가질 수 있음

  2) 각각의 함수 객체는 자신만의 타입을 가지므로, 함수 객체의 타입을 템플릿의 인자로 제공가능함.

  3) 함수객체는 함수포인터보다 빠르다.

 

 1) 정렬기준으로서의 함수 객체.

   예를 들어 연관 컨테이너의 정렬 조건으로서 사용하여 다른 정렬 기준을 정의할 수 있다.

   예제

class Person{  private:     string fn;     string ln;  public:     explicit Person(const string& f, const string& l) : fn(f), ln(l) {}     string firstname() const { return fn; }     string lastname() const { return ln; } };   class PersonSortCrit{ public:    bool operator() (const Person& p1, const Person& p2) const {        return (p1.lastname() < p2.lastname()) || (!(p2.lastname() < p1.lastname()) && p1.firstname() <  p2.firstname());    } };   void fo1(){    using namespace MyLib;    typedef set<Person, PersonSortCrit> PS;    PS col;      Person p1( "Hello", "World");    Person p2( "aa", "World");    Person p3( "a", "World4");    Person p4( "a", "World2");    Person p5( "Hello", "ddd");    col.insert(p1);    col.insert(p2);    col.insert(p3);    col.insert(p4);    col.insert(p5);      PS::iterator pos = col.begin();    for( pos = col.begin() ; pos != col.end() ; pos++){       cout << "[" << pos->firstname() << ", " << pos->lastname() << "]" << endl;    } }

 위와 같이 lastname과 firstname을 정렬조건으로 사용할 수 있도록 함수객체를 넘겨줄 수 있다.

 

  2) 내부상태를 가지는 함수객체

   알고리즘에서는 함수객체 내부의 상태를 변경하지 않는다. 이를 변경하고 싶으면 레퍼런스로 정의하거나 for_each문의 반환값을 이용한다.

   for_each문 예제

예제 

class MeanValue{  private:     long num;     long sum;  public:     MeanValue() : num(0), sum(0){}     void operator() (int elem){        num++;        sum += elem;     }       operator double(){        return static_cast<double>(sum) / static_cast<double>(num);     }  };   void foreachtest1(){    vector<int> col;    initCon(col, 1, 8);      MeanValue mv = for_each(col.begin(), col.end(), MeanValue());    cout << "mean value: " << mv << endl; }

  > for_each에서는 계산(MeanValue())을 마친 후, 그 객체를 mv에 할당함. 그래서, mv는 결과를 가지고 있다.

 

  3) 함수 어댑터

   - 함수-객체를 특정값이나 특정 함수와 결합시킨 함수객체.

   - 미리 정의된 함수 객체는 다음과 같다.

표현식	효과
bind1st(op, value)	op(value, param)
bind2nd(op, value)	op(param, value)
not1(op)	!op(param)
not2(op)	!op(param1, param2)

    위 함수 어댑터와 함수객체를 조합하여 사용할 수 있다.

 

  4) 함수 어댑터를 위한 사용자 정의 함수 객체

   - 함수어댑터와 같이 사용하기 위해 함수 객체를 만들수 있다. C++표준 라이브러리에서는 이를 위해 기본이 되는 구조체인 unary_function, binary_function을 제공한다. 이 두 구조체를 상속받아서 구현하면 된다. 아래는 두 구조체 정의

unary function	binary function
template<class Arg, class Result> struct unary_function{    typedef Arg argument_type;    typedef Result result_type; };	template<class Arg1, class Arg2, class Result> struct binary_function{    typedef Arg1 first_argument_type;    typedef Arg2 second_argument_type;    typedef Result result_type; }

  함수객체 정의 예제 

 예제

//fopow.hpp #include <functional> #include <cmath>   template <class T1, class T2> struct fopow : public std::binary_function<T1, T2, T1> {     T1 operator() (T1 base, T2 exp) const {        return std::pow(base, exp); //VC6에서는 std::pow가 아닌 pow임     } }

  > 위 구조체는 class로 선언해도 좋다. 다만 public선언을 해주어야 한다.

 

 함수객체 사용예제

 예제 

#include "fopow.hpp" using namespace std; void fopowtest() {     vector<int> col;     initCon(col, 1, 9);       transform(col.begin(), col.end(), ostream_iterator<int>(cout, " "), bind1st(fopow<float,int>(),3));     cout << endl;     transform(col.begin(), col.end(), ostream_iterator<int>(cout," "), bind2nd(fopow<float,int>(),3));     cout << endl; }

  > bind1st, bind2nd는 위에 정의된 대로, 첫 번째 인자인지 두 번째 인자인지 정의만 함

 

  이후 조립함수 객체 사용 예제는 아래 링크 참조

  http://gomnezip.tistory.com/320

 

3. 알고리즘

 컨테이너의 지정한 범위에 대해 원소를 처리한다. 알고리즘을 호출하는 호출자는 범위의 유효성에 대해서 보장해야 한다. 범위가 유효하지 않으면 예상치 않은 결과를 반환한다.

  1) for_each알고리즘

   - 컨테이너의 원소를 다양한 방법으로 액세스, 처리, 수정하기에 용이하다.

   - for_each를 사용하여 원소를 수정할 수 있는데, 이는 transform으로도 수행할 수 있다. for_each의 경우 수정할 원소의 값을 레퍼런스로 받아와서 처리하고, transform은 수정된 값을 반환한다. transform이 조금 더 느리지만 원본을 보존한다는 점에서 더 유연하다.

  예제 

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 : 캐스팅 연산자오버로딩. 해당 타입으로 캐스팅이 일어날 때, 호출된다.

 

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

    i) 원소의 카운트 : count, count_if. (count_if는 마지막 인자로 조건자를 넣어준다.). 카운트한 결과 반환

    ii) 최대/최소 : min_element, max_element

     예제   

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의 반환값은 반복자이므로 *를 붙여서 값을 얻어온다.

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

 

   iii) 원소의 검색

     a) 검색조건과 매치되는 첫 번째 원소 검색. find, find_if. find는 value가 일치하는 첫 번째 원소. find_if는 조건자 op가 참이되는 첫 번째 원소를 찾아서 해당 위치를 반환한다.

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

     예제 

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임

 

    c) 첫 번째 부분범위 검색 : search

      ForwardIterator1 search(ForwardIterator1 beg, ForwardIterator1 end, ForwardIterator2 searchBeg,

                                        ForwardIterator2 searchEnd)

      - [beg,end)범위 내에 [searchBeg, searchEnd) 범위가 완전히 포함되어야 참을 리턴해 줌.

 

    d) 마지막 부분 범위 검색 : find_end

      - 부분 범위 검색이나, [searchBeg, searchEnd)를 포함한 첫 부분이 아닌 마지막으로 포함한  부분을 반환함.

 

    e) 여러개의 원소 검색 : find_first_of. [beg,end)범위 내에 [searchBeg, searchEnd) 범위에 속하는 값들을 검색. find와 비슷하지만, 값이 아닌 범위를 검색한다.

 

    f) 연속 중복원소의 검색 : adjacent_find

     예제)

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인 경우의 위치를 반환. 다만, 기본으로 설정된 이항연산자가 '=='인것.

 

iv)범위 비교

  a) 동일성 검사 : [beg,end)에서 col2[Beg,end)이 범위 안에 포함되어야 한다. (시작 아이템도 match가 되어야 한다.)

   예제

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.

 

  b) 두 범위 내에서 다른 값 존재 여부 검색 : mismatch. 조건에 맞지않는 원소의 위치를 반환한다. (반복자)

 

  예제) 

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에 원소가 없는 경우 예상치 못한 비교 결과가 나온다

 

   c) 사전식 방법으로 적은지를 판단 : lexicographical_compare

     예제

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은 사전식 정렬을 한다. (결과 참조)

   

 이후 각 알고리즘에 대한 설명은 http://gomnezip.tistory.com/321 참조