iterator pattern

iterator pattern

정의 : 객체 지향 프로그래밍에서 반복자를 사용하여 컨테이너를 가로지르며 컨테이너의 요소들에 접근하는 디자인 패턴이다. 반복자 패턴은 컨테이너로부터 알고리즘을 분리시키며, 일부의 경우 알고리즘들은 필수적으로 컨테이너에 특화되어 있기 때문에 분리가 불가능하다.

 

-> 서로 다른 자료구조들을 같은 방법으로 순회하고 싶다.

 

 

#include <iostream>

int main()
{
	std::List<int>  s = { 1,2,3,4,5 }; // 모든 요소가 떨어진 메모리
	std::vector<int> v = { 1,2,3,4,5 }; // 모든 요소가 연속된 메모리
}

 

list는 보통 double linked list를 사용하여 구현되어있다 한다. 즉 요소 요소가 떨어져 있다.

[  ←o→   ←o→    ←o→    ←o→    ]

 

vector는 각 요소들이 연속적인 공간에 배치되어 있다.

[oooo]

 

사실 위 두 개가 메모리 상에서 어떤 방식으로 구현되어 있건간에.. 같은 방법으로 내부 요소들을 순회할 수 있으면 좋을 것이다.

만약 하나의 구조체마다 다른 순회 방법이 있으면 상당히 많이 복잡할테니...

 

다행히도, 내부 구조가 어떻게 되어있든간에 우리는 하나의 방법으로 안의 요소들을 순회할 수 있다.

 

for (const auto& elm : list){
	std::cout << elm << std::endl;
}

 

이런 느낌으로... cpp에서는 이미 iterator를 통해 간단하게 다른 구조의 요소들을 순회할 수 있다.

 

 

만약 우리가 새로운 방식의 구조체를 만들고, 그 구조체들 또한 같은 방법으로 순회하고 싶으면 어떻게 해야 할까?

 

MyArray s;
MyArray2 v;

auto p1 = s.makeIterator(); // MyArray의 iterator
auto p2 = v.makeIterator(); // MyArray2의 iterator

int n1 = p1.getObject(); // 요소 얻기
int n2 = p2.getObject();

p1.moveNext(); // 다음으로 이동
p2.moveNext();

이런 식으로 다른 구조체이지만, 한 가지의 방법으로 데이터를 꺼내 보며 순회할 수 있다면 편할 것이다.

 

 

 

 

바로 위 코드가 되게 구현을 해 보자.

먼저 다음으로 옮겨갈 수 있고, 현재 object를 만들 수 있는 iterator interface를 만든다.

그리고 모든 컨테이너들은 같은 방식으로 요소들을 순회하고, 데이터를 꺼낼 수 있게끔 iterable interface를 상속받게 한다.

 

template<typename T>
struct iterator
{
	virtual T& getObject() = 0;
	virtual bool moveNext() = 0;
	virtual ~iterator() {}
};

template<typename T>
struct iterable
{
	virtual iterator<T>* makeIterator() = 0;
	virtual ~iterable() {}
};

이 노드들을 기반으로 linked list container를 만들면

 

 

template<typename T>
struct Node
{
	T     data;
	Node* next;

	Node(const T& d, Node* n) : data(d), next(n) {}
};

 

 

위처럼 된다.

 

 

 

 

위 두 개를 가지고 single linked list를 만들어 보자.

그렇다면 먼저 single linked list 자체와,  single linkedlist의 iterator. 두 개가 필요할 것이다.

 

 

// single linked list에서 돌아가는 iterator를 제작한다.
template<typename T> 
class slist_iterator : public iterator<T>
{
	Node<T>* current;
public:
	slist_iterator(Node<T>* p = nullptr) : current(p) {}

	T& getObject() override
	{
		return current->data;
	}
	bool moveNext() override
	{
		current = current->next;
		return current;
	}
};


// iterable 을 상속받는다.
template<typename T> 
struct slist : public iterable<T>
{
	Node<T>* head = nullptr;
public:
	void push_front(const T& a) {head = new Node<T>(a, head);}

	iterator<T>* makeIterator() override
	{
		return new slist_iterator<T>(head);
	}
};

 

 

 

이렇게 하면, 사용자는 구조체의 내부가 어떻게 되어있는지 신경쓰지 않고 구조체를 순회할 수 있게 된다.

 

 

 

int main()
{
	slist<int> s;
	s.push_front(10);
	s.push_front(20);
	s.push_front(30);
	s.push_front(40);

	iterator<int>* p = s.makeIterator();
	do
	{
		std::cout << p->getObject() << std::endl;

	} while (p->moveNext());

	delete p;
}

 

 

 

다만.. 열심히 만들었지만 cpp 맨 처음에 예를 들었던 std::list / std::vector에서는 이러한 방식의 iterator를 사용하지 않고 다른 방식의 iterator를 사용한다고 한다.

 

몇 가지 이유가 있는데.

 

1. 반복자가 동적 메모리 할당으로 생성된다..사용후 반드시 delete 해야한다.

   => 스마트 포인터 사용하면 되긴 함.

2. 반복자의 getObject(), moveNext() 는 가상함수 이다.

   => 가상함수 테이블의 새로 만들어진다. 성능 이슈.

3. raw array 의 순회 방법과 다르다. ( raw array 는 ++연산자 사용)

 

 

 

결국, cpp에서는 연산자 오버로딩을 사용하여 같은 방식으로 순회할 수 있게 한다고 한다.

 

 

밑. 참고 코드.

 

 

 

#include <iostream>

template<typename T>
struct Node {
    T data;
    Node* next;

    Node(const T& d, Node* n) : data(d), next(n){}
}

template<typename T>
class slist_iterator {
    Node<T>* current;
public:
    slist_iterator(Node<T>* d = nullptr) : current(d){}

    inline T& operator*(){
        return current->data;
    }

    inline slist_iterator<T>& operator++(){
        current = current->next;
        return *this;
    }

    inline bool operator==(const slist_iterator& other) const{
        return current == other.current;
    }
    inline bool operator!=(const slist_iterator& other) const{
        return !(current == other.current);
    }
}


template <typename T>
struct slist{
    Node<T>* head {nullptr};
public:
    void push_front(const T& a){
        head = new Node<T>(a, head);
    }

    using iterator = slist_iterator<T>;

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


int main()
{
	slist<int> s;
	s.push_front(10);
	s.push_front(20);
	s.push_front(30);
	s.push_front(40);

	slist<int>::iterator p = s.begin();
	
	while (p != s.end())
	{
		std::cout << *p << std::endl;
		++p;
	}
}

 

 

 

 

* 잘못된 정보는 알려주시면 감사하겠습니다.