Chapter 7. STL반복자

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

 

7.1 반복자의 헤더파일

 역방향 반복자 같은 특별한 반복자는 <iterator>안에 있음. 그 외에는 컨테이너에 포함

 

7.2 반복자 카테고리

 *반복자 카테고리의 기능

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

 

 7.2.1 입력 반복자

  전진방향으로 읽기 엑세스만 가능한 반복자.

   * 동작

    1) *iter : 원소의 읽기 엑세스를 제공

    2) iter->member : 원소 멤버의 읽기 엑세스를 제공

    3) ++iter : 전방향으로 전진(새로운 위치를 반환)

    4) iter++ : 전방향으로 전진(예전 위치를 반환)

    5) iter1 == iter2 : 두 반복자가 같은지 판별. ( !=는 같지 않음을 판별)

    6) TYPE(iter) : 반복자를 복사한다. (복사생성자)

   *후위증가 연산자 보다는 전위증가 연산자를 사용하는 것이 좋다. 전위증가는 임시객체 생성을

   하지 않아 더 빠르다. (감소 연산자에 있어서도 동일)

 

 7.2.2 출력 반복자

  전진 방향으로 쓰기만 가능한 반복자. 사용자는 동일한 범위에 대해서 두번 이상 출력 반복자를

 사용하여 순회할 수 없음.

  * 동작

   1) *iter = value : 반복자가 참조하는 곳에 value를 기록

   2) ++iter, iter++ ,TYPE(iter) : 입력 반복자와 동일

 

 7.2.3 전방향 반복자

  출력반복자이면서 입력반복자를 의미. 전방향으로 읽기/쓰기 모두 가능

  * 기능

   1) *iter : 원소에 read액세스를 제공

   2) iter->member : 원소의 멤버에 대해 read엑세스 제공

   3) ++iter, iter++, TYPE(iter) : 입/출력 반복자와 동일

   4) TYPE() : 반복자를 생성 (디폴트 생성자)

   5) iter1 == iter2, iter1 != iter2 : 입력반복자의 비교와 동일

   6) iter1 = iter2 : 반복자를 할당한다.

  *출력반복자에서 데이터 기록시, 시퀀스의 끝을 검사하지 않는 것이 올바른 방법. 출력 반복자는

   비교 동작을 지원하지 않는다. 그러나 전방향반복자를 사용시 이 반복자가 유효할지 검사하여야 함.

   예)

while(true){     *pos = foo();     ++pos;  }  //위 코드는 출력 반복자에 대해서는 OK, 전방향 반복자로는 fail  //아래 코드는 전방향 OK, 출력반복자로는 X  while(pos != coll.end()){     *pos = foo();     ++pos;  }

       

 7.2.4 양방향 반복자

  전방향 반복자에 역순 순회 기능을 추가한 반복자.

  * 기능

   전방향 반복자 기능 전부에 역순 순회의 아래 두 기능이 추가됨

   1) 전방향 반복자의 기능 : 전부 추가

   2) --iter : 역방향으로 전진(새로운 위치 반환)

   3) iter--: 역방향으로 전진(기존 위치 반환)

 

 7.2.5 랜덤액세스 반복자

  랜덤 액세스가 가능한 양방향 반복자.

  * 기능

   1) 양방향 반복자의 모든 기능

   2) iter[n] ; 인덱스가 n인 원소의 액세스를 제공함

   3) iter+= n원소만큼 전방향 전진 (n이 음수면 역방향), -=의 경우 반대

   4) iter+n, n+iter / iter-n : n번째 이후/이전 원소의 반복자 반환

   5) iter1 – iter2 : iter1과 iter2의 거리 반환

   6) iter1 (비교연산자) iter2 : iter1과 iter2의 위치에 대해 판단한다.

  *랜덤 액세스 반복자는 다음과 같은 객체와 타입에 대해서만 제공됨

   -랜덤 액세스를 제공하는 컨테이너 (deque, vector), 스트링 (string, wstring), 기본배열

 

 7.2.6 vector반복자의 증,감소 문제

   일반적으로 임시 반복자를 증가/감소시킬 수 있으나 vector와 string에서는 불가능함.

  반복자를 클래스 형태로 구현하면 가능하지만, 기존의 포인터 형태로 구현시는 불가능. 이럴 경우

  에는 vector<type>::iterator iter = coll.beg로 iter라는 보조적인 객체를 만들어서 사용해야함.

 

  7.3 보조 반복자 함수

    advance(), distance(), iter_swap()을 통하여 랜덤 액세스 반복자만이 지원하는 기능을 다른 반

   복자에게도 제공함.

   7.3.1 advance()

    *반복자의 위치 변경에 사용

    * 프로토타입

void advance(InputIterator& pos, Dist n)

     - pos의 위치를 n원소만큼 증가/감소 시킨다. pos가 양방향 또는 랜덤액세스일 경우 음수가능

     - advance()로 이동시킨 위치가 end()를 넘어가는지에 대한 검사가 없음. 주의 필요.

    *랜덤액세스의 경우 위 함수는 상수복잡도를 가지나, 다른 반복자의 경우 ++pos를 n회 수행하

    므로 선형 복잡도를 가짐. 제네릭한 코드를 위해서는 advance를 사용해야 하지만 반복자 종류

    에 따른 성능 저하가 발생할 수 있음을 염두에 두어야 함

    예)

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에서만 그런지 확인 필요)

 

 

   7.3.2 distance()

    *반복자 간 위치차이를 계산하는데 사용

    * 프로토타입

Dist distance(InputIterator pos1, InputIterator pos2)

     - pos1, pos2사이의 거리를 반환. 둘 다 같은 컨테이너에 존재하는 원소를 가리켜야 함

     - 랜덤액세스 반복자가 아닐 경우 pos2는 pos1보다 크거나 같아야만 한다.

     - 반환값 Dist는 반복자 타입에 따른 difference_type 타입임

    * 랜덤액세스는 상수복잡도. 그 외에는 선형복잡도를 가짐. advance와 마찬가지로 반복자 종류

     에 따른 성능저하를 고려해야 함.

    예제)

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; }

    > distance()는 두 반복자 사이의 거리값을 반환(순서 무관).

     

   7.3.3 iter_swap()

    * 두 반복자가 가리키고 있는 값을 교체

    * 프로토타입

void iter_swap(ForwardIterator pos1, ForwardIterator 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 <-> char도 swap됨

 

7.4 반복자 어댑터

 7.4.1 역방향 반복자

   - 역순모드로 동작하기 위해 기존의 증가,감소 연산자를 재정의한 반복자.

   - 역방향 반복자의 경우 위치에서 하나 앞 원소의 값을 가리킨다.

                      -> 반복자 변환시 문제가 없음   

rbegin() : container::reverse_iterator(end())   rend() : container::reverse_iterator(begin())

   reverse_iterator예제

예제)

void print(int elem){    cout << elem << ' '; } void revitr(){    deque<int> col;    initCon(col,1,9);    deque<int>::iterator pos1;    pos1 = find(col.begin(), col.end(), 3);    deque<int>::iterator pos2;    pos2 = find(col.begin(), col.end(), 6);    for_each(pos1, pos2, print);    cout << endl;    deque<int>::reverse_iterator rpos1(pos1);    deque<int>::reverse_iterator rpos2(pos2);    for_each(rpos2, rpos1, print);    cout << endl; }

 

   1)base를 사용한 역방향 반복자를 일반 반복자로 전환하기     

iterator iter = riter.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; }

     > reveerse_iterator::base()로, 역방향 반복자를 반복자로 반환 가능하다.

     > 역방향 반복자의 경우 반복자가 참조하는 값이 하나 앞의 값이다. (같은 위치 대비 하나 앞 원소의 값을 표시)

 7.4.2 삽입반복자

   * 삽입반복자 : 새로운값을 할당하는 작업->새로운 값을 삽입하는 작업으로 변경시키는 반복자. 

                   모든 삽입 반복자는 출력반복자카테고리를 가짐.

   1) 삽입 반복자의 기능

     - 목적지반복자에 새로운 값을 할당함.

     - 삽입 반복자의 구현에 사용되는 트릭

      i) '*'연산자는 아무 동작도 하지 않는 것 처럼 구현한다. inserter는 *pos와 pos가 동일함

      ii) 할당연산자 ‘=’는 삽입하는 동작으로 대체됨. 삽입 반복자는 push_back, push_front, insert를

        호출한다.

    * 삽입 반복자의 경우 *pos=value대신에 pos=value를 사용할 수 있음

     - 삽입 반복자의 기능

        iter = value : value를 삽입함.

    * iter, iter++, ++iter : 아무런 동작도 하지 않음

  

   2) 삽입 반복자의 종류

      - 삽입 반복자는 3종류가 있음. 후위/전위/일반 삽입반복자. 차이는 원소를 삽입하고자 하는 위치의 차

       이. 이들이 호출하는 컨테이너의 멤버함수가 다르므로, 삽입반복자는 컨테이너와 함께 초기화 될 것.

     i) 후위삽입 반복자

       - 컨테이너의 push_back()함수를 호출해 컨테이너의 마지막에 값 삽입.

       - vector, deque, list, string에서만 제공되어 해당 컨테이너와만 동작 가능

     ii) 전위삽입 반복자

       - push_front()함수를 호출해 컨테이너의 제일 앞에 값 삽입

       - deque, list에서만 제공되어 해당 컨테이너와만 동작 가능

     iii) 일반적인 삽입 반복자

       - 두개의 인자와 함께 초기화 됨. (‘컨테이너’와 ‘삽입될위치’)

     iv) 연관 컨테이너를 위한 사용자 정의 반복자

       - 연관 컨테이너에서는 삽입 위치는 오직 힌트 뿐. 경우에 따라 역순의 순서를 가질 경우 프로그램의 수

        행 속도가 저해될 수 있음

 

 7.4.3 스트림 반복자

    - 알고리즘의 목적지나 소스에 스트림을 허용하는 반복자 어댑터.

   1) 출력스트림 반복자

     출력스트림을 통해 원소를 기록함.

    * 반복자의 동작

      - ostream_iterator<T>(ostream) : ostream에 대한 출력스트림 반복자 생성

      - ostream_iterator<T>(ostream, delim) : ostream에 대한 출력스트림 반복자 생성. 각 값 사이의 구분

        자는 delim을 따름

      - iter = value : ostream에 값을 기록 (ostream << value)

      - *iter, ++iter, iter++ : 아무런 동작 하지 않음.

      예제)

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에서 ++을 하고 값을 기록하나, 안하고 기록하나 둘 다 출력된다. 즉, 영향을 받지 않음

  

   2) 입력스트림 반복자

     입력스트림으로부터, 원소를 읽어들임. 입력스트림과 함께 초기화 되어야 함. 읽어오는 과정에서 의 에

    러, 읽어들일 길이에 대한 문제 때문에 종료위치가 필요함. 이 문제를 위해 “끝 스트림반복자”를 사용할 

    수 있음. 읽기 액세스 후 이 두 반복자를 비교해보아야 함.

   * 반복자의 동작

     - istream_iterator<T>() : ‘끝 스트림 반복자’ 생성

     - istream_iterator<T>(istream) : istream에 대해서 입력 스트림 반복자를 생성

     - *iter : 값을 반환.

     - iter->member : 실제 값에 대한 멤버를 반환

     - ++iter , iter++ : 다음값을 읽어들임. (그 위치 반환, 하나 뒤 반환)

     - iter1 == iter2 : iter1,과 iter2를 비교. ( !=비교 안함)

예제

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를 ++해주지 않으면 첫번째값만 무한출력     } }  입력   1 2 3 4   once : 1   once again: 1   once : 2   once again: 2   once : 3   once again: 3   once : 4   once again: 4

   > 위 코드에서 입력을 1 2 3 f 4로 입력하면 1 2 3 까지만 출력되고 프로그램은 종료됨

 

7.5 반복자 특성

  - 반복자는 자신만의 특징을 표현하는 카테고리가 있음.

  - 반복자 특성을 정의하기 위해 반복자 특성이라고 불리는 특별한 템플릿 구조체를 제공함.

   i) 모든 반복자가 모든 타입 정의를 제공함을 보장

   ii) 특별한 반복자 타입에 대해 전문화 될 수 있음

   * 반복자 특성 템플릿

     value_type, difference_type, iterator_category, pointer, reference 5개가 존재

 

 7.5.2 사용자 정의 반복자

   * 사용자가 정의한 반복자 특성 제공 방법

    i) iterator_traits 구조체에 대해서 필요한 5가지의 타입 정의를 제공

    ii) iterator_traits 구조체에 부분 전문화를 제공하는 방법

   예제)

   - 반복자 정의 

//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"); }

   > ++에서 자신을 리턴하도록 변경하였으므로 달라지는 동작이 없다

 

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