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

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

• STL 컨테이너의 iterator — 일반화된 알고리즘;generic algorithm 을 포인터 없이 표현하기 위해, 그리고 템플릿 간의 상호적응;adaptation을 위해 iterator라는 추상화 단계를 뒀다
• auto_ptr<T> — TR1 이전의 C++표준에 있던 유일한 스마트 포인터다. 현재로썬 특수한 경우가 아니면 쓸 일이 없다
• 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> 같은 타입이면,¹

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

같이 쓰면 교집합한 결과가 c에 저장된다. 혹은 저 값을 저장해서 쓸 게 아니라 콘솔로 출력한다면, ostream_iterator<T> 를 써서

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를 통해서 대입 연산자를 제공하고, 이걸 통해서 “대입한다는 개념"을 덮어써서 제곱값을 출력하게 했다.²

즉, duck-typing 스럽게³ 추상화된 포인터인 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 의 개념 설명에 가까운 문서들이 무척 좋다 ((이걸 그냥 찍어내다시피한 책이 있고, 번역서가 있는데 이름이 기억이 안난다;;; ))
• D. Musser and G. Derge, “반복자”, Chap 4., STL 튜토리얼 레퍼런스 가이드, 인포북