Generic Programming in C++ (3)

소개와 활용 III

1999-03-01·김재우26 min read

여태까지 진행된 논의를 기반으로 실제의 표준 라이브러리에 준하는 iterator 인터페이스와 그 기능적 특성을 좀더 깊이 살펴보도록 하자.

Iterator와 재사용성 #

이전 기사를 통해 여러 번 언급한 바와 같이 C++ 표준 라이브러리는 Algorithm-Iterator-Container로 구성된다. 여기서 Iterator는 Container와 algorithm의 지나친 의존관계를 제거하는 인터페이스 역할을 한다. 쉽게 말하자면 algorithm에서 필요한 것은 일련의 원소이고 Container는 원소의 모임이다. 결국 algorithm이 필요로 하는 것은 컨테이너 그 자체가 아니라 컨테이너의 원소를 하나 씩 가져 와서 사용할 수 있는 제어 기능이다. 그리고 그러한 제어기능을 추상화한 데이터 형이 Iterator다. Iterator는 algorithm과 container 양쪽의 직접적인 의존성을 제거하는 중요한 추상화 수단이며 결과적으로 얻게 되는 효과는 극도의 재사용성이다.

재사용성은 일반적으로 효율성의 손실로 이어진다. 그러므로 재사용성을 목표로 잘 설계된 라이브러리 하더라도 일반화의 대가로 효율성을 손해 보게 되면 산업계에서는 빛을 보지 못하는 경우가 허다하다. 그러나 이번C++라이브러리의 주요 부품군인 STL은 다르다. 잘 아시다시피 STL은 Alexander Stepanov와 Meng Lee의 연구 성과다. 그 들은 C++ 언어 자체를 변화 시켜서라도 효율성과 일반성이라는 두 마리 토끼를 모두 잡으려고 무던한 노력을 하였고 여기에는 Bjarne Stroustrup 및 Andrew Koenig등의 잘 알려진 C++의 대가들이 가세하여 헌신적인 도움을 아끼지 않았다. STL의 설계자들이 주목한 C++언어의 기능은 바로 template이었다. 그들은 재사용 라이브러리의 주된 설계 및 구현 모델인 객체지향적 언어기능에 거의 의존하지 않았다. 객체지향적 기법을 채택하지 않은 한 가지 큰 요인은 실행성능의 저하 때문이었다. 비단 C++ 뿐만 아니라 모든 객체지향적 언어는 일반성과 확장성이라는 이득에 비례해서 실행성능의 저하라는 대가를 지불 해야 하기 때문이다. 객체지향적 재 사용성은 한 마디로 subtyping polymorphism에 의존하는 것이고 subtyping polymorphism의 일반적인 구현전략은 method overriding을 위한 dynamic binding이다. Dynamic binding이란 결국 indirection이며 성능의 감소는 필연적이다. 이에 반해 template에 기반한 C++의 generic 또는 parametric polymorphism은 컴파일러가 안정적으로 지원하기만 한다면 효율성의 감소가 거의 없다고 할 수 있다. STL의 기술적인 성공 덕택으로 C++를 위한 generic programming 기법은 확고한 위치를 차지하게 되었다고 할 수 있으며 이제 C++ 프로그래머라면 객체지향적 프로그래밍 기법과 더불어 양대 패러다임을 모두 잘 활용할 수 있어야만 한다. 이제 사설은 접어두고 본론으로 접어들 때가 되었다.

배열의 포인터와 Iterator #

표준 C++ 라이브러리의 Iterator가 cursor라 불리는 모델에 따라 설계되었다는 점은 지난 호에 이미 설명하였다. Cursor 방식만을 두고 얘기한다면 Iterator란 “포인터의 추상화"에 불과하다. 포인터의 사용방법을 이해하지 못하는 독자는 없겠지만 약간 다른 관점에서 이해하기 위해 간단히 포인터에 적용되는 연산을 정리하고 넘어가기로 하자.

포인터는 특정객체의 위치를 가리키는 객체다. 그러므로, 포인터 변수 p가 가리키는 원소를 얻어내려면:

*p

라고 operator*(dereference operator)(read/write)를 사용하면 된다. 다음으로, 만일 p가 배열의 특정원소를 가리키는 포인터 변수라면:

p++
++p

와 같이 위치이동을 하는 연산(2)이 가능하다. 위치이동 연산과 *를 사용하면 배열의 범위 내에 있는 모든 원소를 얻어낼 수 있다. 또한 p는 배열의 포인터기 때문에 subscript (index) 연산자(3)를 사용해서 random으로 다음과 같이 원소를 참조할 수 있다.

p[i] (== p + i)

물론 위의 모든 연산은 배열의 특정위치를 가리키는 포인터 변수가 있을 때 사용할 수 연산들이다.

부가적으로 C/C++의 배열에는 아주 심각한 문제가 있다는 점을 지적하고 넘어가야 하겠다. 포인터변수를 사용해서 배열을 조작하는 경우 배열의 크기를 알 수가 없기 때문에 프로그래머는 포인터 연산을 하거나 indexing을 하는 경우 본래 배열의 범위를 넘지않는지 항시 검사할 필요가 있다. 여러 가지 방법이 있겠지만 미리 배열의 마지막 원소, 바로 그 다음(past-the-end pointer) 위치를 기억해두고 변호하는 포인터가 이 값을 넘어서지 않도록 검사하난 것이다.

int a[4] = { 1, 2, 3, 4 };
int* p= a;
int* const end = a + 4;
while (p != end) { ...; p++; }

살펴본 바와 같이 배열의 포인터는 배열의 범위 내에 있는 모든 원소를 변경하고 추출해낼 수 있는 Iterator라는 점을 인식하는 것이 중요하다. 배열은 바로 Built-in Container이며 결국 오래 전부터 (Random-Accessible) Container인 배열과 (random-access) Iterator인 배열의 포인터를 사용해 왔던 것이다. 즉 이번 표준 라이브러리의 핵심적인 인터페이스이자 전체 라이브러리의 재사용성을 극대화하는 Iterator는 결코 생소한 개념이 아니다.

그렇다면 어떻게 포인터 연산이 추상화된 cursor기반의 Iterator 인터페이스로 사용될 수 있는 것일까? 왜 하필이면 그와 같은 인터페이스를 채택하였을까? 우선 C++는 operator overloading라는 ad hoc polymorphism을 지원한다는 점을 떠올리자. 다시 말하자면 operator*()/ operator++(int)/ operator++()/ operator[]등은 모두 새로운 type을 위해 얼마든지 재정의 할 수 있는 연산자이므로 그 의미만을 충실히 준수한다면 사용하는데 아무런 무리가 없다. 다음으로 만일 포인터 연산자 이외의 다른 인터페이스를 채택한다면 C언어의 배열을 표준적인 컨테이너에서 제외시켜야만 한다. 라이브러리의 설계자들은 새로운 인터페이스를 고안하기 보다 C++ 언어와 무리 없이 결합하여 사용할 수 있는 인터페이스를 원했고 operator overloading은 충분히 좋은 도구였던 것이다. 표준 라이브러리의 Iterator에 관한 논의는 다음 단락 “실제의 C++ 표준 라이브러리"에서 다시 진행되므로 이쯤에서 일단락 짓기로 하자. 독자들은 단지 포인터 연산 (1) (2) (3)이 각기 다른 성질을 대표하고 있다는 정도만을 상기하도록 하자.

일단 여태까지의 논의를 정리하기 위해서 지난 호에서 잠시 중단하였던 container/ iterator/algorithm의 기초적인 설계원리에 관한 실험을 마무리 지어야 할 때가 왔다.

Operator overloading을 사용한 인터페이스의 개선 #

몇 회에 걸쳐서 필자는 표준 라이브러리와 Generic Programming 원문에서는 “포괄적 프로그래밍"으로 표기했다. 이 연재 전체에 걸쳐 Generic Programming으로 고쳐 쓴다. 의 관계를 연거푸 강조하였다. 또한 이를 깊이 이해하기 위해서는 독자 스스로의 체험이 필요하다는 생각에서, 1에서 10까지 정수 값을 더하는 지극히 간단한 문제의 프로그램을 작성하고, 일반화 과정을 단계별로 설명하였다.

독자들은 문제가 극히 간단하다고 하더라도, 진정 “재사용성"을 이해하여 장기적인 안목에서 프로그래밍을 한다는 것이 얼마나 많은 사고의 깊이를 요구하는 일이며, 그 결과로 얼마만큼의 일반화가 가능한가를 충분히 느꼈으리라 믿는다. 결국 프로그래밍이란 해결하고자 하는 문제를 정확히 이해하고 적절한 문제의 해결책을 표현하는 것이다. 그러나 문제는 그러한 작업이 얼마나 가치가 있는 결과를 산출해 내느냐에 달려있다. 그리고 프로그래밍 연습이 많은 시간을 들여 공부할 만한 가치가 있는 것이냐에 대해 자문자답의 기회를 가져야만 한다. 만일 장기간의 교육 과정을 거치고도 여전히 for loop문을 사용해 단순한 합산을 구하는 일회 용 프로그램 정도밖에 작성해내지 못한다면 그와 같은 교육은 시간 낭비일 뿐이다. 프로그래밍 이란 결국 추상화와 알고리즘의 구현이기 때문이다.

그러므로 이 연재기사를 같이해온 독자라면 이 모든 논의가 지극히 단순한 문제를 해결하는 과정에서 시작되었다는 점을 다시 한번 돌이켜 볼 필요가 있다. 컨테이너- Iterator-algorithm의 구조는 결국 필연적인 것이었으며 본래의 단순한 문제의 답을 고안하는 과정에서 산출된 것으로 “재사용성을 위한 추상화의 자연스런 결과 물"인 것이다!

우선 이 전에 작성했던 generic algorithm을 살펴보고 그 구현을 C++ 답게 개선시켜서 좀더 표준 라이브러리에 근접하는 인터페이스를 유도해 보자. 쉬운 예로 만일 정수형 배열만을 위한 accumulate를 작성했다면 어떤 식으로 구현되었을 까? 여러 가지 방법이 있겠지만 다음과 같이 하는 것도 나쁘지는 않다.

typedef int (BinaryOperation)(int, int);
typedef int (UnaryOperation)(int, int);
int accumulate(int* begin,int* end, int init,
    BinaryOperation binop, UnaryOperation f)
{
    while (begin != end)
    {
        init = binop(init, f(*begin));
        ++begin;
    }
    return init;
}

일단 위의 accumulate는 아래와 같이 C언어 수준에서도 유용하게 사용할 수 있는 함수다. 물론 while 문 내에서 f()함수를 빈번히 호출하기 때문에 효율적인 구현이라고는 할 수 없다.

#include <cstdio>

int plus(int x, int y) { return x+y; }
int id(int x) { return x; }

void usage()
{
    int a[] = {1, 2, 3, 4, 5};
    std::printf("sum [1~5] =  %d\n", accumulate(a, a + 5, 0, plus, id))
}

이제 위의 정수형 배열을 위한 accumulate(1)와 아래의 accumulate(2)의 유사점을 살펴보자. 물론 아래는 function template이니까 당연히 T를 int라고 생각하고 비교해보아야 하겠다.

template<class CT, typename T, class BinaryOperation, class UnaryOperation>
T accumulate(const CT& cont, T init, BinaryOperation binop, UnaryOperation f)
{
    typename CT::iterator iter = cont.elements();
    while (iter.hasNext())
    {
        init = binop(init, f(iter.elem()));
        iter.advance();
    }
    return init;
}

우선 (2)에서는 iterator를 직접 받는 대신에 iterator를 제공할 container, CT를 받는다는 점이 다르다. 그리고 (2)를 사용할 CT는 일정한 자격이 필요하다는 점에 주목하자. 즉, 임의의 Container CT는 CT::iterator라는 type attribute와 CT와 연관된 iterator를 얻어낼 수 있는 인터페이스, CT::elements()를 제공해야 한다. 또한 얻어낸 CT::iterator도 hasNext(), advance() 등의 인터페이스를 제공해야만 한다. 이와 같은 점을 제외하면 (1)과 (2)는 매우 유사하다. 좀더 상세하게 하나씩 비교해 보도록 하자.

(1)에서 begin != end는 의미상으로 더 이상 열거할 원소가 없다는 것을 확인하는 절차다. (2)에서는 iterator 인터페이스 hasNext()로 표현되는 부분이다. (1)에서 *begin은 (2)의 iter.elem()에 일치한다. 둘 다 현재 위치의 원소를 추출해내는 연산이다. 마지막으로 (1)에서 ++begin에 일치하는 (2)의 코드는 iter.advance()이다. 모두 다음에 열거할 원소가 저장된 위치로 cursor를 이동하는 연산이다.

안전성 측면에서 본다면 사실 (2)와 같은 방식은 충분히 훌륭한 구현일 뿐만 아니라 여러 가지 면에서 (1)보다도 안전한 구현이다. (1)과 같이 구현하면 다음과 같이 잘못 사용되는 경우를 본질적으로 막을 수가 없다. (사실 아래와 같은 문제점은 표준 라이브러리의 Iterator 인터페이스 정책이 가진 문제점과 정확히 일치한다.)

int absurd_use()
{
    int a[] = {1, 2, 3, 4, 5};
    int b[] = {6, 7, 8, 9, 10}
    return accumulate(a, b + 5, plus, id);
}

위의 예에서는 배열 a와 b가 서로 다른 컨테이너이고 각자의 포인터(Iterator)를 건네준다. 위험한 점은 begin 포인터(Iterator)와 end 포인터(Iterator)를 소유하는 컨테이너가 서로 다른데도 함수 내부에서는 그 점을 검증할 수 있는 방법이 없다는 점이다. 결국 begin이 증가해서 어떤 결과를 얻게 될지는 예측할 수 없다. 만일 b가 다행히도 a+5 다음에 연속적인 주소공간에 할당된다면 운이 좋은(?) 경우다. (Iterator가 단순히 포인터가 아닌 class로 구현된 경우라고 하더라도 동일한 문제가 발생한다. 독자들은 이러한 문제점을 분명히 이해하고 넘어가기 위해 스스로 검증을 해보는 기회를 갖기 바란다.) 그러나, (2)의 구현에서는 Iterator 대신에 컨테이너(Iterator를 소유하는 단일 객체)를 받기 때문에 그와 같은 문제가 아예 발생하지 않는다.

반대로 인터페이스의 기능면에서 본다면 (1)구현이 분명한 장점을 가지고 있다. 만일 배열과 같이 양방향 이동, 그리고 Indexing에 의한 Random 이동이 가능한 컨테이너의 (RandomAccessible)Iterator라면 (2) 같은 Iterator 인터페이스는 그와 같은 기능을 제공하지 못한다는 단점이 있다. (2)에서는 오로지 앞으로만(ForwardIterator) 움직일 수 있기 때문이다. 그러나 (2)의 정책이 (1)과 같은 기능을 공유할 수 있도록 개선하는 것은 매우 쉽다. 단순히 advance(n)자리에 n이 음수 값을 받을 수 있도록 하고 indexing 연산을 위해 T at(int index) 같은 연산을 더해주면 그 뿐이기 때문이다. 하지만 이미 ++, –, *, []등의 연산자가 overloading가능한 언어에서 별도의 문법을 사용한다는 것은 사용자 측면에서 그리 달가운 일이 아니다.

다음은 이전 기사에서 컨테이너와 Iterator를 설명하기 위해 사용했던 class template, vector다. 우리는 (1)에서 사용되었던 것과 같은 인터페이스를 제공하도록 Iterator 인터페이스만을 다음과 같이 수정하였다. 그리고 (1)과 같은 방식을 사용한다면 vector class의 경우엔 별도의 iterator class를 구현할 필요 조차도 없기 때문에 코드는 더욱 간단해 진다.

template<typename T>
class vector {
    size_t sz_;
    T * vec_;
public:
    typedef T value_type;
    explicit vector(size_t size, T init=T());
    ~vector() { delete[] vec_; }
    size_t size() const { return sz_; }
    const T& operator[](size_t i) const { return vec_[i]; }
    T& operator[](size_t i) { return vec_[i]; }

// 생략된 구현은 이전과 다를 바가 없다. 단지 Iterator에 주목하라.
    typedef T* iterator;
    iterator begin() { return vec_; }
    iterator end() { return begin()+size(); }

// 다른 컨테이너에서 원소를 복사해서 초기화하는 ctor를 추가
// member template이 사용되었음에 주목할 것
    template<class Iterator>
    vector(Iterator first, Iterator last)
    : sz_(last-first), vec_( new T[last-first])
    {
        copy(first, last, begin()); // 아래에서 소개된다.
    }
};

위와 같이 구현된다면 (2)의 구현도 다음과 같이 바꾸어야 한다.

template<typename CT, typename T,
    class BinaryOperation, class UnaryOperation>
inline T accumulate(const CT& cont, T init,
        BinaryOperation binop, UnaryOperation f)
{
    typename CT::iterator iter = cont.begin();
    while (iter != cont.end())
    {
        init = binop(init, f(*iter));
        ++iter;
    }
    return init;
}

또한 Iterator 인터페이스를 제공하는 두 컨테이너간의 원소의 복사를 간편하게 하기 위해서 copy를 다음과 같이 구현하자.

template<class Iterator>
inline Iterator copy(Iterator begin, Iterator end, Iterator result)
{ // copy의 구현은 (1)의 인터페이스 원칙을 따른 것이다.
    for (; begin != end; ++begin, ++result) *result = *begin;
    return result;
}

이제 다음과 같이 실험을 할 수 있다.

#include <iostream>
int main(int argc, char* argv[])
{
using namespace std;
    int a[] = { 1, 2, 3, 4, 5 };
    vector<int> v(a, a+5);
    cout << accumulate(v, 0, plus, id) << endl;
    return 0;
}

위의 코드가 무리 없이 수행되었는가? 그렇다면 사용하고 있는 컴파일러를 바꾸어야만 할 것 같다. 위의 코드는 제대로 수행되지 않아야 정상이다. accumulate가 요구하는 컨테이너는 const CT&인데 begin()은 const method가 아니므로 에러가 발생할 수 밖에 없는 상황이다. 이와 같은 결과는 필자가 const iterator의 필요성을 설명하기 위해 일부러 유도한 것이다. iterator는 전과달리 elem()이라는 method를 제공하지 않는다. 다만 operator*을 통해서 elem()의 기능을 제공한다. 그러므로 만일 const 컨테이너에서 얻어낸 iterator라면 당연히 원소의 변경이 불가능한 const iterator를 사용하도록 요구할 필요가 있다. 결과적으로 vector class를 위한 iterator 관련 인터페이스에 다음과 같이 몇 가지 기능을 추가할 필요가 있다.

template<class T>
class vector {
public:
    ...
    typedef const T* const_iterator;
    const_iterator begin() const { return vec_; }
    const_iterator end() const { return begin()+size(); }
};

그리고 accumulate는 원소의 변경이 필요 없는 알고리즘이므로 해당 문장을 다음과 같이 수정할 필요가 있다.

typename CT::const_iterator iter = cont.begin();
...

사실 미리 밝힌다면 표준 라이브러리가 제공하는 generic algorithm의 인터페이스 정책은 (1)과 같다. 다시 말해서 컨테이너를 직접 가져오기 보다는 Iterator를 받아온다. (1)과 같은 방식은 추상화 측면에서 (2)에 비해 명백한 장점이 있다. generic algorithm의 구현이 오로지 Iterator 인터페이스에만 의존하므로 컨테이너와는 완전히 분리되어 있다는 점이다. 아래는 그와 같은 이점을 보여주는 다소 극단적인 예라고 할 수 있다.

class succ {
    int init, step;
public:
    explicit succ(int v, int s=1)
        : init(v), step(s)
    {}
    const succ& operator*() const { return *this; }
    succ& operator*() { return *this; }
    operator int() const { return init; }
    succ& operator++() { init += step; return *this; }
    succ& operator--() { init -= step; return *this; }
};

// succ의 역할을 std::views::iota가 대신한다.
// operator*(), operator++() 등을 직접 구현할 필요 없이:
#include <ranges>

auto seq = std::views::iota(1, 11);          // 1, 2, …, 10
auto stepped = std::views::iota(0, 20)
             | std::views::stride(3);         // 0, 3, 6, …, 18 (C++23)

위에서 succ은 Bidirectional Iterator 인터페이스를 만족하는 class다. 그러나 일반적으로 다음 iterator처럼 어떤 컨테이너에 귀속되어있는 원소를 열거하는 iterator가 아니라 주어진 초기값 v를 기점으로 차례대로 무한히 원소를 열거하는 알고리즘 Iterator다. succ은 다음과 같이 사용될 수 있다.

int add_in_range_by_step(int first, int last, int step=1)
{
    return accumulate(succ(first, step), succ(last+1), 0, plus, id);
}

#include <ranges>
#include <numeric>

int add_in_range_by_step(int first, int last, int step = 1) {
    auto range = std::views::iota(first, last + 1)
               | std::views::stride(step);          // C++23
    return std::accumulate(range.begin(), range.end(), 0);
}

게다가 copy의 구현을 다음과 같이 초기화 한다면 vector와 같은 컨테이너를 초기화하는데 직접 사용할 수 있다.

template<class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator begin, InputIterator end, OutputIterator result)
{
    for (; begin != end; ++begin, ++result) *result = *begin;
    return result;
}

void succ_use2()
{
    succ first(1), last(11);
    vector<int> v(first, last);
    ...
}

#include <ranges>
#include <vector>
#include <algorithm>

void iota_use() {
    // succ + copy 대신 std::views::iota로 직접 초기화
    auto seq = std::views::iota(1, 11);
    std::vector<int> v(seq.begin(), seq.end());

    // 또는 ranges::copy
    std::vector<int> v2(10);
    std::ranges::copy(seq, v2.begin());
}

그러나 앞서 지적한 바와 같이 표준 라이브러리의 Iterator와 알고리즘의 인터페이스 정책은 결코 안전하지 않다는 점을 반드시 지적해야만 하겠다. 다시 말해서 표준 라이브러리가 제공하는 대부분의 알고리즘은 처리할 원소의 범위를 지정하기 위하여 두개의 Iterator 인자를 요구한다. 그리고 두개의 Iterator 인자는 같은 당연히 같은 형이어야 하고 하나의 컨테이너에서 생성한 것이라야 한다. 그러나 동형의 서로 다른 Iterator가 주어져도 단일 컨테이너 객체에서 생성되었다는 사실을 검증할 방법이 없다. 그리고 copy를 보라. 값이 복사되는 OutputIterator result의 범위는 최소한 end - begin는 되어야 하지만 그 구현내부에는 아무런 검증기능이 없다. 그리고 주어진 인자로는 그러한 경우를 검출할 방법이 없다. 모든 위험은 사용자가 책임지고 막아야만 한다.

실제의 표준 라이브러리 #

Iterator category를 이해하자 #

C++ 표준 라이브러리가 제공하는 Iterator는 연산의 성질에 따라 다섯 가지로 분류된다. InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator, RandomAccessIterator.

(처음 이와 같은 용어를 접하면 조금 당황하게 되지만 특별히 이해하기 어려운 개념이 아니므로 하나 씩 살펴보면서 용도를 이해하기만 하면 된다. 앞 단락에서 언급한 포인터 연산을 성질에 따라 분류한 것에 지나지 않는다) 이들 5개의 Iterator category들은 연산의 성질에 따라 다음과 같이 계층구조적으로 연관되어있다.

struct InputIterator {};
struct OutputIterator {};
struct ForwardIterator : public InputIterator, OutputIterator {}
struct BidirectionalIterator : public ForwardIterator {}
struct RandomAccessIterator : public BidirectionalIterator {}

위와 같은 계층구조적 관계를 이해하는데 매우 주의해야 할 점은 위의 C++ 식의 계층구조는 이해의 편의를 위하여 C++ 문법으로 표현한 것일 뿐이지 실제로 Iterator를 표현하는 class가 별도로 구현되고 위와 같이 public derivation으로 구현된 것이 아니라는 점을 명심할 필요가 있다. 물론 객체지향적 구현 기법을 사용할 수 없는 것은 아니지만 표준 라이브러리가 채택한 주된 프로그래밍 전략은 Generic Programming이기 때문이다.

위에서 제시한 분류방식을 이해하기 위해 iterator category마다 적용될 수 있는 연산을 살폅도록 하자. 가장 단순한 Iterator는 OutputIterator다.

Let p : OutputIterator
   v, *p : T
        *p =  v (write)
        ++p, p++  (iteration)

다음으로 InputIterator는:

Let p, k : InputIterator
   v, *p : T
        v = *p (read)
        p->
        ++p, p++  (iteration)
        p ==k , p !=  k (equality comparable)

ForwardIterator는 InputIterator이자 OutputIterator다. 그러므로 위의 두 category가 제공하는 모든 연산을 사용할 수 있다. Bidirectional Iterator는:

Let p : BidirectionalIterator
        p should be a ForwardIterator
        --p, p--

마지막으로 RandomAccessIterator는:

Let p, k : RandomAccessIterator, i : RandomAccessIterator::difference_type
        p should be a BidirectionalIterator
        p[i]
        p +=  k, p -= k
        p < k, p > k, p >= k, p <= k (Ordered)

위와 같이 Iterator의 분류는 매우 직관적이고 배우기 쉽다. 문법이 일반적인 포인터의 조작과 크게 다를 바가 없기 때문이다. 사실 위와 같은 분류에 따르자면 포인터 변수는 RandomAccessIterator에 포함된다. 그러므로 Iterator의 사용자는 위와 같은 개념적 구분이 필요한 이유를 잘 이해하는 것이 더 중요하다. 우선 위에서 언급한 accumulate를 보자. accumulate를 사용하는 데 필요한 Iterator연산은 *p, p++ 가 전부이므로 입력되는 Iterator의 category는 InputIterator다. 한편 copy는 두 category의 서로 다른 iterator가 필요한 알고리즘이다. 하나는 입력을 위해서 다른 하나는 출력을 위해서 사용된다. 그러므로 copy algorithm을 사용하는 Iterator는 InputIterator와 OutputIterator다. (Iterator 인터페이스를 사용하는 프로시저를 구현하는 경우 type 인자의 명칭에 category의 이름을 사용하면 알고리즘이 요구하는 type constraint를 잘 표현할 수 있다.)

template<class InputIterator, class T, class BinaryOperation, class UnaryOperation>
inline T accumulate(InputIterator begin, InputIterator end, T init,
    BinaryOperation binop, UnaryOperation f) { ... }

위와 본 바와 같이 Iterator를 적용 가능한 연산의 성질에 따라 개념적으로 구분하는 이유는 서로 다른 algorithm이 요구하는 Iterator가 어떤 종류의 연산을 제공해야만 하는 지를 체계적으로 구정할 수 있기 때문이다. 예를 들어 header를 통해 제공되는 generate를 살펴보자. generate는 다음과 같이 사용되는 function template이다.

#include <algorithm>
#include <cstdlib>
#include <ctime>

template<class Forward>
void get_n_random_numbers(Forward first, Foward last)
{
using namespace std;
   srand( (unsigned)time( NULL ) );
   generate(first, last, rand)
}

// Usage
#include <vector>
int main()
{
using namespace std;
    vector<int> v (10);
    get_n_random_numbers(v.begin(), v.end());
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
}

#include <algorithm>
#include <random>
#include <vector>
#include <iostream>
#include <iterator>

template<std::forward_iterator Forward>   // concept으로 제약
void get_n_random_numbers(Forward first, Forward last)
{
    std::mt19937 gen{std::random_device{}()};
    std::uniform_int_distribution<int> dist(0, RAND_MAX);
    std::ranges::generate(first, last, [&]{ return dist(gen); });
}

int main()
{
    std::vector<int> v(10);
    get_n_random_numbers(v.begin(), v.end());
    std::ranges::copy(v, std::ostream_iterator<int>(std::cout, " "));
}

위에서 get_n_random_numbers는 generate를 사용해서 구현되고 이 함수의 사용자는 ForwardIterator가 필요하다는 사실을 알아야만 한다. generate는 다음과 같이 구현되기 때문이다.

template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen) {
  for ( ; first != last; ++first) *first = gen();
}

generate의 인자로 사용되는 Iterator를 i, j라고 한다면:

• i != j(equality comparable)
• ++i (iteration)
• *i = x (write)

가 가능해야 한다. Iterator category에서 위의 연산을 모두 제공하는 가장 일반적인(또는 가장 관용적인) iterator category는 ForwardIterator다.

두 마리 토끼를 잡는 법: Enhancing Generality without loss of efficiency #

앞 단락에서 언급한 것처럼 Iterator는 여러 가지 속성을 가진 객체다. 표준 C++라이브러리가 정의하는 Iterator의 속성은 다음과 같이 Iterator class의 type attributes로 표현될 수 있다. (Iterator관련된 모든 기본적인 기능들은 header에서 제공한다.)

template <class Category, class T,
    class Distance=ptrdiff_t,
    class Pointer=T*, class Reference=T&>
struct iterator {
  typedef Category  iterator_category;
  typedef T         value_type;
  typedef Distance  difference_type;
  typedef Pointer   pointer;
  typedef Reference reference;
};

즉, 모든 iterator 형은 iterator::value_type과 같은 방식으로 연관된 속성정보를 얻어올 수 있어야 한다. 또한, Iterator를 위한 base class가 C++ OOP 기능을 이용하여 iterator를 구현하고자 하는 것이 아니라는 점에 주목하자. iterator class는 아무런 구현도 method도 없으며 다만 새로운 iterator를 작성하는 경우 반복되고 잊어버리기 쉬운 코딩의 부담을 덜어주기 위해서 derivation을 이용하고 있을 뿐이다.

Iterator의 category 속성은 iterator tag를 사용하여 다음과 같이 표현될 수 있다.

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

위의 정보를 사용해서 나머지 iterator를 위한 일반적 base class를 쉽게 작성할 수 있다. 예를 들어 BidirectionalIterator 같은 경우라면:

template <class T, class Distance>
struct bidirectional_iterator : iterator<bidirectional_iterator_tag, T, Distance> {
};

물론 위와 같은 class는 예를 보이기 위한 것이지 무슨 특별히 쓸모가 있는 것은 아니다. 단지 누군가가 bidirectional_iterator category에 속하는 새로운 iterator를 class로 표현한다면 코딩의 부담을 완전히 덜어줄 수 있기는 하다.

template<class T, class Distance>
class my_iterator : public bidirectional_iterator<T, Distance> { ... }

위에서 인용한 바와 같이 iterator나 tag class가 필요한 것은 무슨 새로운 객체지향적 프로그래밍 기법을 예시 한다 기 보다 단지 C++의 template 기능을 보완하기 위해 사용되고 있다. C++의 template 기능은 언어처리과정이나 수행속도의 효율성을 고려하여 다소 불완전한 기능으로 설계되어 있는 것이 사실이다. 특히 tag는 overloading resolution을 보완하는 프로그래밍 기법에 활용된다. (언어가 제공하는 기능이 불완전하면 프로그래머는 그만큼 부질없는 곳에 더 신경을 기울일 수밖에 없다는 사실을 보여주는 좋은 예다.) 예를 들어 The C++ Programming Language 3rd에서의 제시하는 예를 살펴보자.

template<class InputIterator>
inline typename Iterator::difference_type
distance(InputIterator first, InputIterator last)
{ // O(n) time complexity
    typename Iterator::difference_type dist = 0;
    while (first++ != last) dist++;
    return dist;
}

distance는 주어진 두 iterator간의 range 값을 얻어내는 함수다. InputIterator라는 최소한의 요구사항을 만족하기만 한다면 어떤 category에 속하는 iterator라 하더라도 distance함수를 사용할 수 있다. 그러나 RandomAccessIterator라면 위와 같은 구현은 매우 비효율적이며 다음과 같이 간단한 연산으로 계산하는 편이 낫다.

template<class RandomAccessIterator>
inline typename RandomAccessIterator::difference_type
distance(RandomAccessIterator first, RandomAccessIterator last)
{ // O(1) time complexity
    return last - first;
}

문제는 위와 같이 동일한 이름의 동일한 parameter를 가진 template함수가 공존할 수 없다는 점이다. 그러므로 STL의 설계자들은 객체지향적 방법을 빌지않고 특정 category의 Iterator를 위해 특화된 구현을 제공할 수 있는 동시에 동일한 인터페이스를 제공할 수 있는 방법이 필요했다. Distance와 비슷한 예는 표준 라이브러리 전반에 산재해 있으므로 그 예제를 찾는 것은 그리 어렵지 않다.

만일 Iterator를 n 만큼 이동하는 연산 advance()를 구현한다고 가정하자. 그러면:

template<class UnknownIterator, class Distance, ...>
inline void advance(UnknownIterator& i, Distance n) { ... }

문제는 각각의 Iterator마다 적합한 알고리즘이 다르다는 것이다. ForwardIterator라면 i를 n만큼 하나씩 선형적으로 이동하는 방법이외에는 없으며 i를 되감을 수는 없기 때문에 n은 항시 양의 정수여야 한다. BidirectionalIterator경우 계산방식은 같지만 n이 음수인 경우에 뒤로 되감는 경우를 고려해야만 한다. RandomAccessIterator는 보다 효율적인 구현이 가능하다. 앞의 두 함수는 O(n)의 계산방식이 필요하지만 이 경우엔 n을 i에 가감하는 것만으로 충분하다O(1). 그러므로 Iterator의 category에 따라 별도의 함수가 제공되어야 하는 것이 합당하다. 그러나 사용자에게 자신이 사용하고 있는 Iterator의 category를 매번 확인하여 별도의 procedure를 사용하라고 하는 것은 너무 불편한 일이며 오류를 유발할 가능성도 짙다. 더 심각한 것은 advance를 사용하여 구현되는 함수가 특정 category의 iterator에 의존하게 되므로 generic 정의에 의한 재사용성을 막는다. (아무리 간단한 함수라 하더라도 그 연산이 매우 기초적인 기능을 수행한다면 그 파급효과는 무시할 수 없다.) 결국 효율성과 일반성을 모두 잡아낼 수 있는 프로그래밍 기법이 필요한 것이다. C++ overloading 기능의 특성을 잘 활용하면 원하는 목표를 쉽게 달성할 수 있다. 아이디어 그 자체는 매우 단순하다. 실제 사용되지는 않지만 C++ 의 type deduction기능을 보조해주는 부가적인 인자를 하나 더 추가하는 것이다.

#include <iterator> // 앞으로는 생략하기로 하자

template<class InputIterator, class Distance>
inline void advance_with_tag(InputIterator& iter, Distance n, std::input_iterator_tag)
{
     while (n--) ++iter;
}

ForwardIterator는 InputIterator와 같은 알고리즘을 사용하므로 별도의 구현이 필요 없다. 간단한 사용 예를 살펴보기 위해, 표준 라이브러리에서 InputIterator category에 속하는 유용한 iterator class를 사용해 보기로하자. istream_iterator 자체의 사용방법이야 InputIterator에 속하니까 어려울 게 없지만 생성자 인터페이스 만큼은 정확히 이해할 필요가 있다.

std::istream_iterator<T>  ii(istream&);

// 표준입력으로부터 입력된 정수를 표준출력으로 적어내는 함수
void get_and_print_integer()
{
using namespace std;
    // 표준 입력으로 부터 원하는 만큼 정보를 얻어와서 출력한다.
    istream_iterator<int> ii(cin);

    // 표준입력으로부터 얼마만큼의 입력을 받을 것인지는 미리 알 수 없다.
    // 그러므로 다른 iterator처럼 [begin, end)라는 범위는 완전히
    // 동적으로 결정된다. 그래서 istream_iterator는 the-end-of-file이나 어떤
    // 상황하에서 입력이 종결되면 istream_iterator<T>() 객체를 생성하여
    // 돌려준다.
    istream_iterator<int> iiend =  istream_iterator<int>();

    // 주목!!! 맨처음 입력된 3개의 정수를 무시하고 싶다.
    advance_with_tag(ii, 3, input_iterator_tag());

    ostream_iterator<int> oi(cout); // 표준출력으로의 OutputIterator
    copy(ii, iiend, oi);
}

이제 BidirectionalIterator, RandomAccessIterator를 위한 advance_with_tag를 작성하자.

template <class BidirectionalIterator, class Distance>
inline void advance_with_tag(BidirectionalIterator& bi, Distance n,
                      bidirectional_iterator_tag) {
    if (n > 0) while (n--) ++bi;
    else while (n++) --bi;
}

template <class BidirectionalIterator, class Distance>
inline void advance_with_tag(BidirectionalIterator& i, Distance n,
                      random_access_iterator_tag) {
  i += n;
}

이제 남은 것은 Iterator category에 따라 각기 다른 구현을 호출할 수 있는 인터페이스 함수를 구현하는 일이다. 임의의 iterator type의 type attribute, iterator_category를 사용하여 필요한 정보를 쉽게 추출해낼 수 있다.

template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
    return advance_with_tag(i, n, typename InputIterator::iterator_category());
}

// C++20 concepts + if constexpr — tag dispatch가 필요 없다.
template <std::input_iterator Iter>
constexpr void advance(Iter& i, std::iter_difference_t<Iter> n)
{
    if constexpr (std::random_access_iterator<Iter>) {
        i += n;
    } else if constexpr (std::bidirectional_iterator<Iter>) {
        if (n > 0) while (n--) ++i;
        else       while (n++) --i;
    } else {
        while (n--) ++i;
    }
}

사용자는 iterator의 category에 대한 정보를 명시적으로 제공해야 할 필요가 전혀 없기 때문에 advance를 사용하더라도 특정 iterator에 의존하지 않는 generic 함수를 작성할 수 있다. 헤더 파일을 통해 제공되는 거의 모든 알고리즘은 이와 같은 방식으로 작성된다.

마지막으로 표준 라이브러리가 제공하는 iterator_traits class가 왜 필요한 가를 이해하면서 이 단락을 마무리 짓도록 하자. traits class가 필요한 이유는 Iterator class로 구현되지 않았다 하더라도 표준 iterator의 속성을 공유할 수 있게 하기 위해서다. 만일 traits class가 없다면 class로 구현되지 않는 iterator는 위에서 distance나 advance같은 함수를 사용할 수가 없다. 정수배열의 int* 또는 앞에서 예로든 vector::iterator 같은 경우엔 Iterator::iterator_category같은 type attribute가 있을 수 없기 때문이다. 이러한 경우를 추상화하여 특정 class의 객체가 주어졌을 때 별도로 관련 속성을 얻어낼 수 있는 공통적인 방법이 필요하고 그러한 목적에 사용되는 것이 iterator_traits class다.

먼저 가장 일반적인 iterator_traits class는 다음과 같이 구현되어있다.

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;
};

그러나 위의 구현은 단지 class로 구현된 iterator를 위한 정의이고 T* (포인터) iterator를 위해서는 별도의 구현이 필요하다.

template <class T>
struct iterator_traits<T*> { // Built-in Iterator
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

template <class T>
struct iterator_traits<const T*> {
  ...
  typedef const T*                   pointer;
  typedef const T&                   reference;
};

iterator_traits class를 사용하여 advance를 수정하면:

template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
    return advance_with_tag(i, n, typename iterator_traits<InputIterator>::iterator_category());
}

위와 같다. 그리고 단순 배열이라고 해도 advance/distance같은 함수를 사용할 수 있다는 점이 무엇보다도 중요하다.

typename iterator_traits::iterator_category()란 이름이 길고 불편하다고 느끼면 다음처럼 주어진 Iterator의 category 객체를 만들어주는 함수로 구현하면 매우 편리하고 코드도 말끔해진다.

template<Iterator>
typename iterator_traits<Iterator>::iterator_category
category(Iterator)
{
    return typename iterator_traits<Iterator>::iterator_category();
}

그러면:

return advance_with_tag(i, n, typename iterator_traits<InputIterator>::iterator_category());

는

return advance_with_tag(i, n, category(InputIterator));

로 말끔한 코드가 된다.

참고 #

• cppreference: Iterator categories
• cppreference: iterator_traits
• cppreference: std::advance
• cppreference: std::distance
• cppreference: Ranges (C++20) — iterator_category 기반 tag dispatch를 concept으로 대체

이번 호에서는 algorithm-iterator-container에 관한 실험적 논의를 마무리 지었다. 또한 실제 표준 라이브러리에서 iterator 개념과 인터페이스를 구현하는 기법 중, 고급 프로그래밍에 유용하게 활용할 수 있는 기법 만을 인용하여 약간 깊게 논의하였다. 다음 호에서는 Container를 집중적으로 살펴보고 이와 연관해서 Inserter/reverse iterator 등의 특수한 generic iterator class의 기능을 소개할 계획이다. 그러나 algorithm은 별도로 다룰 계획이 없다. 정말 algorithm은 C++ 프로그래밍 기법에 관련된 것이라기 보다 사용설명서를 가지고 필요할 때마다 찾아서 써야할 도구의 집합이기 때문에 필자의 생각으론 이 연재기사의 논의를 벋어난 주제라고 판단하였기 때문이다. 그 보다는 만일 시간 또는 지면이 허락한다면 “새로운 C++ 프로그래밍 언어의 기능"을 연재하면서 바뜨렸거나 미처 간추리진 못한 특징을 마무리 지었으면 하는 것이 필자의 바램이다.