STL은 기본적으로 컨테이너(container) 및 반복자(iterator), 알고리즘(algorithm)의 템플릿이 구성되어 있지만, 이 외에 유틸리티(utility)라고 불리는 템플릿도 몇 개 들어 있습니다. 이들 중 하나가 advance라는 이름의 템플릿인데, 이 템플릿이 하는 일은 지정된 반복자를 지정된 거리(distance)만큼 이동시키는 것입니다. 간단한 개념만 놓고 볼 때 advance는 그냥 iter += d만 하면 될 것 같지만, 사실 이렇게 구현할 수는 없습니다. += 연산을 지원하는 반복자는 임의 접근 반복자밖에 없기 때문에, 임의 접근 반복자보다 기능적으로 떨어지는 다른 반복자 타입의 경우에는 ++ 혹은 -- 연산을 d번 적용하는 것으로 advance를 구현해야 합니다.
STL 반복자는 각 반복자가 지원하는 연산에 따라 다섯 개의 범주로 나뉩니다.
1. 입력 반복자(input iterator)는 전진만 가능하고, 한 번에 한 칸씩만 이동하며, 자신이 가리키는 위치에서 읽기만 가능한데다가, 그것도 읽을 수 있는 횟수가 한 번뿐입니다.
C++ 표준 라이브러리의 istream_iterator가 대표적인 입력 반복자입니다.
2. 출력 반복자(output iterator)는 입력 반복자와 비슷하지만 출력용인 점민 다릅니다.
즉, 오직 앞으로만 가고, 한 번에 한 칸씩만 이동하며, 자신이 가리키는 위치에서 쓰기만 가능한데다가 쓸 수 있는 횟수가 딱 한 번뿐입니다.
ostream_iterator가 이 부류의 대표주자입니다.
3. 순방향 반복자(forward iterator)는 입력 반복자와 출력 반복자가 하는 일은 기본적으로 다 할 수 있고, 여기에 덧붙여 자신이 가리키고 있는 위치에서 읽기와 쓰기를 동시에 할 수 있으며, 그것도 여러 번이 가능합니다.
STL은 원칙적으로 단일 연결 리스트를 제공하지 않지만 몇몇 라이브러리를 보면 제공하는 것들이 있는데(대개 slist입니다), 이 컨테이너에 쓰는 반복자가 바로 순방향 반복자입니다.
4. 양방향 반복자(bidirectional iterator)는 순방향 반복자에 뒤로 갈 수 있는 기능을 추가한 것입니다.
STL의 list에 쓰는 반복자가 바로 이 범주에 들어갑니다.
set, multiset, map, multimap 등의 컨테이너에도 양방향 반복자를 씁니다.
5. 임의 접근 반복자(random access iterator)는 양방향 반복자에 "반복자 산술 연산(iterator arithmetic)" 수행 기능을 추가한 것이죠.
쉽게 말해 주어진 반복자를 임의의 거리만큼 앞뒤로 이동시키는 일을 상수 시간 안에 할 수 있다는 것입니다.
C++ 표준 라이브러리의 vector, deque, string에 사용하는 반복자가 임의 접근 반복자입니다.
C++ 표준 라이브러리에는 지금까지 말씀드린 다섯 개의 반복자 범주 각각을 식별하는 데 쓰이는 "태그(tag) 구조체"가 정의되어 있습니다.
1 2 3 4 5 | 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_iterator_tag: public bidirectional_iterator_tag {}; | cs |
구조체들 사이의 상속 관계를 보면 is-a 관계인 것을 알 수 있는데, 딱 적합한 의미입니다. 이를테면 모든 순방향 반복자는 입력 반복자도 되니까요.
이제 advance로 돌아와서, 반복자들이 종류마다 가능한 것이 있고 불가능한 것이 있다는 점을 안 이상, 구현할 때 조금 신경을 써야 합니다. 한 가지 방법이라면 소위 최소 공통 분모(lowest-common-denominator) 전략을 들 수 있습니다. 반복자를 주어진 횟수만큼 반복적으로 (한 칸씩) 증가시키거나 감소시키는 루프를 돌리는 것이죠. 하지만 이 방법을 쓰면 선형 시간이 걸리기 때문에, 임의 접근 반복자 입장에서는 손해입니다. 그래서 임의 접근 반복자가 주어졌을 때는 상수 시간 연산을 이용할 수 있는 방법이 있었으면 좋겠습니다.1 2 3 4 5 6 7 8 9 10 11 | template<typename IterT, typename DistT> void advance(IterT& iter, DistT d) { if (iter가 임의 접근 반복자이다) { iter += d; } else { if (d >= 0) { while (d--) ++iter; } else { while (d++) --iter; } } } | cs |
위의 코드가 제대로 되려면 iter 부분이 임의 젭근 반복자인지를 판단할 수 있는 수단이 있어야 합니다. 그러니까, 이 iter의 타입인 IterT가 임의 접근 반복자 타입인지를 알아야 한다는 거죠. 여기서 이를 도와주는 것이 바로 특성정보(traits)인데, 컴파일 도중에 어떤 주어진 타입의 정보를 얻을 수 있게 하는 객체를 지칭하는 개념입니다.
특성정보는 C++에 미리 정의된 문법구조가 아니며, 키워드도 아닙니다. 그냥 C++ 프로그래머들이 따르는 구현 기법이며, 관례입니다. 특성정보가 되려면 몇 가지 요구사항이 지켜져야 하는데, 특성정보는 기본제공 타입과 사용자 정의 타입에서 모두 돌아가야 한다는 점이 그 중 하나입니다. 정확한 의미는 '특성정보 기법 포인터 등의 기본제공 타입에 적용할 수 있어야 한다'라는 것입니다. 이것은 어떤 타입 내에 중첩된 정보 등으로는 구현이 안 된다는 말로도 풀이할 수 있습니다. 결국, 어떤 특성정보는 그 타입의 외부에 존재하는 것이어야 하겠습니다. 특성정보를 다루는 표준적인 방법은 해당 특성정보를 템플릿 및 그 템플릿의 1개 이상의 특수화 버전에 넣는 것입니다. 반복자의 경우, 표준 라이브러리의 특성정보용 템플릿이 iterator_traits라는 이름으로 준비되어 있습니다.
1 2 | template<typename IterT> // 반복자 타입에 대한 struct iterator_traits; // 정보를 나타내는 | cs |
보다시피, iterator_traits는 구조체(어짜피 클래스) 템플릿입니다. 예전부터 이어져 온 관례에 따라, 특성정보는 항상 구현하는 것으로 굳어져 있습니다. 관례가 하나 더 있는데, 위처럼 특성정보를 구현하는 데 사용한 구조체를 가리켜 '특성정보 클래스'라고 부릅니다. iteraot_traits<IterT> 안에는 IterT 타입 각각에 대해 iterator_category라는 이름의 typedef 타입의 선언되어 있습니다. 이렇게 선언된 typedef 타입이 바로 IterT의 반복자 범주를 가리키는 것입니다.
iterator_traits 클래스는 이 반복자 범주를 두 부분으로 나누어 구현합니다. 첫 번째 부분은 사용자 정의 반복자 타입에 대한 구현인데, 사용자 정의 반복자 타입으로 하여금 iterator_category라는 이름의 typedef 타입을 내부에 가질 것을 요구사항으로 둡니다. 이때 이 typedef 타입은 해당 태그 구조체에 대응되어야 합니다. 예를 들어, deque의 반복자는 임의 접근 반복자이므로, deque 클래스(템플릿)에 쓸 수 있는 반복자는 다음과 같은 형태일 것입니다.
1 2 3 4 5 6 7 8 9 10 | template <...> // 템플릿 매개변수는 편의상 class deque { public: class iterator { public: typedef random_iterator_tag iterator_category; ... }; ... }; | cs |
다른 예로, list의 반복자는 양방향 반복자이기 때문에 다음과 같이 되어 있습니다.
1 2 3 4 5 6 7 8 9 10 | template <...> class list { public: class iterator { public: typedef bidirectional_iterator_tag iterator_category; ... }; ... }; | cs |
이 iterator 클래스가 내부에 지닌 종첩 typedef 타입을 앵무새처럼 똑같이 재생한 것이 iterator_traits입니다.
1 2 3 4 5 | template<typename IterT> struct iterator_traits { struct typename IterT::iterator_category iterator_category; ... }; | cs |
위의 코드는 확실히 사용자 정의 타입에 대해서는 잘 돌아가지만, 반복자의 실제 타입이 포인터인 경우에는 전혀 안 돌아갑니다. 포인터 안에 typedef 타입이 중첩된다는 것부터가 도무지 말이 안 되기 때문입니다. iterator_traits 구현의 두 번째 부분은 바로 반복자가 포인터인 경우의 처리입니다.
포인터 타입의 반복자를 지원하기 위해, iterator_traits는 포인터 타입에 대한 부분 템플릿 특수화(partial template specialization) 버전을 제공하고 있습니다. 사실 포인터의 동작 원리가 임의 접근 반복자와 똑같으므로, iterator_traits가 이런 식으로 지원하는 반복자 범주가 바로 임의 접근 반복자입니다.
1 2 3 4 5 6 | template<typename IterT> // 기본제공 포인터 타입에 struct iterator_traits<IterT*> // 부분 템플릿 특수화 { typedef random_access_iterator_tag iterator_category; ... }; | cs |
특성정보 클래스의 설계 및 구현 방법은 이렇습니다.
다른 사람이 사용하도록 열어 주고 싶은 타입 관련 정보를 확인합니다(예를 들어, 반복자라면 반복자 범주 등이 여기에 해당됩니다).
그 정보를 식별하기 위한 이름을 선택합니다(예: iterator_category).
지원하고자 하는 타입 관련 정보를 담은 템플릿 및 그 템플릿의 특수화 버전(예: iterator_traits)을 제공합니다.
이렇게 iterator_traits가 주어졌으므로 advance의 의사코드를 다음과 같이 다듬을 수 있습니다.
1 2 3 4 5 6 7 | template<typename IterT, typename DistT> void advance(IterT& iter, DistT d) { if (typeid(typename std::iterator_traits<IterT>::iterator_category) == typeid(std::random_access_iterator_tag)) ... } | cs |
잘 될 것 같지만 원하는 형태가 아닙니다. 첫 번째 걸림돌이 컴파일 문제인데, 일단 지금은 그보다 더 근본적인 문제를 해결해 봅시다. IterT의 타입은 아시다시피 컴파일 도중에 파악되기 때문에, iterator_traits<IterT>::iterator_category를 파악할 수 있는 때도 역시 컴파일 도중입니다. 하지만 if 문은 프로그램 실행 도중에 평가되기에, 컴파일 도중에 할 수 있는 것을 굳이 실행 도중에 해야 할 이유가 없습니다. 게다가 실행 코드의 크기도 비대해지겠죠.
주어진 타입에 대한 평가를 컴파일 도중에 수행하는 조건처리 구문요소는 C++에서는 오버로딩입니다. 어떤 함수 f를 오버로딩한다는 것은 매개변수 리스트가 다르지만 f라는 이름은 같은 오버로드 버전을 여러 개 만든다는 것입니다. 이 상태에서 f를 호출하면, 컴파일러는 여러분이 넘긴 인자를 보고 호출 시의 전후관계에 가장 잘 맞는 오버로드 버전을 골라냅니다. 이걸 써서 advance가 우리가 원하는 대로 동작하게 만들면 되는 거죠. advance의 "동작 원리 알맹이"는 똑같이 하고, 받아들이는 iterator_category 객체의 타입을 다르게 해서 오버로드 함수를 만듭니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | template<typename IterT, typename DistT> // 임의 접근 void doAdvance(IterT& iter, DistT d, // 반복자에 대해서는 std::random_access_iterator_tag) // 이 구현을 씁니다. { iter += d; } template<typename IterT, typename DistT> // 양방향 void doAdvance(IterT& iter, DistT d, // 반복자에 대해서는 std::bidirectional_iterator_tag) // 이 구현을 씁니다. { if (d >= 0) { while (d--) ++iter; } else { while (d++) --iter; } } template<typename IterT, typename DistT> // 입력 반복자에 대해서는 void doAdvance(IterT& iter, DistT d, // 이 구현을 씁니다. std::input_iterator_tag) { if (d < 0) { throw std::out_of_range("Negative distance"); } while (d--) ++iter; } | cs |
doAdvance 함수의 오버로딩도 마쳤겠다, 이제 advance가 해 줄 일은 오버로딩된 doAdvance를 호출하는 것뿐입니다. 이때 컴파일러가 오버로딩 모호성 해결을 통해 적합한 버전을 호출할 수 있도록 반복자 범주 타입 객체를 맞추어 전달해야 하겠지요.
1 2 3 4 5 6 7 8 9 | template<typename IterT, typename DistT> void advance(IterT& iter, DistT d) { doAdvance( // iter의 반복자 iter, d, // 범주에 적합한 typename // doAdvance의 std::iterator_traits<IterT>::iterator)category() // 오버로드 버전을 ); // 호출합니다. } | cs |
특성정보 클래스를 어떻게 사용하는지, 정리해 봅시다.
"작업자(worker)" 역할을 맡을 함수 혹은 함수 템플릿(예: doAdvance)을 특성정보 매개변수를 다르게 하여 오버로딩합니다.
그리고 전달되는 해당 특성정보에 맞추어 각 오버로드 버전을 구현합니다.
작업자를 호출하는 "주작업자(master)" 역할을 맡을 함수 혹은 함수 템플릿(예: advance)을 만듭니다.
이때 특성정보 클래스에서 제공되는 정보를 넘겨서 작업자를 호출하도록 구현합니다.
특성정보 클래스는 컴파일 도중에 사용할 수 있는 타입 관련 정보를 만들어냅니다.
또한 특성정보 클래스는 템플릿 및 템플릿 특수 버전을 사용하여 구현합니다.
함수 오버로딩 기법과 결합하여 특성정보 클래스를 사용하면, 컴파일 타임에 결정되는 타입별 if...else 점검문을 구사할 수 있습니다.