C++ Iterator 뜯어보기

C++ Iterator 뜯어보기
Photo by Gabriel Heinzer / Unsplash

C++ 에서 vector 와 같은 컨테이너들을 사용하다보면 마주하는 iterator. 이들은 어떻게 구현이 되어있는 것일까? 같이 함께 뜯어보자.

Iterator

Iterator의 정의

Iterator Pattern

  • 컨테이너의 구현 방법을 노출시키지 않으면서도 그 집합체 안에 들어있는 모든 항목에 접근할 수 있는 방법을 제공한다. iterator 를 통해서 컨테이너와 알고리즘을 분리할 수 있으며, 인터페이스를 고치지 않고 새로운 순회 구조 또한 구현할 수 있다.
  • 다양한 컨테이너에 대해서 공통된 형태의 iterator 를 구성함으로써 더 generic한 프로그래밍을 구현하는데 큰 도움이 된다.

STL Container

  • C++ 에서는 STL container의 내부 데이터 접근/순회 방식으로 iterator를 사용한다. iterator를 통해서 다양한 형태의 구조에 대해서 마치 포인터와 같이 데이터를 접근할 수 있으며, std::algorithm 에서도 다양한 컨테이너에 공통적으로 존재하는 iterator를 통해서 공통된 작업을 수행할 수 있다.
  • 예를 들어, 단순하게 연속적인 데이터를 저장하는 array, vector, string과 같은 클래스의 경우 내부 데이터를 가리키는 포인터 연산을 통해서 내부 데이터를 순회하며 algorithm 에 있는 다양한 템플릿 함수를 사용할 수 있겠지만, map, set, list, deque 와 같이 연속적인 데이터를 가지지 않는 컨테이너의 경우 단순히 포인터 연산만으로는 내부 데이터를 순회할 수 없다. 이 때, iterator를 통해 오버로딩된 operator를 이용하면, 내부 자료 구조를 이해하지 않더라도 포인터 연산과 유사한 방법으로 내부 데이터를 순회할 수 있다.

코드와 함께 이해하기

아래 설명에 활용되는 자료

  • 자료 1) C++ 98 standard

  • 자료 2) OLD_GCC libstdC++ (C++98)

libstdc++ 의 iterator의 구조

: iterator 를 끝까지 파고 들어가면 다음과 같은 구조만 덩그라니 있다.

template <class _Category, class _Tp, class _Distance = ptrdiff_t,
          class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator {
  typedef _Category  iterator_category;
  typedef _Tp        value_type;
  typedef _Distance  difference_type;
  typedef _Pointer   pointer;
  typedef _Reference reference;
};
  • std::iterator는 스스로 아무것도 할 수 없다. 결국 자료구조에 따라, iterator의 동작은 별개로 정의해야한다. 하지만, iteratorgeneric 하게 사용하기 위해서는 유저가 정의한 iterator안에 위에 정의된 iterator의 요소들을 가지고 있어야한다.
  • 이 요소를 가지고 있기 위해서 사용자가 정의하는 iteratorwrapping 혹은 상속을 통해서 위 구조를 내부적으로 가지고 있다. 이 과정에서 iterator_traits 가 이용된다.
  • iterator_traits에서 들고 있는 tag를 바탕으로, 이후 opreator 가 제한된다.

iterator_traits

  • iterator sturct 에서는 정작 iterator_traits 에 대한 언급이 없다. 그러면 iterator_traits 는 어디에 활용하는 것일까? 코드를 함께 살펴보자.
// iterator_traits 구현부
// 일반적인 iterator의 경우 아래 템플릿을 통해 생성될 것이다.
template <class Iter>
struct iterator_traits
{
	typedef typename Iter::difference_type		difference_type;
	typedef typename Iter::value_type			    value_type;
	typedef typename Iter::pointer			    	pointer;
	typedef typename Iter::reference			    reference;
	typedef typename Iter::iterator_category	iterator_category;
};
// 만약, 포인터 형태로 Iterator가 들어온다면, 아래 템플릿을 활용한다.
template<class T>
struct iterator_traits<T*>
{
	typedef ptrdiff_t						            difference_type;
	typedef T								                value_type;
	typedef T*							               	pointer;
	typedef T&							               	reference;
	typedef std::random_access_iterator_tag	iterator_category;
};

/*
...
*/
// custom iterator 구현부
template <class Iter>
class reverse_iterator:
	public std::iterator<typename iterator_traits<Iter>::iterator_category,
                    typename iterator_traits<Iter>::value_type,
                    typename iterator_traits<Iter>::difference_type,
                    typename iterator_traits<Iter>::pointer,
                    typename iterator_traits<Iter>::reference>
{
// implementation ...
}
  • iterator_traits 가 등장하는 부분은 iterator를 상속하는 부분이다.
  • iterator를 상속받기 위해서는 iterator에 활용되는 특질인 5가지의 typedef 에 관련한 부분이 필요하다. 그러나, iterator 단독으로는 이를 알아낼 수 없다. iterator 의 경우 typetemplate를 통해서 가져오기 때문이다.
  • iterator_traits 는 이 특질을 가져오기 위해서 활용된다. iterator_traits의 경우 크게 두 가지로 구분된다. 일반적으로 iterator를 받아 사용하여 iterator_traits 를 생성하는 방식과, pointer가 들어왔을 때 pointer에 맞는 특질을 생성하는 방식이다.
  • 일반적인 iterator의 경우, iterator 내부에 특질을 정의해두었을 것이다. 따라서, 내부의 type definition을 들고와서 이를 특질로 저장하면 된다. 그러나, pointer의 경우에는 그렇지 않다. pointer의 경우 type definition을 별도 가지고 있지않다. (int*iterator에 맞는 특질을 가지고 있지 않듯…) 대신, 일반적으로 포인터를 iterator로 사용하는 경우, random_access_iterator 의 특성을 가진다.
  • 따라서, 포인터에 대한 iterator_traits는 사용자가 별도 정의를 통해 iterator의 형태로 만들지 않아도, 단순히 template 을 통해 iterator의 형태를 가질 수 있도록 돕는다.
  • 결국, C++ 98의 iterator_traits의 경우, template를 통해서 pointeriterator 모두 iterator의 특질을 가질 수 있도록 유도하는 하나의 장치인 것이다.

iterator 구현 예시

  • 아래 __normal_iterator 의 경우 pointer 형태의 iterator 의 동작을 정의하는 역할을 한다. (gnu 2.90.8)
    • __normal_iterator 라는 classiterator가 아닌 pointer 와 같은 형태의 iterator를 가지고 있어, iterator의 형태로 wrapping하는데 활용된다.
    • 따라서 __normal_iteratorvector, string 과 같은 연속적 데이터를 활용하는 컨테이너에 사용된다.
// This iterator adapter is 'normal' in the sense that it does not
// change the semantics of any of the operators of its itererator
// parameter.  Its primary purpose is to convert an iterator that is
// not a class, e.g. a pointer, into an iterator that is a class.
// The _Container parameter exists solely so that different containers
// using this template can instantiate different types, even if the
// _Iterator parameter is the same.
template<typename _Iterator, typename _Container>
class __normal_iterator
  : public iterator<iterator_traits<_Iterator>::iterator_category,
                    iterator_traits<_Iterator>::value_type,
                    iterator_traits<_Iterator>::difference_type,
                    iterator_traits<_Iterator>::pointer,
                    iterator_traits<_Iterator>::reference>
{
public:

  typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;

  inline __normal_iterator() : _M_current() { }

  inline explicit __normal_iterator(const _Iterator& __i)
    : _M_current(__i) { }

  // Allow iterator to const_iterator conversion
  template<typename _Iter>
  inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
    : _M_current(__i.base()) { }

  // forward iterator requirements

  inline reference
  operator*() const
    { return *_M_current; }

  inline pointer
  operator->() const
    { return _M_current; }

  inline normal_iterator_type&
  operator++()
    { ++_M_current; return *this; }

  inline normal_iterator_type
  operator++(int)
    { return __normal_iterator(_M_current++); }

  // bidirectional iterator requirements

  inline normal_iterator_type&
  operator--()
    { --_M_current; return *this; }

  inline normal_iterator_type
  operator--(int)
    { return __normal_iterator(_M_current--); }

  // random access iterator requirements

  inline reference
  operator[](const difference_type& __n) const
    { return _M_current[__n]; }

  inline normal_iterator_type&
  operator+=(const difference_type& __n)
    { _M_current += __n; return *this; }

  inline normal_iterator_type
  operator+(const difference_type& __n) const
    { return __normal_iterator(_M_current + __n); }

  inline normal_iterator_type&
  operator-=(const difference_type& __n)
    { _M_current -= __n; return *this; }

  inline normal_iterator_type
  operator-(const difference_type& __n) const
    { return __normal_iterator(_M_current - __n); }

  inline difference_type
  operator-(const normal_iterator_type& __i) const
    { return _M_current - __i._M_current; }

  const _Iterator& base() const
    { return _M_current; }

protected:
  _Iterator _M_current;
};
  • 위 코드를 잘 살펴보면, iterator의 멤버 변수 currenttemplate parameter_Iterator type로 정의된 것을 볼 수 있다. 그런데 결국 해당 클래스의 의도 상, pointertemplate_Iterator로 할당될 것이며, 내부 operationpointer 연산을 통해 작동하도록 정의됐다.

  • 두 번째 예시는 tree 구조를 사용하는 stl_mapiterator 구현이다.

// ... stl map
typedef _Rb_tree<key_type, value_type, 
                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
_Rep_type _M_t;
typedef typename _Rep_type::iterator iterator;
/*
 ...
*/

// _Rb_tree
typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
// 위와 같이 iterator type 에 대해 정의한 뒤
struct _Rb_tree_base_iterator
{
  typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
  typedef bidirectional_iterator_tag iterator_category;
  typedef ptrdiff_t difference_type;
  _Base_ptr _M_node;

  void _M_increment()
  {
    if (_M_node->_M_right != 0) {
      _M_node = _M_node->_M_right;
      while (_M_node->_M_left != 0)
        _M_node = _M_node->_M_left;
    }
    else {
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_right) {
        _M_node = __y;
        __y = __y->_M_parent;
      }
      if (_M_node->_M_right != __y)
        _M_node = __y;
    }
  }

  void _M_decrement()
  {
    if (_M_node->_M_color == _S_rb_tree_red &&
        _M_node->_M_parent->_M_parent == _M_node)
      _M_node = _M_node->_M_right;
    else if (_M_node->_M_left != 0) {
      _Base_ptr __y = _M_node->_M_left;
      while (__y->_M_right != 0)
        __y = __y->_M_right;
      _M_node = __y;
    }
    else {
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_left) {
        _M_node = __y;
        __y = __y->_M_parent;
      }
      _M_node = __y;
    }
  }
};

template <class _Value, class _Ref, class _Ptr>
struct _Rb_tree_iterator : public _Rb_tree_base_iterator
{
  typedef _Value value_type;
  typedef _Ref reference;
  typedef _Ptr pointer;
  typedef _Rb_tree_iterator<_Value, _Value&, _Value*>             
    iterator;
  typedef _Rb_tree_iterator<_Value, const _Value&, const _Value*> 
    const_iterator;
  typedef _Rb_tree_iterator<_Value, _Ref, _Ptr>                   
    _Self;
  typedef _Rb_tree_node<_Value>* _Link_type;

  _Rb_tree_iterator() {}
  _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
  _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }

  reference operator*() const { return _Link_type(_M_node)->_M_value_field; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  _Self& operator++() { _M_increment(); return *this; }
  _Self operator++(int) {
    _Self __tmp = *this;
    _M_increment();
    return __tmp;
  }
    
  _Self& operator--() { _M_decrement(); return *this; }
  _Self operator--(int) {
    _Self __tmp = *this;
    _M_decrement();
    return __tmp;
  }
};
// wrap{base_iterator} -> Rb_tree_iterator 와 같이 구성되고
// Rb_tree_iterator는 앞서 언급한 요건들을 충족한다. 
  • 구조를 살펴보면, mapRb_tree를 데이터 구조로 가지고 있다. 따라서, 이를 순회하기 위한 Rb_tree iterator를 별도로 가진다.
  • typedef typename _Rep_type::iterator iterator; 라는 부분을 통해서 mapiterator type을 정의했으며, 이 iterator 는 순회 방법에 활용하는 increment(), decrement() 와 몇가지 특질을 담는 base_iterator 를 상속받는다. (여기서는 std::iterator를 별도로 상속받지 않고, 필요한 특질을 직접 정의하는 방식을 채택했다.)
  • 그리고, iteratorbidirection_iterator 에서 순회하는데 활용되는 operator++, 를 정의함으로써, iterator의 동작을 정의했다.
  • 결국, 사용자는 iterator 자체에 정의된 operator를 통해 직접 순회를 할 수 있으며, algorithm 에서는 아래 설명할 iterator_category를 통해서 적절하게 순회를 할 수 있을 것이다.

iterator_category

  • iterator_category 를 통해서 특정 범주의 iterator에 대한 동작을 별개로 오버로딩할 수 있다. 이는 std::algorithmadvance() 를 통해 구현된다. 사용자는 advance 함수를 통해서 범주에 적합하게 iterator를 이동시킬 수 있다.
  • container를 만드는 사람의 관점에서는 내가 만든 iterator가 동작할 수 있는 operator의 범위를 제한하는 용도로 사용한다. 따라서 이에 맞게 iterator_category를 이해하고 iterator에 적절한 category를 부여하면 된다… 이 정도로 이해하면 될 것 같다.

[C++] iterator_category( 반복자 범주 )란 무엇인가?

reference

Writing a custom iterator in modern C++

[C++] iterator_traits( 반복자 특질 )이란 무엇인가?

Iterator pattern - Wikipedia