3일차 - 반복자 (iterator)

Intro

  간단한 싱글 리스트의 구현을 생각해보자.

template <typename T> struct Node 
{
public:
	Node(T a, Node* n) : data(a), next(n) {}

private:
	T data;
	Node* next;
};

template <typename T> class slist 
{
public:
	slist() : head(nullptr) {}
  
	// Node의 생성자를 활용해서 list의 맨 앞에 새로운 Node를 추가
	void push_front (const T& a) { head = new Node<T>(a, head); }

private:
	Node<T>* head;
};

  별로 특별한 것은 없다. 아래와 같이 값을 삽입하는 것만 가능한 단순한 리스트이다.

slist<int> s;

s.push_front(10);
s.push_front(20);
s.push_front(30);

 

반복자 (iterator)

  이제는 이 리스트를 순회하면서 원소값도 확인해보고 싶고, 이전 글에서 작성했던 xfind 함수도 적용해 보고 싶은 생각이 든다. 이러한 일들이 가능하기 위해서는 리스트(컨테이너) 내에 노드를 가리킬 수 있는 포인터와 유사하면서, xfind에서 필요로 했던 추가 연산들을 지원하는 뭔가가 필요하다. 이런 존재를 반복자라고 부르며, STL 내에 있는 컨테이너들은 각자의 반복자를 정의하고 있다. 여기서는 slist를 위한 반복자를 정의해보자.

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

	// xfind 함수에서 필요로 하는 연산자들
	inline slist_iterator& operator++() {
		current = current->next;
		return *this;
	}

	inline T& operator*() { return current->data; }  //< 임시객체 생성방지
  
	inline bool operator==(const slist_iterator& it) { 
    		return current == it.current; 
	}
	inline bool operator!=(const slist_iterator& it) { 
    		return current != it.current; 
	}

private:
	Node<T>* current;  //< 현재 Node를 가리키는 포인터
};

 

 이제 인터페이스의 통일을 위해 slist 클래스 내에 아래의 코드를 추가하자.

typedef slist_iterator<T> iterator;
typedef T value_type;

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

  우선 모든 컨테이너 설계자는 해당 컨테이너의 반복자의 이름을 "iterator"라는 약속된 형태로 노출한다. 이는 이전에 컨테이너에 저장되는 요소의 타입을 value_type으로 노출하기로 했던것과 같은 맥락이다. 그리고 공통적으로 컨테이너의 시작과 마지막 '다음'을 가리키는 반복자를 begin과 end라는 함수로 제공한다.

  이제 slist는 아래와 같이 순회 및 예전에 작성했던 xfind를 통한 요소 검색이 가능해졌다.

slist<int> s;

s.push_front(10);
s.push_front(20);
s.push_front(30);

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

// xfind 함수 적용
slist<int>::iterator n = xfind(s.begin(), s.end(), 20);
if (n != s.end()) {
	cout << *n << endl;
}