[Design pattern] 3-4. 반복자 패턴 (Iterator pattern)

안녕하세요. 명월입니다.

이 글은 디자인 패턴의 반복자 패턴(Iterator pattern)에 대한 글입니다.

반복자 패턴은 우리가 디자인 패턴을 모르는 상태에서도 아주 자주 사용하는 패턴입니다. C#에서는 list를 foreach로 사용하는 구문이고 Java에서는 for(var x : list)의 형태로 자주 사용되는 패턴입니다.

일반적인 배열(Array)에서는 어차피 index로 배열을 참조하기 때문에 반복자 패턴이 의미가 없습니다만, 연결 리스트(LinkedList)에서는 이야기가 다릅니다.

get(100)을 취득하게 되면 index를 0부터 100까지 이동하게 되기 때문에 실제 for에서 사용하게 되면 엄청나게 느려지겠네요.

예를 들면 0번째는 리스트의 가장 앞쪽이니 문제가 없습니다만 for의 1로 가게 되면 0를 참조해서 1번을 취득합니다. 다시 2로 가게되면 0을 참조해서 1로 이동하고 2를 취득합니다. 다시 3이면 0을 참조해서 1로 이동하고 2로 이동하고 3을 취득합니다.

그래서 반복자 패턴을 이용해서 매번 참조 할 때마다 포인터를 이동하여 찾을 필요가 없고 현재의 위치를 저장해서 현재의 값을 리턴, 그리고 다음 포인터로 이동하는 형식의 패턴이 필요합니다.

실무에서는 이걸 구현할 필요는 없고 List 타입은 모두 반복자 패턴을 상속 받고 있기 때문에 foreach를 하게 되면 자동으로 반복자 패턴 (Iterator pattern)으로 전환이 되기 때문에 패턴의 내용만 인지하고 응용하는 데에 사용할 수 있어야 합니다.

출처 - https://en.wikipedia.org/wiki/Iterator_pattern

#pragma once
#include <stdio.h>
#include <iostream>
#include<vector>
using namespace std;

// 실행 함수
int main()
{
  // 백터 인스턴스 생성
  vector<int> node;
  // 백터에 값을 넣는다.
  for (int i = 0; i < 10; i++) {
    node.push_back(i);
  }
  // 반복자 패턴으로 포인터를 취득
  for (vector<int>::iterator ptr = node.begin(); ptr < node.end(); ptr++) {
    // 콘솔 출력
    cout << *ptr << endl;
  }
  return 0;
}

우리가 실제 프로그램에서 사용하는 반복자 패턴은 for를 이용해서 값의 포인터를 가져와서 일렬의 순서대로 출력을 하는 패턴입니다.

사실 제가 C/C++로 반복자 패턴을 구현해보려 했는데... 어렵네요... C/C++를 사용 안 한지도 오래되었고 막상 구현하려니 엄청 어렵네요.. 그래서 여기에서는 그냥 반복자 패턴을 사용하는 방법에 대해서만 소개하겠습니다.

혹시, 반복자 패턴을 구현하시는 분이 있으면 알려주세요...

import java.util.Iterator;
// iterator 패턴을 사용하기 위해서 Iterable 인터페이스를 상속
class LinkedList<T> implements Iterable<T> {
  // 연결 리스트 알고리즘을 위한 인스턴스 클래스
  private class Node {
    // 리스트에 담는 값
    T data;
    // 연결 리스트의 다음 인스턴스 포인터
    Node next;
  }
  // 연결 리스트의 앞쪽 인스턴스 포인터
  private Node first = null;
  // 연결 리스트의 뒤쪽 인스턴스 포인터
  private Node end = null;
  // 값 추가 함수
  public void add(T data) {
    // 인스턴스 생성
    Node ptr = new Node();
    // 데이터 설정
    ptr.data = data;
    // 리스트 안에 없을 경우
    if (first == null) {
      // 연결 리스트의 앞과 뒤에 설정
      first = ptr;
      end = ptr;
      return;
    }
    // 리스트가 있으면 가장 뒤에 연결
    end.next = ptr;
    // 뒤쪽 인스턴스 변경
    end = ptr;
  }
  // Iterator 패턴을 위한 클래스, Iterator 인터페이스 상속
  private class Itr implements Iterator<T> {
    // for에서 현재 출력될 인스턴스 포인터 변수
    Node point;
    // 다음 인스턴스가 있는 여부
    public boolean hasNext() {
      // 포인터가 없으면 false
      return point != null;
    }
    // 현재의 값을 리턴하고 포인터를 이동
    public T next() {
      // 리턴할 값을 취득
      T ret = point.data;
      // 포인터 이동
      point = point.next;
      // 값 리턴
      return ret;
    }
  }
  // Iterable 인터페이스의 재정의 함수
  @Override
  public Iterator<T> iterator() {
    // Iterator 패턴을 위한 클래스의 인스턴스 생성
    Itr itr = new Itr();
    // 가장 첫번째 인스턴스 설정
    itr.point = first;
    // Iterator 패턴 클래스의 인스턴스 리턴
    return itr;
  }
}
public class Program {
  // 실행 함수
  public static void main(String[] args) {
    // Iterable 인터페이스를 상속 받은 클래스의 인스턴스를 생성
    LinkedList<Integer> list = new LinkedList<>();
    // 값 데이터 입력
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    // iterator 함수를 호출하여 hasnext의 값으로 true, false를 확인하고 값을 출력한다.
    for (var data : list) {
      // 콘솔 출력
      System.out.println(data);
    }
  }
}

위 예제는 간단한 연결 리스트의 알고리즘입니다.

그리고 임의로 연결 리스트의 LinkedList 클래스를 for의 반복문에 반복자 패턴(Iterator pattern)으로 데이터가 순서대로 출력되는 것을 확인할 수 있습니다.

즉, for의 반복문에 반복자 패턴을 사용하려면 Iterable의 인터페이스를 상속 받으면 됩니다.

Iterable의 인터페이스에서는 iterator 함수를 재정의해야 하는 데 iterator 함수의 반환 값은 Iterator의 인터페이스 형식입니다.

그럼 다시 Iterator의 인터페이스를 상속 받은 Itr 클래스를 생성하고 Itr 클래스는 hasNext 함수와 next 함수를 재정의 해야 합니다.

즉, for에서의 반복자 패턴을 사용하게 되면 hasNext를 호출하여 값이 있는지 true, false의 값을 받아, true가 되면 next 함수를 호출하게 됩니다.

next함수에서는 값을 출력받지만, 다음 포인터의 위치로 움직여야 하는 처리를 해야 합니다.

그렇게 마지막에 hasNext에서 false가 나오게 되면 for문을 빠져나오게 됩니다.

using System;
using System.Collections;
using System.Collections.Generic;
// iterator 패턴을 사용하기 위해서 IEnumerable 인터페이스를 상속
public class LinkedList<T> : IEnumerable<T>
{
  // 연결 리스트 알고리즘을 위한 인스턴스 클래스
  class Node
  {
    // 리스트에 담는 값
    public T Data { get; set; }
    // 연결 리스트의 다음 인스턴스 포인터
    public Node Next { get; set; }
  }
  // 연결 리스트의 앞쪽 인스턴스 포인터
  private Node first = null;
  // 연결 리스트의 뒤쪽 인스턴스 포인터
  private Node end = null;
  // 값 추가 함수
  public void Add(T data)
  {
    // 인스턴스 생성
    Node node = new Node() { Data = data };
    // 리스트 안에 없을 경우
    if(first == null)
    {
      // 연결 리스트의 앞과 뒤에 설정
      first = node;
      end = node;
      return;
    }
    // 리스트가 있으면 가장 뒤에 연결
    end.Next = node;
    // 뒤쪽 인스턴스 변경
    end = node;
  }
  // Iterator 패턴을 위한 클래스, IEnumerator 인터페이스 상속
  class Enumerator : IEnumerator<T>
  {
    // Reset 함수를 위한 리스트의 앞쪽 변수
    private Node first;
    // 현재 위치 변수
    private Node current;
    // 생성자
    public Enumerator(Node first)
    {
      // 맴버 변수 설정
      this.first = first;
      this.current = first;
    }
    // 현재 위치 값 반환
    public T Current
    {
      get
      {
        // 리턴 값을 취득
        T ret = current.Data;
        // 포인터 이동
        current = current.Next;
        // 값 리턴
        return ret;
      }
    }
    // Current의 값과 동일
    object IEnumerator.Current => Current;
    // foreach가 끝났을 경우 호출
    public void Dispose()
    {
      // 만약 리소스를 사용할 경우, 즉 IO나 Socket이 사용된 경우에는 커넥션 종료를 한다.
    }
    // 다음 인스턴스가 있는 여부
    public bool MoveNext()
    {
      // 없으면 false, 있으면 true
      return current != null;
    }
    // Iterator 패턴 초기화
    public void Reset()
    {
      current = first;
    }
  }
  // Iterator 패턴 클래스의 인스턴스 리턴
  public IEnumerator<T> GetEnumerator()
  {
    // 인스턴스 생성
    return new Enumerator(first);
  }
  // GetEnumerator 함수와 동일
  IEnumerator IEnumerable.GetEnumerator()
  {
    return GetEnumerator();
  }
}

class Program
{
  // 실행 함수
  static void Main(string[] args)
  {
    // 연결 리스트 인스턴스 생성
    LinkedList<int> iter = new LinkedList<int>();
    // 값 추가
    iter.Add(1);
    iter.Add(2);
    iter.Add(3);
    iter.Add(4);
    iter.Add(5);
    // MoveNext()를 호출하고 true면 Current를 호출한다.
    // 결과는 1, 2, 3, 4, 5
    foreach (var data in iter)
    {
      // 콘솔 출력
      Console.WriteLine(data);
    }
    // 아무 키나 누르시면 종료합니다.
    Console.WriteLine("Press any key...");
    Console.ReadKey();
  }
}

내용은 Java의 예제와 동일합니다.

반복자 패턴(Iterator pattern)은 우리가 패턴을 알아도 몰라도 자주 사용하는 패턴입니다. 특히, 대용량의 값을 Queue와 LinkedList로 사용할 경우 자주 사용하게 되는 패턴 중에 하나입니다.

알고리즘 특성상 for(int i=0;i<size;i++)식으로 구현하게 되면 이중 탐색이 되어 버리기 때문에 성능 상에 많은 문제가 발생할 수 있겠네요.

그리고 사양에 따라서 프로그램 상에서 반복자 패턴(Iterator pattern)를 구현을 해야 할 경우가 있습니다.

그럴 경우에는 꼭 단순한 LinkedList의 FIFO식의 알고리즘이 아닌 캐쉬 알고리즘 LRU(Least Recently Used)나 LFU(Least Frequency Used)로 응용해서 사용하는 경우도 있습니다.

여기까지 디자인 패턴의 반복자 패턴(Iterator pattern)에 대한 글이었습니다.

궁금한 점이나 잘못된 점이 있으면 댓글 부탁드립니다.