의도
- 내부 표현부를 노출하지 않고 어떤 집합 객체에 속한 원소들을 순차적으로 접근할 수 있는 방법을 제공
다른 이름
언제 쓰는가 ?
- 객체 내부 표현 방식을 모르고도 집합 객체의 각 원소들에 접근하고 싶을 때
- 집합 객체를 순회하는 다양한 방법을 지원하고 싶을 때
- 서로 다른 집합 객체 구조에 대해서도 동일한 방법으로 순회하고 싶을 때
구조
GoF의 디자인 패턴 중 P.343
- Iterator : 원소를 접근하고 순회하는 데 필요한 인터페이스를 제공
- ConcreteIterator : Iterator에 정의된 인터페이스를 구현하는 클래스로, 순회 과정 중 집합 객체 내에서 현재 위치를 기억
- Aggregate : Iterator 객체를 생성하는 인터페이스를 정의
- ConcreteAggregate : 해당하는 ConcreteIterator의 인스턴스를 반환하는 Iterator 생성 인터페이스를 구현
협력 방법
- ConcreteIterator는 집합 객체 내 현재 객체를 계속 추적하고 다음번 방문할 객체를 결정
결과
- 집합 객체의 다양한 순회 방법을 제공
- Iterator는 Aggregate 클래스의 인터페이스를 단순화
- 집합 객체에 따라 하나 이상의 순회 방법이 제공될 수 있음
구현 / 고려 사항
- 누가 반복을 제어 ?
- 외부 반복자 vs 내부 반복자
- 어떤 부분에서 반복을 제어할 것인지 결정하는 것이 중요한 안건
- 순회 알고리즘을 어디에 정의?
- Iterator 클래스에만 순회 알고리즘을 정의하지는 않음
- Iterator에 순회 상태만 저장하는 것을 커서(cursor)라고 함
- 어떻게 반복자를 견고하게 만들 수 있을까?
- 집합 객체를 순회하는 동안 집합 객체를 수정하는 것은 위험한 일
- 견고한 반복자는 순회 중에 삽입이나 삭제가 일어나지 말아야 하며, 이를 해결하는 방법은 복사를 하는 것 (대신 비용이 많이 듬)
- 추가적으로 필요한 반복자 연산
- 최소한 초기 위치(First), 다음 원소 이동(Next), 완료 인지(IsDone), 현재 원소 반환(CurrentItem)의 연산은 지원해야 함
- C++에서 다형성을 지닌 반복자를 이용하는 방법
- 다형적인 반복자는 런타임에 팩토리 메서드로 동적으로 반복자 객체를 제공해야 하기 때문에 추가 비용을 지불해야 함. 다형성은 필요할 때만 사용. 확장된 반복자를 사용하는 것이 더 나은 일
- 다형적인 반복자의 경우 삭제 시 오류가 발생할 수 있음 ( 힙 메모리를 사용하기 때문 ). -> 프록시 패턴 사용(스마트 포인터 같은)
- 반복자에는 특수한 접근 권한이 있음
- friend 선언으로 자유롭게 접근 가능 -> 편하고 좋으나 새로운 순회 방법 정의 어려워짐
- Iterator 내 protected 지정자를 활용하면 iterator의 서브클래스들은 접근할 수 있으나 외부에는 노출하기 꺼려지는 원소 접근 메서드들을 관리할 수 있음
- 복합체를 위한 반복자
- 외부 반복자의 경우 재귀적인 처리가 어려움 (트리의 전위, 후위, 중위 순회 같은 ?) -> 복합체 패턴을 이용해서 자신이 거쳐온 단계를 저장해둬야 함
- 널 반복자
- IsDone 혹은 STL의 end() 반복자 같은 끝났음을 알리는 반복자가 필요함
예제 코드
- 간단하게 Inventory라는 클래스에 대해 STL 사용처럼 Begin과 End로 이터레이터를 제공하여 원소를 순회해봤습니다.
- End 이터레이터를 제공하는 방법에 있어서 원소 순회 중 원소가 추가되거나 삭제될 때 문제가 생기는 건 만들고나서 깨달았습니다. 참고하고 보시면 되겠습니다.
#include "Iterator1.h"
#include <iostream>
int main()
{
Inventory<int> inventory;
for (int i = 0; i < 10; i++)
{
inventory.Add(i);
}
for (auto iter = inventory.Begin(); iter != inventory.End(); iter.Next())
{
std::cout << iter.CurrentItem() << std::endl;
}
return 0;
}
- item 클래스를 따로 만들기는 귀찮아서 int 0 ~ 9 까지 담은 인벤토리를 이터레이터를 통해 순회한 결과입니다.
//Iterator1.h
#pragma once
#include <vector>
template<typename T>
class Inventory;
template<typename T>
class InventoryIterator;
template<typename Item>
class Inventory
{
public:
using Iterator = InventoryIterator<Item>;
friend class Iterator;
public:
Iterator Begin();
Iterator End();
void Add(Item item);
void Remove(Item item);
private:
std::vector<Item> items;
};
template<typename Item>
class IIterator
{
public:
virtual void First() = 0;
virtual void Next() = 0;
virtual bool IsDone() = 0;
virtual Item CurrentItem() = 0;
};
template<typename Item>
class InventoryIterator : public IIterator<Item>
{
public:
InventoryIterator(Inventory<Item>* inventory, bool bBegin = true)
: inventory(inventory)
{
if (bBegin)
{
First();
}
else
{
current_index = inventory->items.size();
}
}
virtual void First();
virtual void Next();
virtual bool IsDone();
virtual Item CurrentItem();
bool operator !=(const InventoryIterator<Item> rhs) const
{
return current_index != rhs.current_index;
}
private:
Inventory<Item>* inventory;
size_t current_index;
};
template<typename Item>
inline void InventoryIterator<Item>::First()
{
current_index = 0;
}
template<typename Item>
inline void InventoryIterator<Item>::Next()
{
current_index++;
}
template<typename Item>
inline bool InventoryIterator<Item>::IsDone()
{
return inventory->items.size() <= current_index;
}
template<typename Item>
inline Item InventoryIterator<Item>::CurrentItem()
{
return inventory->items[current_index];
}
template<typename Item>
inline typename Inventory<Item>::Iterator Inventory<Item>::Begin()
{
return InventoryIterator<Item>(this, true);
}
template<typename Item>
inline typename Inventory<Item>::Iterator Inventory<Item>::End()
{
return InventoryIterator<Item>(this, false);
}
template<typename Item>
inline void Inventory<Item>::Add(Item item)
{
items.push_back(item);
}
template<typename Item>
inline void Inventory<Item>::Remove(Item item)
{
items.erase(item);
}
- 일단 일벤토리에서 item을 관리하는 컨테이너는 그냥 vector 사용했습니다. Add, Remove시 vector의 push_back, erase 메서드 이용했습니다.
- Inventory 클래스의 Begin, End에서 InventoryIterator 클래스를 반환하게 되고
- 이 InventoryIterator는 index를 관리하게 되며 이 index는 Inventory 클래스의 items(vector)의 인덱스로 사용할 수 있습니다.
- 또한 표준 STL 사용과 비슷하게 처리하기 위해 != 연산에 대해서도 오버로딩을 해주었습니다.
- 위에서 이터레이터 순회 중에 Add나 Remove 시 문제가 생길 수 있다고 언급했는데 그 이유는 End() 가 반환하는 Iterator의 경우 만들어지는 시점의 Items 배열의 크기를 기준으로 생성하기 때문입니다.