CPP

C++ Iterator 뜯어보기

C++ Iterator 는 어떻게 작동하는 것일까?

Sungjun Park

2023년 1월 3일 — 9 min read

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의 동작은 별개로 정의해야한다. 하지만, iterator를 generic 하게 사용하기 위해서는 유저가 정의한 iterator안에 위에 정의된 iterator의 요소들을 가지고 있어야한다.
이 요소를 가지고 있기 위해서 사용자가 정의하는 iterator 는 wrapping 혹은 상속을 통해서 위 구조를 내부적으로 가지고 있다. 이 과정에서 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 의 경우 type을 template를 통해서 가져오기 때문이다.
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를 통해서 pointer와 iterator 모두 iterator의 특질을 가질 수 있도록 유도하는 하나의 장치인 것이다.

iterator 구현 예시

아래 __normal_iterator 의 경우 pointer 형태의 iterator 의 동작을 정의하는 역할을 한다. (gnu 2.90.8)
- __normal_iterator 라는 class는 iterator가 아닌 pointer 와 같은 형태의 iterator를 가지고 있어, iterator의 형태로 wrapping하는데 활용된다.
- 따라서 __normal_iterator는 vector, 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의 멤버 변수 current 가 template parameter인 _Iterator type로 정의된 것을 볼 수 있다. 그런데 결국 해당 클래스의 의도 상, pointer가 template 의 _Iterator로 할당될 것이며, 내부 operation은 pointer 연산을 통해 작동하도록 정의됐다.
두 번째 예시는 tree 구조를 사용하는 stl_map 의 iterator 구현이다.

// ... 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는 앞서 언급한 요건들을 충족한다.

구조를 살펴보면, map은 Rb_tree를 데이터 구조로 가지고 있다. 따라서, 이를 순회하기 위한 Rb_tree iterator를 별도로 가진다.
typedef typename _Rep_type::iterator iterator; 라는 부분을 통해서 map의 iterator type을 정의했으며, 이 iterator 는 순회 방법에 활용하는 increment(), decrement() 와 몇가지 특질을 담는 base_iterator 를 상속받는다. (여기서는 std::iterator를 별도로 상속받지 않고, 필요한 특질을 직접 정의하는 방식을 채택했다.)
그리고, iterator 를 bidirection_iterator 에서 순회하는데 활용되는 operator인 ++, — 를 정의함으로써, iterator의 동작을 정의했다.
결국, 사용자는 iterator 자체에 정의된 operator를 통해 직접 순회를 할 수 있으며, algorithm 에서는 아래 설명할 iterator_category를 통해서 적절하게 순회를 할 수 있을 것이다.

iterator_category

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