39-2-바.반복자의 속성

알고리즘 함수들은 임의의 컨테이너에 대해 동작하므로 반복자만 인수로 전달받을 뿐 컨테이너에 대해서는 알지 못한다. 하지만 때로는 반복자의 특성을 알면 좀 더 효율적으로 동작 가능한 경우가 많다. 여기서 반복자의 특성에는 일단은 순방향인지 임의 접근인지 등을 지정하는 반복자의 레벨이 가장 중요하고 그외 반복자가 가리키는 타입, 반복자의 거리를 표현하는 타입 등 반복자와 관련된 타입 정보들이 포함된다.

알고리즘이 인수로 반복자만 받았을 때 이 반복자만 가지고 특성을 어떻게 파악할 수 있을까? 사실 반복자 그 자체만 가지고는 어떠한 정보도 알아낼 수 없다. 우리가 InIt, BiIt, RanIt 등으로 반복자의 종류를 표기하는 것은 어디까지나 문서화를 위한 분류 방법일 뿐이지 컴파일러가 인식하는 타입은 아니다. 알고리즘 함수로 전달되는 반복자는 통상 템플릿의 인수이며 임의의 모든 타입이 전달될 수 있으므로 이 타입만 가지고는 반복자의 종류를 알아낼 수 없다. 심지어는 반복자인지 정수인지 조차도 분간할 수 없다.

하지만 현실적으로는 반복자의 특징이 필요한 경우도 있는데 STL은 반복자의 특징을 표현하기 위해 iterator_traits 클래스와 이 클래스를 보조하는 여러 가지 타입 정보를 정의한다. 이 정보는 사실 내부적으로 사용되기 때문에 최종 사용자가 굳이 알아야 할 필요는 없지만 STL을 더 잘 이해하기 위한 방편으로 내부를 분석해 보자. 단, 이후에 나오는 코드는 이해를 돕기 위해 꼭 필요한 것만 간추려 정리한 것이라 실제 컴파일러의 코드보다는 훨씬 더 개념적이다.

template<class 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 클래스는 멤버를 가지지 않고 타입만 정의하는 빈 클래스이다. iterator_category는 반복자의 종류를 지정하며 value_type은 반복자가 가리키는 대상체의 타입이고 difference_type은 반복자끼리의 거리를 표현하는 타입이다. 반복자 타입 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 클래스가 요구하는 타입들을 개별적으로 정의한다. 컨테이너별로 반복자의 특징이 달라지므로 이 타입들은 매 컨테이너마다 달라질 것이다. 대표적으로 벡터와 리스트의 반복자 클래스가 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;

....

벡터는 iterator_category 타입을 random_access_iterator_tag 타입으로 정의하여 자신이 임의 접근 반복자라는 것을 표시하고 있다. 그리고 value_type은 T 타입으로 정의하는데 이때 T는 벡터의 템플릿 인수로 전달된 타입이 될 것이다. vector<int> 타입에서 int가 곧 T로 전달되므로 반복자의 대상체도 int가 된다는 얘기다. 리스트의 반복자는 양방향 반복자이며 대상체의 타입은 역시 템플릿 인수로 전달된 T이다.

각 반복자 클래스가 이렇게 자신의 정체와 자신과 관련된 타입을 약속된 이름으로 밝혀 놓으면 iterator_traits 클래스는 이 이름들을 외부에서 일관되게 사용할 수 있도록 제공한다. 예를 들어 벡터에 대한 반복자와 리스트에 대한 반복자가 있을 때 반복자를 iterator_traits의 인수로 전달하면 반복자에 대한 여러 가지 특징을 얻을 수 있다.

vector<int>::iterator vit;

list<int>::iterator lit;

iterator_traits<vit>::iterator_category; // 임의 접근이다.

iterator_traits<lit>::iterator_category; // 양방향이다.

iterator_traits<vit>::value_type; // 정수를 가리킨다.

이런 정보들을 사용하면 알고리즘을 반복자 종류에 맞게 최적화시킬 수 있다. 대표적으로 반복자 사이의 거리를 구하는 distance 알고리즘의 구현 코드를 보자. 두 반복자의 거리를 구하는 방법은 반복자가 어떤 연산을 제공하는가에 따라 달라지는데 입력, 순방향, 양방향 반복자인 경우에는 다음과 같이 구해야 한다.

template<class InIt>

void distance_impl(InIt first,InIt last,input_iterator_tag) {

int d=0;

while(;first != last; ++first) ++d;

return d;

}

반복자끼리 연산할 수 없기 때문에 first가 last가 될 때까지 루프를 돌면서 카운트를 세는 수밖에 없다. 반면 임의 접근이 가능한 반복자인 경우는 뒤쪽 반복자에서 앞쪽 반복자를 빼기만 하면 단 한 방에 거리를 구할 수 있다.

template<class RanIt>

void distance_impl(RanIt first,RanIt last,random_access_iterator_tag) {

return last - first;

}

반복자의 종류에 따라 distance_impl이라는 이름으로 두 함수를 오버로딩해 놓았다. 세 번째 인수로 받는 반복자 태그 타입이 다르기 때문에 분명히 오버로딩 조건을 만족하고 있다. 하지만 이 함수가 실제 거리를 구하는 함수는 아니고 사용자가 아는 함수는 distance이다. 이 함수는 이제 다음과 같이 구현된다.

template<class Iter>

int distance(Iter first, Iter last) {

return distance_impl(first,last,iterator_traits<Iter>::iterator_category());

}

distance_impl이라는 함수를 호출하되 세 번째 인수로 반복자의 종류를 전달하는 것이다. 이 반복자가 입력용이면 위쪽 distance_impl 함수가 호출될 것이고 임의 접근이면 아래쪽 distance_impl 함수가 호출될 것이다. 순방향이나 양방향에 대해서는 별도로 함수를 정의하지 않는데 이 부류의 태그가 입력 반복자 태그의 파생 클래스이므로 굳이 함수를 따로 정의할 필요가 없다. 부모는 자식을 대입받을 수도 있고 가리킬 수도 있다. 이런 문법적인 이점을 활용하기 위해 반복자 태그가 계층을 이루고 있는 것이다. 출력 반복자에 대해서는 함수가 따로 정의되어 있지 않으므로 distance는 출력 반복자에 대해서는 쓸 수 없다.

결국 반복자 태그라는 것은 어떤 유용한 정보를 담는 구조체가 아니라 단순히 타입만을 정의함으로써 오버로딩된 함수 중 적절한 함수를 선택하는 역할을 한다. 이 선택에 관여하는 클래스는 모두 빈 클래스이므로 단 1바이트도 불필요하게 사용되지 않았다. 뿐만 아니라 타입이란 컴파일 중에만 사용되는 정보이며 모든 선택은 컴파일 중에 일어나므로 실행시의 효율 감소도 전혀 없다. distance 함수의 구현 코드를 좀 더 단순화해서 표현해 보면 다음과 같이 쓸 수 있다.

int distance(Iter first, Iter last) {

if (반복자가 입력용이면) {

하나, 둘, 셋, 넷 열심히 세서 리턴

} else {

뺄셈만 하면 됨.

}

}

if 문안에 있는 조건 판단을 위해 반복자의 타입만으로 특징을 조사할 수 있는 방법이 필요한데 iterator_traits 클래스와 반복자 태그들이 컴파일러가 인식할 수 있는 타입을 정의함으로써 특징을 판별할 수 있도록 한다. 이 정도 설명이면 내부 구조에 대해 약간의 감은 잡을 수 있을 것이다. 감이 확실히 잡혔으면 절묘하다는 감탄이 나올 만도 하다.

단, 여기서 보인 코드는 이해의 편의를 위해 간략화한 것이지 실제 코드가 아님은 분명히 하도록 하자. distance가 리턴하는 타입을 int로 기술했지만 더 정확하게 표현하면 iterator_traits<Iter>:: difference_type 으로 해야 옳다. 또한 각 반복자의 상수 버전에 대해, 요소의 포인터 버전에 대해서도 일일이 타입 정의를 해야 하며 컴파일러에 따라 이 클래스를 구현하는 방식도 천차 만별이라 일반적인 분석을 하기는 어렵다.

만약 기필코 정확한 내부 코드를 알고 싶다면 사용 컴파일러의 헤더 파일 사이를 헤엄치고 다녀야 한다. 학술적인 목적으로 꼭 연구해 보고 싶다면 굳이 말리지는 않겠지만 특정 컴파일러의 구현 방식을 이해하는 것은 그다지 큰 의미가 없으므로 권하고 싶지는 않다. 실제 코드는 훨씬 더 복잡하고 읽기 어려운데 아마 5분 정도 집중해서 읽다 보면 멀미가 날 것이다.