반복자 패턴(Iterator Pattern)

내부를 노출하지 않고 어떤 컬렉션에 속한 항목들을 순차적으로 접근할 수 있는 방법을 제공합니다.

컬렉션의 항목 하나에 접근하는 방법과 그 항목의 다음 항목으로 이동하는 방법을 알고 있는 것을 반복자라 합니다.

표준 라이브러리의 반복자

stl의 vector, map, list 등의 iterator는 이미 우리에게 익숙하며 잘 알것이라고 생각합니다.

이진 트리의 탐색

전통적인 컴퓨터 과정에서 다루는 이진 트리 탐색을 살펴봅시다.

Node는 left, right, parent 그리고 전체 tree에 대한 참조를 가집니다.

template <typename T> struct Node
{
 T value = T();
 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);
 }
 
 ~Node()
 {
  if (left) delete left;
  if (right) delete right;
 }
};

BinaryTree에 iterator의 필수 구현 요소인 != 연산자, ++연산자, 역참조 연산자, begin(), end()를 구현하였습니다.

template <typename T> struct BinaryTree
{
 Node<T>* root = nullptr;
 
 explicit BinaryTree(Node<T>* const root)
  : root{ root }
 {
  root->set_tree(this);
 }
 
 ~BinaryTree() { if (root) delete root; }
 
 template <typename U>
 struct PreOrderIterator
 {
  Node<U>* current;
 
  explicit PreOrderIterator(Node<U>* current)
   : current(current)
  {
  }
 
  bool operator!=(const PreOrderIterator<U>& other) // != 구현
  {
   return current != other.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>& operator*() { return *current; } // 역참조 구현
 };
 
 typedef PreOrderIterator<T> iterator;
 
 iterator end() // end() 구현
 {
  return iterator{ nullptr };
 }
 
 iterator begin() // begin() 구현
 {
  Node<T>* n = root;
 
  if (n)
   while (n->left)
    n = n->left;
  return iterator{ n };
 }
};

이제 아래처럼 반복자를 이용해 트리를 순회 할 수 있습니다.

//         me
//        /  \
//   mother   father
//      / \
//   m'm   m'f
 
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";
}
// 출력 결과
// mother's mother
// mother
// mother's father
// me
// father

코루틴을 이용한 순회

C++의 코루틴은 아쉽게도 아직 실험적으로 제공합니다.
다음의 코드는 코루틴으로 구현한 후위 탐색입니다.

experimental::generator<Node<T>*> post_order()
 {
  return post_order_impl(root);
 }
 
 experimental::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;
  }
 }
// 출력 결과
// mother's mother
// mother's father
// mother
// father
// me

코루틴을 이용하면 호출 중간에 중간 결과를 넘겨준 후 순회를 중단하고 중간 결과에 대한 작업이 끝난 후 순회를 재개할 수 있습니다.

 

 

[독서 리뷰] - 모던 C++ 디자인 패턴

모던 C++ 디자인 패턴

코드 참고 : https://cpp-design-patterns.readthedocs.io/en/latest/

Welcome to C++ Design Patterns’s documentation! — C++ Design Patterns 0.0.1 documentation