[디자인패턴][행위패턴] 반복자 Iterator - C++

[모던 C++ 디자인 패턴] 책을 바탕으로 공부하는 내용을 정리한 내용이다.

---

Iterator Pattern

복잡한 데이터 구조를 다뤄야 할 때 데이터 순회(traversal) 문제에 부딪힌다. 여러 방법이 있지만 vector 형태의 데이터에서는 반복자(iterator)라고 불리는 방법이 흔히 사용된다.

반복자는 단순히 어떤 컬렉션의 항목 하나에 접근하는 방법과 그 항목의 다음 항목으로 이동하는 방법을 알고 있는 것이다. 따라서 ++ 연산자와 != 연산자만 구현하면 된다.

C++ 표준 라이브러리에서도 반복자를 광범위하게 사용하고 있다. 먼저 C++ 표준 라이브러리가 반복자를 어떻게 사용하고 있는지 알아볼 것이다. 그다음 직접 반복자를 만들고 반복자가 가진 제약들을 살펴본다.

---

표준 라이브러리 반복자

vector의 begin() 함수는 이름의 값이나 참조를 넘겨주지 않는다. 대신 반복자를 넘겨준다. begin()은 vector의 멤버 함수로도 존재하고 전역 함수로도 존재한다. 전역 함수는 저수준 배열(std::array가 아닌 C 스타일 배열)을 사용할 때 편하다.

begin()은 포인터를 리턴한다고 볼 수도 있다. vector의 반복자는 포인터처럼 동작하며, 역참조를 통해 이름의 값을 출력할 수 있다. 얻어진 반복자는 컬렉션을 순회하는 방법을 알고 있어, ++ 연산자가 포인터의 메모리 주소 값이 증가하는 것이 아닌 다음 항목으로의 이동을 의미한다. 또, 접근되는 항목의 값을 바꿀 수도 있다.

begin()의 반대편 짝은 end()인데, 마지막 항목을 가리키지 않는다. 마지막 항목 다음 위치를 가리킨다. 이를 이용해 종료 조건으로 활용할 수 있다.

rbegin(), rend()도 제공한다. 이 함수들은 컬렉션을 역방향으로 순회한다. rbegin()은 마지막 항목을, rend()는 첫 번째 항목의 바로 앞 위치를 가리킨다. rbegin()에서 rend()로 가는 경우에도 ++ 연산자를 사용한다.

---

이진트리의 탐색

전통적인 이진트리 탐색을 살펴보자. 트리의 노드는 다음과 같이 정의한다.

template <typename T> struct Node {
    T value;
    Node<T> *left = nullptr;
    Node<T> *right = nullptr;
    Node<T> *parent = nullptr;
    BinaryTree<T> *tree = nullptr;
};

노드는 그 자체에 대한 정의로 생성될 수도 있고, 자식들에 대한 정의를 통해 생성될 수도 있다.

explicit Node(const T &value) : value(value) {
}

Node(const T &value, Node<T> *const left, Node<T> *const right) : 
    value(value), left(left), right(right) {
    this->left->tree = this->right->tree = tree;
    this->left->parent = this->right->parent = this;
}

void set_tree(BinaryTree<T> *t) {
    tree = t;
    if ( left ) left->set_tree(t);
    if ( right ) right->set_tree(t);
}

위의 준비를 기반으로 트리 순회를 가능하게 하는 BinaryTree 데이터 구조를 만들 수 있다.

template<typename T> struct BinaryTree {
    explicit BinaryTree(Node<T> *const root) : root(root) {
        root->set_tree(this);
    }
    
    Node<T> *root = nullptr;
};

BinaryTree에 대한 반복자를 정의해 보자. 이진트리 탐색에는 크게 세 가지 방법이 있다. 전위(preorder) 탐색 방법을 구현해 보자.

• 항목(Leaft 노드)을 만나자마자 바로 리턴한다.
• 재귀적으로 왼쪽 서브트리를 순회한다.
• 재귀적으로 오른쪽 서브트리를 순회한다.

template <typename U>
struct PreOrderIterator {
    explicit PreOrderIterator(Node<U> *current) : current(current) {
    }
    
    bool operator!=(const PreOrderIterator<U> &other) {
        return current != other.current;
    }
    
    Node<U> &operator*() {
        return *current;
    }
    
    PreOrderIterator<U> &operator++() {
        if ( current->right ) {
            current = current->right;
            while ( current->left ) {
                current = current->left;
            }
        }
        else {
            Node<T> *p = current->parent;
            while ( p && current == p->right ) {
                current = p;
                p = p->parent;
            }
            current = p;
        }
        
        return *this;
    }
    
    Node<U> *current;
};

이제 마지막으로 BinaryTree에서 이 반복자를 어떻게 클라이언트에 노출하느냐이다. 만약 이 방식을 트리의 디폴트 탐색 방법으로 한다면 아래처럼 멤버 함수를 만들면 된다.

typedef PreOrderIterator<T> iterator;

iterator begin() {
    Node<T> *n = root;
    
    if ( n ) {
        while ( n->left ) {
            n = n->left;
        }
    }
    
    return iterator(n);
}

iterator end() {
    return iterator(nullptr);
}

아래와 같이 쓸 수 있다.

BinaryTree<string> family {
    new Node<string> {"me",
        new Node<string> {"mother",
            new Node<string> {"mother's mother"},
            new Node<string> {"mother's father"}
        },
        new Node<string> {"father"}
    }
};

for ( auto it = family.begin(); it != family.end(); ++it ) {
    cout << it->value << "\n";
}

순회 방법을 별도로 객체로 분리해서 제공할 수도 있다.

---

코루틴(Coroutine)을 이용한 순회

위에서 작성했던 operator++의 구현은 일반적으로 찾을 수 있는 트리 탐색 알고리즘의 의사 코드와 너무 다르다. 가독성이 크게 떨어진다. 이 코드가 동작할 수 있는 이유는 반복자의 시작 지점을 뿌리 노드의 최좌측 노드로 초기화했기 때문이다.

가독성에 문제가 생기는 이유는 operator++ 코드가 재시작을 지원하지 않기 때문이다. 호출 간의 스택을 보존할 수 없어 재귀호출이 불가능하다. 호출 중간 결과를 넘겨준 뒤 순회를 중단하고 중간 결과 작업이 끝난 뒤 순회를 재개할 수 있다면 어떨까? 재시작 가능한 함수라면 올바르게 재귀 호출을 할 수 있을까? 이러한 목적으로 코루틴이 만들어졌다. C++에서는 C++20에서 추가되었다.

코루틴 참조

코루틴을 이용하면 트리의 후위 탐색을 아래와 같이 구현할 수 있다.

generator<Node<T>*> post_order_impl(Node<T> *node) {
    if ( node ) {
        for ( auto x : post_order_impl(node->left) )
            co_yield x;
        for ( auto y : post_order_impl(node->right) )
            co_yield y;
        co_yield node;
    }
}

generator<Node<T>*> post_order() {
    return post_order_impl(root);
}

이제 코드에서 알고리즘이 쉽게 드러나고 잃어버렸던 가독성을 찾았다. begin() / end()도 더 이상 보이지 않는다. 단지 generator를 리턴할 뿐이다. generator는 co_yield로 전달되는 중간 결과를 넘겨주며 진행해 나가도록 설계되었다. 각 결과가 넘겨지고 함수의 진행이 임시 중단되면 클라이언트에서는 넘겨진 중간 결과로 필요한 작업을 수행한 후 순회 컨텍스트를 유지한 상태로 순회 작업을 재시작한다.

코루틴은 C++의 전통적 반복자가 가진 한계를 극복해 줄 것이다.

---

요약

C++에서 반복자 디자인 패턴을 명시적인 형태와 묵시적인 형태(범위 기반 for 루프 등)를 모두 지원한다. 반복자를 직접 구현하는 것은 간단하다. 포인터 연산의 단순한 퍼사드 인터페이스로 볼 수 있다.

코루틴은 반복자가 가진 문제를 해결할 수 있다. 반복자 호출 간에 상태를 보존할 수 있어 재귀 알고리즘 구현이 가능하다. 코루틴은 C# 등 다른 언어에서 오래전부터 지원하던 기능으로 C++에서는 C++20에 추가되었다.