[ft_containers] 1. Iterator 이해하기

본격적으로 컨테이너들을 구현하기에 앞서,

컨테이너에 포함된 원소들에 접근하는 용도로 사용되는 이터레이터에 대해 정확히 이해하고 넘어가야할 필요가 있는 것 같으니 이터레이터에 대해 먼저 정리해보도록 하자.

 

1. Iterator(반복자)란?

지금까지 C로 프로그래밍을 할 때에는 여러 개의 데이터를 순차적으로 저장할 필요가 있을 때에는 가장 기본적인 자료구조인 배열을 주로 사용해왔다. 이 배열에 담긴 원소에 순차적으로 접근하기 위해서는 배열에 인덱스를 이용하거나(arr[i]), 포인터에 증감연산을 하는 방식(*arr + i)을 사용한다.

 

c++의 STL은 배열만이 아닌 vector, set, map 등등 여러구조의 container를 포함하고 있다. STL에서는 container의 종류와 상관 없이 범용적으로 컨테이너의 원소에 순차적으로 접근할 수 있는 표준화된 인터페이스 객체 iterator를 제공하고 있다.

 

즉, iterator란 container가 vector건 set이건 상관 없이, container에 담긴 타입이 int이건 str이건 상관 없이 모두 동일한 방식으로 container에 포함된 요소에 순차적 접근을 가능하게 해주는 객체인 것이다.

 

이러한 iterator는 마치 포인터처럼 동작한다. 증감연산을 통해 container의 다른 원소에 접근할 수 있으며, iterator간의 연산을 통해 특정한 범위를 구할 수도, 포인터 연산을 통해 특정 원소의 값을 직접 수정할 수도 있다.   

 

2. Iterator의 카테고리

STL에 구현되어 있는 iterator는 그 특성에 따라 다음과 같은 카테고리로 나뉘게 된다.

카테고리	연산자	비고
Input	++ * -> copy constructor = == !=	* 읽기 전용이며, forward로만 접근가능 (--로 역방향 이동 연산이 불가능) * 대입, 비교 및 복제가 가능
Output	++ * copy constructor =	* 쓰기 전용이며, forward로만 접근가능 *대입은 가능하지만, 비교는 불가능 *증가 연산의 경우, 후위연산과 전위연산 모두 가능
Forward	input의 연산자 + default constructor	읽기 및 forward 전용
Bidirectional	Forward + 감소연산 (--)	forward에서 지원하는 기능을 모두 사용가능하며 역방향 이동 가능
Random Access	양방향 + + - += -= < > <= >= []	포인터 연산에서 사용 가능한 모든 기능 사용 가능.

이러한 카테고리는 공식적으로 계층화 되어있지는 않지만, 계층적으로 작성되어있다는 것을 추론할 수 있다. 모든 Random Access Iterator는 Bidirectional Iterator가 제공하는 기능을 전부 제공하며, Bidirectional -> forward -> output... 이런 순서로 하위 이터레이터의 기능을 모두 포함하고 있다.

 

//실제 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 {};

 

3.  Iterator Traits

Iterator 객체를 사용하여 함수를 구현하는 경우 iterator에 대한 추가적인 정보가, 예를 들어 iterator의 카테고리, 혹은 iterator가 참조하는 원소의 타입 등이 필요할 수 있다. (특정한 타입에 대해서만 동작하는 함수를 만들고 싶거나, 하는 경우)

 

이러한 정보에 접근할 수 있도록 iterator는 iterator traits라는 클래스 템플릿을 제공하고 있다.

//실제 STL에 구현된 iterator

template<class Iterator>
struct iterator_traits
{
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
    typedef typename Iterator::iterator_category iterator_category;
};

template<class T>
struct iterator_traits<T*>
{
    typedef ptrdiff_t difference_type;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef random_access_iterator_tag iterator_category;
};

 

4. Iterator의 클래스템플릿

이러한 iterator 역시 클래스 템플릿으로 생성되는 객체로 다음과 같은 타입 앨리어스를 가지게 된다.

template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
  struct iterator {
    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
    typedef Category  iterator_category;
  };

T : iterator가 가르키는 원소의 타입

Distance: 두 이터레이터 사이의 거리

Pointer: 이터레이터가 가르키는 원소의 포인터

Reference: 이터레이터가 가르키는 원소의 참조자

Category: 이터레이터의 카테고리

 

//추후 필요한 내용이나 알게되는 내용 추가