[STL] 반복자(5) - 속성

알고리즘 함수들은 반복자만 인수로 전달받을 뿐 컨테이너에 대해서는 알지 못한다.

 

그럼 알고리즘은 어떻게 반복자의 특성을 파악할 수 있을까?

 

사실 함수 입장에서는 어떠한 정보도 알 수 없다. 심지어 반복자인지 정수인지 조차도 분간할 수 없다.

 

하지만, 이를 분간하는 것을 필요로 하는 상황이 분명이 있기 때문에, STL은 반복자의 특징을 표현하기 위해 iterator_traits 클래스와 이 클래스를 보조하는 여러 가지 타입 정보를 정의한다.

template <typename Iter>
struct iterator_traits
{
	typedef typename Iter::iterator_category iterator_category; // 반복자의 종류
	typedef typename Iter::value_type value_type; // 반복자가 가리키는 대상체의 타입
	typedef typename Iter::difference_type difference_type; // 반복자끼리의 거리를 표현하는 타입
	typedef typename Iter::pointer pointer;
	typedef typename Iter::reference reference;
};

 

위에서 볼 수 있듯이 `iterator_traits` 클래스는 멤버를 가지지 않고 타입만 정의하는 빈 클래스다. 

 

반복자 타입 `Iter`를 템플릿 인수로 전달하면 `Iter` 반복자가 정의하는 타입을 약속된 이름으로 재정의하는 역할을 할 뿐이다.

 

반복자의 종류는 다음과 같이 태그 이름이 정의되어 있다.

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

위는 모두 멤버를 가지지 않는 빈 구조체이면서 자기네들끼리 일종의 '상속 계층'을 구성하고 있다.

 

 

다음은 벡터와 리스트가 어떻게 iterator_traits을 정의하는지 살펴보겠다.

class vector_iterator {
	typedef random_access_iterator_tag iterator_category;
	typedef T value_type;
	...
}

class list_iterator {
	typedef bidirectional_iterator_tag iterator_category;
	typedef T value_type;
	...
}

벡터는 `random_access_iterator_tag`를`iterator_category`로 지정하고 `value_type`은 `T` 타입으로 정의하는데 이때 `T`는 벡터의 템플릿 인수로 전달된 타입이 될 것이다.

 

리스트는 양방향 반복자를 반복자 카테고리로 지정한 것을 알 수 있다.

 

각 반복자 클래스가 이렇게 자신의 정체와 자신과 관련된 타입을 '약속된 이름'으로 밝혀 놓으면 `iterator_traits` 클래스는 이 이름들을 외부에서 일관되게 사용할 수 있도록 제공한다.

 

예를 들어, 다음과 같이 벡터에 대한 반복자와 리스트에 대한 반복자가 있을 때 반복자를 `iterator_traits`의 '탬플릿 인수'로 전달하면 반복자에 대한 특징을 얻을 수 있다.

std::vector<int>::iterator vit;
std::list<int>::iterator lit;
iterator_traits<vit>::iterator_category; // 임의 접근이다.
iterator_traits<lit>::iterator_category; // 양방향이다.
iterator_category<vit>::value_type; // 정수를 가리킨다.

 

이를 이용하여 다음과 같이 알고리즘을 구현할 수 있다.

template <typename InIt>
void distance_impl(InIt first, InIt last, input_iterator_tag) {
	int d = 0;
	while (; first != last; ++first)
		++d;
	return d;
}

template <typename RanIt>
void distance_impl(RanIt first, RanIt last, random_access_iterator_tag) {
	return last - first;
}

template <typename Iter>
void distance(Iter first, Iter last) {
	return distance_impl(first, last, iterator_traits<Iter>::iterator_category());
}

위와 같이 `distance_imple`이라는 함수를 호출하되 세 번째 인수로 '반복자의 종류'를 전달하는 것이다.

 

이렇게 반복자 태그라는 것은 어떠한 유용한 정보를 담는 구조체가 아니라 단순히 타입만을 정의함으로써 오버로딩된 함수 중 적절한 함수를 선택하는 역할을 한다.

 

메모리 낭비도 없고 (빈 클래스라서) 타입이란 컴파일 중에만 사용되는 정보이며 모든 선택은 컴파일 중에 일어나므로 실행시의 효율 감소도 없다.