iterator_traits( 반복자 특질 )이란 무엇인가?

http://dev.log.mumbi.net/497

1. 알고리즘( algorithm )의 일반화.
  알고리즘의 일반화라는 것은 어떠한 컨테이너( container )도 그 알고리즘을 사용할 수 있게 만드는 것이다.

이 때, 그 알고리즘은 대상 컨테이너를 순회하기 위해서 컨테이너의 반복자를 사용한다. 보통, 시작을 가리키는 반복자와, 끝을 가리키는 반복자를 사용하고 끝을 가리키는 반복자는 순회에 포함되지 않고 컨테이너의 마지막 요소 다음을 가리킨다.

여기서 중요한 사실은 STL( Standard Template Library )이 제공하는 알고리즘이 제공하는 컨테이너 뿐 아니라 기본 배열에도 사용할 수 있게 C++ 표준이 지정되었다.

특정한 형을 사용하는 알고리즘을 일반화 시켜보면..

1. int 형 배열의 모든 원소의 합을 구하여 반환하는 함수.
 int Sum( int* _pFirst, int* _pLast )
{
    int sum = *_pFirst++;
 
    while( _pFirst != _pLast )
        sum += *_pFirst++;
 
    return sum;
}

배열의 첫 요소의 주소와 마지막 요소의 다음 주소를 인자로 받아 각 요소들을 순회하면서 합을 구한다.

2. 배열을 비롯한 모든 컨테이너에서 사용하기 위해 템플릿( template )을 적용한 일반화된 함수.
 template< class IteratorType >
 Sum( IteratorType _first, IteratorType _last )
{
    ???? sum = *_first++;
 
    while( _first != _last )
        sum += *_first++;
 
    return sum;
}

컨테이너에서는 포인터( pointer )를 일반화한 반복자( iterator )를 사용하기 때문에 시작을 가리키는 반복자와 끝을 가리키는 반복자를 인수로 받아 각 요소들을 순회하면서 합을 구한다.

그런데 요소들의 타입( type )을 모르기 때문에 그 합의 타입도 알 수 없다.

3. 반복자가 가리키는 타입 알려주는 value_type으로 일반화한 함수.
 template< class IteratorType >
typename IteratorType::value_type Sum( IteratorType _first, IteratorType _last )
{
    typename IteratorType::value_type sum = *_first++;
 
    while( _first != _last )
        sum += *_first++;
 
    return sum;
}

컨테이너의 반복자는 value_type이라는 타입을 제공한다. 반복자의 value_type은 반복자가 가리키는요소의 타입이다.

하지만 컨테이너의 반복자는 value_type을 제공하지만 기존의 포인터는 객체가 아니기 때문에 value_type을 제공하지 않으므로 배열에 대해서는 일반화되지 않았다.

배열의 포인터로 어떻게 요소의 타입을 알 수 있을까?

2. 템플릿 부분 특수화( partial specialization ).
배열의 요소 타입을 알아 내기 위해 템플릿의 부분 특수화를 알아야 한다.

[C++] 템플릿 특수화 ( template specialization )

STL 은 부분 특수화를 통해 iterator_traits 를 제공한다.

 template<class _iter="">
    struct iterator_traits      // 포인터가 아닐 경우( 반복자 ).
    {   // get traits from iterator _Iter
    typedef typename _Iter::iterator_category iterator_category;
    typedef typename _Iter::value_type value_type;      // <--
    typedef typename _Iter::difference_type difference_type;
    typedef difference_type distance_type;  // retained
    typedef typename _Iter::pointer pointer;
    typedef typename _Iter::reference reference;
    };
 
template<class _ty="">
    struct iterator_traits<_Ty *> // 포인터일 경우.
    {   // get traits from pointer
    typedef random_access_iterator_tag iterator_category;
    typedef _Ty value_type;         // <--
    typedef ptrdiff_t difference_type;
    typedef ptrdiff_t distance_type;    // retained
    typedef _Ty *pointer;
    typedef _Ty& reference;
    };

 

위의 코드는 MSVC9 에서 제공하는 STL의 iterator_traits 이다.

부분 특수화를 이용해 포인터일 경우와 반복자일 경우의 value_type을 다르게 하여 제공한다.

3. iterator_traits.
결론적으로 iterator_traits 는 반복자 특질이라고 번역되지만 사실, 반복자와 배열의 포인터를 구분하기 위해서 만들어진 것이다.

알고리즘을 구현하고 있다면 iterator_traits 가 무엇인지 반드시 알아야 한다.

---

iterator_traits Class 

Visual Studio 2005

Other Versions

A template helper class used to specify all the critical type definitions that an iterator should have.

template<class Iterator>
   struct iterator_traits {
   typedef typename Iterator::iterator_category iterator_category;
   typedef typename Iterator::value_type value_type;
   typedef typename Iterator::difference_type difference_type;
   typedef typename Iterator::pointer pointer;
   typedef typename Iterator::reference reference;
   };
template<class Type>
   struct iterator_traits<Type*> {
   typedef random_access_iterator_tag iterator_category;
   typedef Type value_type;
   typedef ptrdiff_t difference_type;
   typedef Type *pointer;
   typedef Type& reference;
   };
template<class Type>
   struct iterator_traits<const Type*> {
   typedef random_access_iterator_tag iterator_category;
   typedef Type value_type;
   typedef ptrdiff_t difference_type;
   typedef const Type *pointer;
   typedef const Type& reference;
   };

Remarks

---

The template class defines the member types

• iterator_category: a synonym for Iterator::iterator_category.

• value_type: a synonym for Iterator::value_type.

• difference_type: a synonym for Iterator::difference_type.

• pointer: a synonym for Iterator::pointer.

• reference: a synonym for Iterator::reference.

The partial specializations determine the critical types associated with an object pointer of type Type * or const Type *.

In this implementation you can also use several template functions that do not make use of partial specialization:

template<class Category, class Type, class Diff>
C _Iter_cat(const iterator<Category, Ty, Diff>&);
template<class Ty>
    random_access_iterator_tag _Iter_cat(const Ty *);

template<class Category, class Ty, class Diff>
Ty *_Val_type(const iterator<Category, Ty, Diff>&);
template<class Ty>
    Ty *_Val_type(const Ty *);

template<class Category, class Ty, class Diff>
Diff *_Dist_type(const iterator<Category, Ty, Diff>&);
template<class Ty>
    ptrdiff_t *_Dist_type(const Ty *);

which determine several of the same types more indirectly. You use these functions as arguments on a function call. Their sole purpose is to supply a useful template class parameter to the called function.

Example

---

// iterator_traits.cpp
// compile with: /EHsc
#include <iostream>
#include <iterator>
#include <vector>
#include <list>

using namespace std;

template< class it >
void
function( it i1, it i2 )
{
   iterator_traits<it>::iterator_category cat;
   cout << typeid( cat ).name( ) << endl;
   while ( i1 != i2 )
   {
      iterator_traits<it>::value_type x;
      x = *i1;
      cout << x << " ";
      i1++;
   };   
   cout << endl;
};

int main( ) 
{
   vector<char> vc( 10,'a' );
   list<int> li( 10 );
   function( vc.begin( ), vc.end( ) );
   function( li.begin( ), li.end( ) );
}

Output

struct std::random_access_iterator_tag
a a a a a a a a a a 
struct std::bidirectional_iterator_tag
0 0 0 0 0 0 0 0 0 0 

Requirements

---

Header: <iterator>

See Also

---

Reference

<iterator> 
Thread Safety in the Standard C++ Library 
Standard Template Library