iterator: C++의 포인터 추상화

제목은 거창하지만(…), C++에서 흔히 사용되는 포인터의 추상화만 해도,

  • STL 컨테이너의 iterator — 일반화된 알고리즘;generic algorithm 을 포인터 없이 표현하기 위해, 그리고 템플릿 간의 상호적응;adaptation을 위해 iterator라는 추상화 단계를 뒀다
  • auto_ptr<T> — TR1 이전의 C++표준에 있던 유일한[…] 스마트 포인터다. 현재로썬 특수한 경우가 아니면 쓸 일이 -_-a
  • shared_ptr<T>, weak_ptr<T> — boost 혹은 C++ TR1의 일부인 스마트 포인터 템플릿이다. 멀티스레딩 환경에서도 상당히 편하게 쓸 수있는 구조로 되어있고, auto_ptr<T>의 소유권 문제를 겪지 않는다

정도가 존재 한다. 이 외에도 policy-based smart pointer인 loki 의 스마트 포인터나 ace library의 스마트 포인터도 있고…

일단 거기에서 일단 이 글에서 설명하려는 것은 iterator — 특히 이 앞 글에서 사용했던 output iterator 를 중심으로 설명하겠다. STL에 있는 iterator는 그 용도(=특성)에 따라 총 5종류가 존재하는데, instance를 it일 때 연산들을 설명해보면,

우선 가장 제한적인 iterator 두 종류.

  • input iterator — 값을 읽어들이기 위한 iterator 다. someVar = *it; ++it;를 해서 읽으면서 진행하는데 중점을 둔다. 참조;dereference 했을 때 (* 연산자), value_type 에 해당하는 값을 읽을 수 있다.
  • output iterator — 값을 써 넣기 위한 iterator. *it = someValue; ++r; 하는 식으로 쓰기 위한 녀석이다.

이 두 가지는 it++ 같은 연산의 타입이 void 인 경우가 대부분이고 — 즉 위치를 바꾸기만 하면 된다는 것 — 진행하고 나서 되 돌아가는 일이 없다 (=단방향으로 움직인다). 둘 다 [시작, 끝) 영역에 대해서 읽거나/쓰는데 중점을 두는 것인데, 이 앞 글에서 썼던,

std::set_intersection( A.begin(), A.end(), B.begin(), B.end(), OutputIteratorInstance );

같은 연산에서 "결과/출력 값을 쓰기 위해" 사용된다. 이 녀석을 실제로 구현할 때 필요한 연산은 몇 개 없는데,

  1. ++it, it++가 정의 될 것. 단 ++it 는 자기 자신의 타입의 리퍼런스를 반환해야함.
  2. "*it = 값" 이 정의되어야함 — 이게 원래 목적
  3. 다시 이전 iterator를 접근하는 일은 없음

정도의 가정/연산이 있으면 그만. *it 에서 반환하는 타입은 굳이 정의될 필요는 없는데, 흔히 일종의 proxy-type을 두고, 거기에 필요한 = 연산자를 타입별로 오버로딩한다 — 심지어 템플릿을 쓰기도 한다(…).

가장 흔하게 보게되는 애는 아마,

back_inserter( some_vector );

일 것 같은데, A, B가 set<int> 같은 녀석이면,[1]

vector<int> c;
set_intersection( A.begin(), A.end(), B.begin(), B.end(), back_inserter(c));

같이 쓰면 교집합한 결과가 c에 저장된다. 혹은 저 값을 저장해서 쓸 게 아니라 콘솔로 출력한다면, 그런 대로 자주 보게되는 ostream_iterator 라는 녀석을 써서

set_intersection( A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<int>( cout ) );

이런 함수를 통해 cout 으로 뿌려댈 수 있다. 근데 이런 연산으로 부족하다면, 위에서 설명한 output-iterator 의 조건을 만족하는 클래스를 짜버리면 된다. 예를 들어 제곱값을 출력하는(…) output-iterator는 다음처럼 정의할 수 있다.

struct FunctorOutputIterator
{
    FunctorOutputIterator() {};
    FunctorOutputIterator( const FunctorOutputIterator& rhs ) {} ;

    void operator++(int) { }
    inline FunctorOutputIterator& operator++() { return *this; };

    struct Contain
    {
        inline Contain& operator=( const int x )
        {
            cout << x*x << " " << endl;
            return *this;
        }

    } m_Con;

    inline Contain& operator*() { return this->m_Con; } 
};

살짝 길긴한데, Contain 이라는 proxy를 통해서 대입 연산자를 제공하고, 이걸 통해서 "대입한다는 개념"을 덮어써서 제곱값을 출력하게 했다.[2]

즉, duck-typing 스럽게[3] 추상화된 포인터인 C++의 iterator를 "따라 구현해서" 공간 낭비 없이 STL 특유의 효율적인 알고리즘을 쉽게 사용할 수 있게 해준다. 이런 식의 일반화 프로그래밍도 좀 공부해보면 — 특히 STL의 algorithm, iterator의 철학을 익히고, 그리고 boost의 lambda, function, functional 를 좀 써보면 — 괜찮은 코드를 별 타입문제 없이(=duck-typing!) 쉽게쉽게 쓸 수 있게된다 :)

 

References

  • SGI, Iterators Overview, http://www.sgi.com/tech/stl/Iterators.html — 이 곳에 있는 STL 의 개념 설명에 가까운 문서들이 무척 좋다[4]
  • D. Musser and G. Derge, "반복자", Chap 4., STL 튜토리얼 레퍼런스 가이드, 인포북
  1. 두 개가 정렬된 순서로 iterator를 내뱉어야함 []
  2. 비슷한 의미로 ostream_iterator는 대입이라는 연산이 stream 출력으로 대체 된 것이다, 직전에 쓴 글에서 했다고 말한 삽질에서는 저 구조체 전체를 template화 하고 function template을 대입연산자에서 실행하게 했다. []
  3. 오리처럼 걷고, 혜엄치고 울면 오리로 본다(?)는 duck-typing. 즉 필요한 연산이 같은 이름으로 존재하기만 하면 []
  4. 이걸 그냥 찍어내다시피한 책이 있고, 번역서가 있는데 이름이 기억이 안난다;;; []

Published by

rein

나는 ...

3 thoughts on “iterator: C++의 포인터 추상화”

Leave a Reply