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;
};
C++
복사
•
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 ...
}
C++
복사
•
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;
};
C++
복사
•
위 코드를 잘 살펴보면, 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는 앞서 언급한 요건들을 충족한다.
C++
복사
•
구조를 살펴보면, 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를 부여하면 된다… 이 정도로 이해하면 될 것 같다.
