C++ Iterator 뜯어보기
C++ Iterator 는 어떻게 작동하는 것일까?
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_treeiterator를 별도로 가진다. 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를 부여하면 된다… 이 정도로 이해하면 될 것 같다.
[C++] iterator_category( 반복자 범주 )란 무엇인가?
reference
Writing a custom iterator in modern C++
