[STL] Iterator개념과 advance, distance 함수

이번글은 간단한 Iterator의 종류와 구분방식을 살펴보고 정리한 뒤 advance, distance를 직접 구현한 글입니다 :)

(STL 기본 컨테이너의 동작방식이나 개념은 없습니당)

---

STL의 vector, deque, list는 sequence container로 원소의 위치가 정해진 상태로 삽입됩니다.

STL의 set, multiset, map, multimap의 경우 associate containder로 원소의 삽입 위치가 특정 조건에 따라 달라집니다.(default는 less<int>() 입니다)

 

또한 시퀀스 컨테이너는 선형적이며,

연관 컨테이너는 비선형적 이라고 구분할 수 있습니다.

그중에서도 STL의 vetor, deque가 배열기반의 컨테이너이며(데이터 여러개가 하나의 메모리 단위에 저장)

list, set, multiset, map, multimap의 경우 노드 기반 컨테이너 입니다.(데이터 하나를 하나의 메모리 단위에 저장)

 

iterator는 STL 컨테이너에 저장된 원소(순차열)를 순회하고 접근하는 일반화된 방법을 제공합니다.

이 반복자 덕분에 알고리즘은 특정 컨테이너에 종속적이지 않고 독립적이면서도 언제든지 컨테이너들과 결합할 수 있다는 장점이 있습니다.

 

이러한 반복자의 종류로는 

• input iterator : 전방향 읽기 istream
• ouput iterator : 전방향 쓰기 ostream
• 순방향 반복자 (forward iterator) : 전방향 읽기, 쓰기
• 양방향 반복자 (bidiretional iterator) : 양방향 읽기, 쓰기 (list, set, multiset, map, multimap)
• 임의 접근 반복자 (random access iterator) : 양방향 읽기, 쓰기 (vector, deque)

가 있습니다.

 

STL의 모든 컨테이는 기본적으로 "양방향 반복자" 이상을 제공합니다.

 

순방향 반복자는 *iter, ->, ++, ==, !=, =(대입), iterator()(기본 생성자), iterator(iter)연산을 제공합니다.

양방향 반복자는 순방향 반복자 기능에 --(역방향 이동) 연산을 제공합니다.

임의 접근 반복자는 양방향 반복자 기능에 반복자의 랜덤 연산인 [], +=, -=, +, -, >, <, <=, >= 연산을 제공합니다.

---

양방향 반복자에 임의 접근 반복자 기능을 사용할 수 없다는 것은 잠시 생각해보면 타당합니다.

노드기반 컨테이너에 어떻게 [], +=, ++ 와같은 연산을 적용할 수 있을 까요?

노드를  동적으로 생성하여 연결한 연관컨테이너에 += 3; 을 수행할 경우 어느 메모리 위치를 가르킬 줄 모르니까 당연히 random access 접근은 안되는게 맞는거 같습니다.

 

하지만 양방향 반복자를 제공하는 assoiciate container에 임의 접근 반복자만이 가지고 있는 연산 (+, -, +=, -=) 을 가능하게 해주는 함수가 있는데요

바로 "advance()", "distacne()" 함수입니다.

 

반복자는 효율적인 사용을 위해 5가지로 반복자를 분류하고(입력, 출력, 순방향, 양방향, 임의 접근)

이때 각 반복자는 자신만의 특징을 가지는데 이 특징을 저장하는 템플릿 클래스를 가르켜 "반복자 특성(iterator traits)"라고 합니다.

또한 STL은 반복자의 종류를 구분할 수 있도록 5개의 반복자 태그를 제공합니다.

 

iterator traits는 iterator_category, value_type, difference_type, pointer, referece를 하나의 템플릿 클래스로 제공하는 반복자의 공통된 Interface입니다.

 

distacne(b, e)의 경우 반환형식은 unsigned int 또는 int이지만 반복자 마다 다릅니다. 

이를 정확히 표현하면 반복자 특성(iterator traits)의 difference_type 형식입니다.

 

따라서

int main()
{
	using namespace std;

	list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);

	int dis = l.end() - l.begin(); cout << dis << endl; // Error
	iterator_traits<vector<int>::iterator>::difference_type n = distance(l.begin(), l.end());
	cout << n << endl;
	
	return 0;
}

연관 컨테이너인 list에 '-'연산을 적용하여 그 길이를 구할 수 없지만

distance함수를 통해 iterator traits의 difference_type형식으로 거리를 구해서 받을 수 있습니다.

 

advance의 경우에도 l.begin() + 3; 와 같은 연산을 수행할 수 없지만

list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);

auto liter = l.begin();
advance(liter, 3);

위와같은 begin() += 3 과같은 연산이 가능합니다.

 

위의 advance 함수를 직접 구현해보도록 하겠습니다.

 

시퀀스 컨테이너와 연관컨테이너일 경우에 따라 advance를 직접 정의한 _Advance함수를 인자에 따라 오버라이딩 하고 

반복자의 특성인 iterator_traits를 직접 정의하고

반복자의 종류를 구분할 수 있는 반복자 태그를 정의하여 구현 할 수 있도록 합니다.

 

#include <iostream>
using namespace std;

// iterator traits 직접 정의
namespace MY
{
	template <class Iter>
	struct iterator_traits
	{
		typedef typename Iter::iterator_category iterator_category;
		typedef typename Iter::value_type value_type;
		typedef typename Iter::difference_type difference_type;
		typedef typename Iter::pointer pointer;
		typedef typename Iter::reference reference;
	};

	// 반복자의 종류를 구분하기위한 STL 반복자 태그
	struct input_iterator_tag {};
	struct output_iterator_tag {};
	struct forward_iterator_tag : public ::input_iterator_tag {};
	struct bidirectional_iterator_tag : public ::forward_iterator_tag {};
	struct random_access_iterator_tag : public ::bidirectional_iterator_tag {};
};

template <typename T>
class _Vector
{
public:
	class Iterator
	{
	public:
		typedef MY::random_access_iterator_tag iterator_category;
		typedef T value_type;
		typedef int diffence_type;
		typedef T* pointer;
		typedef T& refernce;

		void operator += (int) {}
	};
	void Push_Back(const T& data) {};
	Iterator Begin() { return Iterator(); }
};

template <typename T>
class List
{
public:
	class Iterator
	{
	public:
		typedef MY::bidirectional_iterator_tag iterator_category;
		typedef T value_type;
		typedef int difference_type;
		typedef T* pointer;
		typedef T& reference;

		void operator++ () {}
	};
	void Push_Back(const T& data) {};
	Iterator Begin() { return Iterator(); }
};

// overwrite
// ================================
template <typename Iter>
void _Advance(Iter& iter, int n, MY::bidirectional_iterator_tag category_tage)
{
	for (int i = 0; i < n; ++i)
	{
		++iter;
	}
	std::cout << "양방향 반복자 버전의 advance() ++iter 실행" << std::endl;
}

template <typename Iter>
void _Advance(Iter& iter, int n, MY::random_access_iterator_tag category_tag)
{
	iter += n;
	cout << "임의 접근 반복자 버전의 advance() iter += n 실행" << endl;
};
// ================================

template <typename Iter>
void Advance(Iter& iter, int n)
{
	_Advance(iter, n, MY::iterator_traits<Iter>::iterator_category());
}

int main()
{	
	_Vector<int> v;
	v.Push_Back(10);
	v.Push_Back(20);
	v.Push_Back(30);

	List<int> lt;
	lt.Push_Back(10);
	lt.Push_Back(20);
	lt.Push_Back(30);

	_Vector<int>::Iterator viter(v.Begin());
	List<int>::Iterator liter(lt.Begin());

	Advance(viter, 2);
	Advance(liter, 2);
	
	return 0;
}