[디자인 패턴] 행동 패턴 (8) 반복자 Iterator

디자인 패턴/GoF

[디자인 패턴] 행동 패턴 (8) 반복자 Iterator

로파이 2021. 3. 24. 16:29

반복자 (Mediator) 패턴

1. 의도

자료구조에서 흔히 쓰이는 패턴으로 속한 원소에 대한 순차적 접근 방법을 제공하고 방법에 대한 표현을 외부에 노출하지 않는다.

2. 활용

리스트와 같이 원소에 대한 접근과 다음 원소로 이동하는 방법이 존재하는 자료구조에서 모든 원소를 순차적으로 접근하는 방법을 구현한다. 순차적 접근을 통해 반복자 함수 내부에서 삽입, 삭제 등의 연산을 포함시킬 수 있다. 이를 위해 반복자는 현재 몇 번째 원소를 가리키고 있는지, 자료구조의 끝에 도달했는 지를 판별한다.

- ListIterator와 List

반복자는 어떤 자료구조냐에 따라 순회 방법이 다르다. List와 같이 선형적 탐색 혹은 반대 방향으로 가능할 수도 있고 Tree같은 경우 전위, 중위, 후위 탐색 혹은 레벨 탐색 등 순회 방법이 다양하다.

List와 Tree 자료구조에 대해 모두 동작하는 Iterator를 만들고 싶다면 Iterator라는 추상 클래스를 정의하여 기본 인터페이스만 정의하도록한다. ListIterator/TreeIterator 등의 각 자료구

조에 올바른 순회 방법을 제공하는 내용을 구현한다.

List와 SkipList라는 다양한 List를 지원하고 싶다면 이를 추상화하여 AbstractList라는 추상 클래스를 정의하고 실제 원소에 대한 삽입, 삭제, 탐색 등의 인터페이스를 정의하고 구체 클래스에서 해당 내용을 구현한다.

사용자는 런타임에 자료구조와 반복자를 선택하여 Iterator 추상 클래스의 인터페이스를 기반으로 반복자 기능을 사용할 수 있다.

3. 참여자

Iterator: 원소를 접근하고 순회하는 데 필요한 인터페이스를 제공한다.
ConcreteIterator: Iterator에 정의된 인터페이스를 구현하는 클래스로, 순회 과정 중 집합 객체 내에서 현재 위치를 기억한다.
Aggregate: Iterator 객체를 생성하는 인터페이스를 정의한다.
ConcreteAggregate: 해당하는 ConcreteIterator의 인스턴스를 반환하는 Iterator 생성 인터페이스를 구현한다.

4. 협력 방법

ConcreteIterator는 현재 객체를 추적하고 다음 방문할 객체를 결정한다.

5. 결과

1) 집합 객체의 다양한 순회 방법을 제공한다.

트리와 같이 순회 방법을 선택하여 실현할 수 있다.

2) Iterator는 Aggregate 클래스의 인터페이스를 단순화한다.

Iterator의 순회 인터페이스는 Aggregate 클래스에 정의한 순회 방식을 대신하기 때문에 Aggregate에 순회 방식을 생략할 수 있다.

3) 집합 객체에 따라 하나 이상의 순회 방법이 제공될 수 있다.

Iterator에 순회 상태가 기억되므로 순회를 두번 이상 반복할 수도 있다.

6. 구현

예제 코드

예제 코드를 통해 반복자 구현을 위한 고려 사항을 알아보도록 한다.

Employee.h

리스트 자료구조에서 관리할 데이터를 정의한다.

class Employee
{
private:
	char _name[32] = {};
	int _age;
public:
	Employee(const char* name, int age) : _age(age)
	{
		strcpy_s(_name, name);
	}
	void Print()
	{
		std::cout << "Name : " << _name << "\tage : " << _age << std::endl;
	}
};

AbstractList.h

다양한 리스트를 구현하기 위한 추상 클래스를 정의한다.

#include "Iterator.h"
// 다양한 리스트 객체를 만들기 위한 추상 리스트 클래스
template<class Item>
class AbstractList
{
public:
	// 알맞은 반복자를 생성하도록 팩토리 메서드를 정의
	virtual Iterator<Item>* CreateIterator() const = 0;
	// ...
};

구체 클래스에 맞는 반복자를 생성하도록 팩토리 메서드를 제공한다.

List.h

구체 List 클래스의 예시로 삽입, 삭제, 탐색 방법을 제공하며 스택과 똑같이 동작하는 인터페이스를 가지고 있다.

#include "AbstractList.h"
#include "Iterator.h"
#define DEFAULT_LIST_CAPACITY 100

// 템플릿 클래스의 전방 선언
template<typename Elem>
class ListIterator;

template<class Item>
class List : public AbstractList<Item>
{
public:
	// 초기 갯수 만큼의 원소를 가진 리스트를 초기화 합니다. 
	List(long size = DEFAULT_LIST_CAPACITY);
	// 복사 생성을 위한 기본 복사 생성자 입니다.
	List(List&);
	// 더 이상 상속하지 않는 제너릭한 List가 되기 위해 가상 소멸자로 선언하지 않습니다. 
	~List();
	// 대입 연산 정의입니다.
	List& operator=(const List&);

	// 리스트 객체 수를 반환합니다.
	long Count() const;
	// 주어진 인덱스의 원소를 반환합니다.
	Item& Get(long index) const;
	// 첫번째 객체를 반환합니다.
	Item& First() const;
	// 마지막 객체를 반환합니다.
	Item& Last() const;
	// 해당 객체를 포함하는지 판별합니다.
	bool Includes(const Item&) const;

	// 인자를 리스트에 추가하고 그것을 마지막 원소로 만듭니다.
	void Append(const Item&);
	// 인자를 리스트에 추가하고 그것을 첫 번째 원소롤 만듭니다.
	void Prepend(const Item&);

	// 주어진 원소를 리스트에서 제거합니다.
	void Remove(const Item&);
	// 마지막 원소를 제거합니다.
	void RemoveLast();
	// 첫번째 원소를 제거합니다.
	void RemoveFirst();
	// 모든 원소를 제거합니다.
	void RemoveAll();

	// 리스트는 기본적으로 스택 인터페이스를 기초로합니다.
	// 제일 위 원소를 반환합니다.
	Item& Top() const;
	// 스택 위에 원소를 삽입합니다. 
	void Push(const Item&);
	// 스택 위의 원소를 제거하고 반환합니다.
	Item& Pop();

	/* Abstract List 객체를 상속한 List 객체는 자신의 반복자를 반환해야합니다. */
	Iterator<Item>* CreateIterator() const override
	{
		return new ListIterator<Item>(this);
	}
};

1) 반복자에 필요한 연산을 구현

Iterator.h

순회를 위한 기본 인터페이스를 정의한다.

// Iterator 클래스는 순회 인터페이스를 정의하는 추상 클래스 입니다.
template<class Item>
class Iterator
{
public:
	// 반복자를 첫 번째 객체에 위치시킵니다.
	virtual void First() = 0;
	// 반복자를 그 다음 객체에 위치시킵니다.
	virtual void Next() = 0;
	// 그 다음에 있는 객체가 더는 없을 때 true를 반환합니다.
	virtual bool IsDone() const = 0;
	// 현재 위치에 있는 객체를 반환합니다.
	virtual Item CurrentItem() const = 0;
protected:
	Iterator();
};

ListIterator.h

List를 위한 반복자로 앞에서 부터 순차적 순회를 위한 First() / Next() / IsDone() / CurrentItem() 함수를 구현한다.

#pragma once
#include "IteratorOutOfBounds.h"
#include "Iterator.h"

// 템플릿 클래스 전방 선언
template<class Elem>
class List;

// 리스트 자료구조를 위한 구체 반복자 클래스입니다.
template<class Item>
class ListIterator : public Iterator<Item>
{
public:
	ListIterator(const List<Item>* aList);
	
	virtual void First();
	virtual void Next();
	virtual bool IsDone() const;
	virtual Item CurrentItem() const;

private:
	const List<Item>* _list; // 실제 리스트 객체
	long _current; // 현재 가리키고 있는 원소의 번지 수
};

/*
	ListIterator의 구현 예시
*/
template<class Item>
ListIterator<Item>::ListIterator(const List<Item>* aList)
	: _list(aList), _current(0)
{
}

// 첫번째 인덱스로 이동
template<class Item>
void ListIterator<Item>::First()
{
	_current = 0;
}

// 다음 인덱스로 이동
template<class Item>
void ListIterator<Item>::Next()
{
	++_current;
}

// 반복자가 끝을 가리키고 있는지 확인
template<class Item>
bool ListIterator<Item>::IsDone() const
{
	return _current >= _list->Count();
}

// 현재 인덱스의 원소를 반환합니다.
// 끝을 가리키고 있을 떄는 IteratorOutOfBounds 예외를 발생시킵니다.
template<class Item>
Item ListIterator<Item>::CurrentItem() const
{
	if (IsDone())
	{
		throw IteratorOutOfBounds();
	}
	return _list->Get(_current);
}

ReverseListIterator.h

리스트의 뒤부터 차례대로를 탐색하는 반복자를 구현한다.

#pragma once
#include "IteratorOutOfBounds.h"
#include "Iterator.h"
#include "List.h"

// 거꾸로 순회를 하는 리스트 반복자 입니다.
template<class Item>
class ReverseListIterator :
    public Iterator<Item>
{
public:
    ReverseListIterator(const List<Item>* aList);

	virtual void First();
	virtual void Next();
	virtual bool IsDone() const;
	virtual Item CurrentItem() const;

private:
	const List<Item>* _list; // 실제 리스트 객체
	long _current; // 현재 가리키고 있는 원소의 번지 수
};

/*
	ReverseListIterator의 구현 예시
*/
template<class Item>
ReverseListIterator<Item>::ReverseListIterator(const List<Item>* aList)
	: _list(aList), _current(0)
{
}

// 첫번째 인덱스로 이동
template<class Item>
void ReverseListIterator<Item>::First()
{
	_current = _list->Count();
}

// 다음 인덱스로 이동
template<class Item>
void ReverseListIterator<Item>::Next()
{
	--_current;
}

// 반복자가 끝을 가리키고 있는지 확인
template<class Item>
bool ReverseListIterator<Item>::IsDone() const
{
	return _current <= 0;
}

// 현재 인덱스의 원소를 반환합니다.
// 끝을 가리키고 있을 떄는 IteratorOutOfBounds 예외를 발생시킵니다.
template<class Item>
Item ReverseListIterator<Item>::CurrentItem() const
{
	if (IsDone())
	{
		throw IteratorOutOfBounds();
	}
	return _list->Get(_current);
}

2) 반복 제어에 대한 주체

사용자 코드 예시 1

PrintEmployee() 함수는 리스트 반복자를 받아 구현된 순회를 실행한다.

실제 순회 방식이 외부에서 구현되므로 외부 반복자라고 한다.

void PrintEmployee(Iterator<Employee*>& i)
{
	for (i.First(); !i.IsDone(); i.Next())
	{
		i.CurrentItem()->Print();
	}
}

int main()
{
	List<Employee*>* employees = new List<Employee*>();
	
	// ... 원소 삽입
	employees->Push(new Employee("Bob", 32));
	employees->Push(new Employee("Ander", 28));

	ListIterator<Employee*> forward(employees);
	ReverseListIterator<Employee*> backward(employees);

	PrintEmployee(forward);
	PrintEmployee(backward);
    
    return 0;
}

실제 순회 방식을 클래스에 구현하여 사용한다면 내부 반복자라고 한다.

ListTraverser.h

다음은 내부 반복자의 예시로 ListTraverser라는 클래스가 가지고 있는 반복자를 활용하여 Traverse()라는 순회 함수를 호출 할 때 각 원소에 대한 ProcessItem()을 처리한다.

#pragma once
#include "ListIterator.h"

template<class Item>
class ListTraverser
{
public:
	ListTraverser (List<Item>* aList);
	bool Traverse();
protected:
	// 더 이상 처리할 원소가 없다면 false를 반환합니다.
	virtual bool ProcessItem(const Item&) = 0;
private:
	ListIterator<Item> _iterator;
};

template<class Item>
inline ListTraverser<Item>::ListTraverser(List<Item>* aList)
	:
	_iterator(aList)
{
}

template<class Item>
inline bool ListTraverser<Item>::Traverse()
{
	bool result = false;
	for (_iterator.First(); !_iterator.IsDone(); _iterator.Next())
	{
		result = ProcessItem(_iterator.CurrentItem());

		if (result == false)
		{
			break;
		}
	}
	return result;
}

PrintNEmployees.h

다음 클래스는 ListTraverser를 상속하는 구체 클래스로 사원에 대한 정보를 출력하는 함수를 제공한다. 1번 사용자 코드 예시에서 외부에 노출된 함수가 클래스 멤버 함수로 구현된다.

#pragma once
#include "ListTraverser.h"
#include "Employee.h"

class PrintNEmployees : public ListTraverser<Employee*>
{
public:
	PrintNEmployees(List<Employee*>* aList, int n)
		:
		ListTraverser<Employee*>(aList),
		_total(n), _count(0)
	{
	}
protected:
	bool ProcessItem(Employee* const&);
private:
	int _total;
	int _count;
};

bool PrintNEmployees::ProcessItem(Employee* const& e)
{
	_count++;
	e->Print();
	return _count < _total;
}

사용자 코드 예시 2

사용자 코드에서 외부 반복자 vs 내부 반복자의 표현

/* Iterator의 서브 클래스로 Employee 정보를 출력하는 방법을 클래스가 제공 */
	PrintNEmployees pa(employees, 10);
	pa.Traverse();

	// 외부 반복자를 이용한 경우
	ListIterator<Employee*> i(employees);
	int count = 0;

	for (i.First(); !i.IsDone(); i.Next())
	{
		++count;
		i.CurrentItem()->Print();
		
		if (count >= 10)
		{
			break;
		}
	}

3) 반복자 삭제에 대한 책임

리스트 클래스에는 리스트 클래스에 맞는 반복자를 생성하여 반환하는 팩토리 메서드를 제공한다.

/* Abstract List 객체를 상속한 List 객체는 자신의 반복자를 반환해야합니다. */
Iterator<Item>* CreateIterator() const override
{
	return new ListIterator<Item>(this);
}

사용자 코드 예시 3

반복자를 동적 생성하였다면 반드시 사용 후 이 반복자를 삭제 해야한다.

Iterator<Employee*>* iterator = employees->CreateIterator();
PrintEmployee(*iterator);
delete iterator;

프록시 패턴으로 구현한 IteratorPtr 클래스

실제 Iterator에 대한 삭제 책임을 프록시 클래스가 대신하고 이 클래스에 대한 포인터 접근 방법을 제공한다.

내부에는 반복자 포인터를 관리하고 소멸자가 호출 될 때 반복자를 삭제하는 것으로 자동 삭제한다.

복사 생성과 대입 생성을 막아 자신이 관리하는 반복자가 복제된 다른 인스턴스에서 삭제되는 것을 방지한다.

#include "Iterator.h"

template<class Item>
class IteratorPtr
{
public:
	IteratorPtr(Iterator<Item>* iter) : _iter(iter) {}
	~IteratorPtr() { delete _iter; }
	IteratorPtr<Item>* operator->() { return _iter; }
	Iterator<Item>& operator*() { return *_iter; }
private:
	// _i 를 여러번 삭제 하는 것을 방지하기 위해 복사 생성, 대입을 막는다.
	/*
		IteratorPtr(const IteratorPtr&) = delete;
		IteratorPtr& operator=(const IteratorPtr&) = delete;
	*/
	// 혹은 구현 없음
	IteratorPtr(const IteratorPtr&) {};
	IteratorPtr& operator=(const IteratorPtr&) {};
private:
	Iterator<Item>* _iter;
};

사용자 코드 예시 4

IteratorPtr은 반복자 삭제 책임을 대신 해주게 된다.

/* 확실한 반복자 삭제 */
// IteratorPtr 이라는 프록시 객체를 이용
IteratorPtr<Employee*> iteratorPtr(employees->CreateIterator());
PrintEmployee(*iteratorPtr);

그 밖에도 반복자는,

순회 중 삽입이나 삭제 혹은 원소의 내용을 변경하지 않는 견고한 반복자를 구현해야 하며, 순회가 끝났는지 판별하기 위해 원소의 끝을 가리키기 위한 Null Iterator에 대한 정의를 해야한다. 위 코드 예시에서는 단순히 현재 인덱스가 전체 원소 갯수를 벗어났는 지로 판별하였지만 트리와 같이 노드를 방문하였을 때, 자식이 없는 노드인지 판별하기 위해 Null Iterator를 정의하여 사용하도록 한다.

'디자인 패턴 > GoF' 카테고리의 다른 글

[디자인 패턴] 행동 패턴 (10) 방문자 Visitor (0)	2021.04.07
[디자인 패턴] 행동 패턴 (9) 메멘토 Memento (0)	2021.03.29
[디자인 패턴] 행동 패턴 (7) 중재자 Mediator (0)	2021.03.23
[디자인 패턴] 행동 패턴 (6) 전략 Strategy (0)	2021.03.13
[디자인 패턴] 행동 패턴 (5) 감시자 Observer (0)	2021.02.04

현재글[디자인 패턴] 행동 패턴 (8) 반복자 Iterator

움직이는 월e