반복자 (iterator)

hyenam·2022년 4월 14일

ft_containers

목록 보기

2/8

거의 cplusplus 페이지 파파고 버전입니다.

카테고리

반복자는 배열또는 컨테이너같은 어떤 요소 범위의 일부 요소를 가리키는 객체이다. 원래 포인터랑 다르지만 동작은 거의 동일하게 하는 객체라고 알고 있었는데 cplusplus 설명을 보니 The most obvious form of iterator is a pointer 라고 써있어서 그냥 포인터로 봐도 무방할 것 같다.

반복자는 구현하는 기능에 따라 카테고리가 5개로 나뉜다.

output
input
forward
bidirectional
random access

input과 output은 가장 기능이 제한되어 있는 타입이다.

forward는 input iterator의 모든 기능을 가진다.
const iterator가 아닌 경우 output의 기능도 가지고 있지만 정방향 한정이다. 또한 모든 표준 컨테이너는 최소한 forward iterator를 지원한다.

bidirectional는 forward와 비슷하지만 역방향으로도 가능하다.

random access iterator는 bidirectional iterator가 가지고 있는 기능들이 전부 구현되어 있다. 또한 비 순차적으로 요소에 접근이 가능하다. 그래서 random access iterator는 포인터와 유사한 기능을 가지고 있다. (포인터가 이 카테고리에 해당한다. pointers are iterators of this category)

모든 카테고리는 기본적으로

복사 생성자
복사 할당 연사자
소멸자
증가 연산자
를 가지고 있다.

또한 카테고리별로

카테고리 이름	비교 연산자	역참조	Lvalue참조	기본 생성자	Multi-pass	감소 연산자	산술 연산자	비교 연산자	복합 할당 연산자
input	O	O	X	X	X	X	X	X	X
output	X	X	O	X	X	X	X	X	X
forward	O	O	O	O	O	X	X	X	X
bidirectional	O	O	O	O	O	O	X	X	X
random access	O	O	O	O	O	O	O	O	O

이렇게 기능들을 가지고 있다.

참고로 반복자간의 산술 연산은 random-access-iterator일 경우 operator-로 연산을 하고 다른 경우는 operator++로 연산을 한다.
std::distance

Input iterator

struct input_iterator_tag {};

iterator 카테고리들은 전부 식별용으로 만들어졌기 때문에 빈 구조체 형태를 가지고 있다.

Input iterator는 순차적 입력 작업에서 사용할 수 있다. 각 요소는 반복자는 각 요소를 딱 한번 만 읽고 다음으로 넘어간다.

단일 입력 패스 알고리즘만 이 반복자를 필요로 한다.

Output iterator

struct output_iterator_tag {};

output iterator는 input과 반대로 출력만 지원이 된다.
각 요소들은 딱 한번만 기록이 된다.

Forward iterator

struct forward_iterator_tag {};

forward iterator는 처음부터 끝까지 요소가 순차적으로 이어져 있는 곳에 사용할 수 있는 반복자이다.

Bidirectional iterator

struct bidirectional_iterator_tag {};

Bidirectional iterator는 범위의 양방향에서 요소들을 접근할 수 있는 반복자이다.

Random-access iterator

struct random_access_iterator_tag {};

포인터와 동일한 기능을 제공하고, 임의의 요소에 접근을 할 수 있다.

구조

반복자는 클래스 템플릿이다.

std::iterator

반복자 클래스에는 기본 반복자 클래스가 존재하고, 다른 반복자 클래스들이 이 클래스를 상속받아 만들어진 형태이다.

이 기본 클래스는 일부 멤버 유형만 제공하며, 실제로 모든 반복자 유형에 존재할 필요는 없지만(?) (반복자 유형은 특정 멤버 요구 사항이 없음) default iterator_traits 클래스 템플릿이 적절한 인스턴스화를 자동으로 생성하는 데 필요한 멤버를 정의하기 때문에 유용할 수 있습니다. (이러한 인스턴스화는 모든 반복자 유형에 대해 유효해야 합니다.).

기본 반복자 클래스는

template <class Category,              // iterator::iterator_category
          class T,                     // iterator::value_type
          class Distance = ptrdiff_t,  // iterator::difference_type
          class Pointer = T*,          // iterator::pointer
          class Reference = T&         // iterator::reference
          > class iterator;

이런 매개변수들을 사용한다.

Category - 반복자가 속한 카테고리. (위에서 작성한 카테고리들을 의미함.)
T - 반복자가 가리키는 요소의 유형.
Distance - 두 반복자간의 차이.
Pointer - 반복자가 가리키는 요소에 대한 포인터.
Reference - 반복자가 가리키는 요소에 대한 참조를 나타내는 유형.

    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
    typedef Category  iterator_category;

코드내에서 저 매개변수들은 typedef로 이름을 바꾸어 사용한다.

반복자를 커스텀하기 위해서는

template <typename T>
class MyIterator : public std::iterator<std::iterator_tag_you_want, T>
{
	/*위 태크에 해당하는 연산자들을 전부 오버로딩*/
};

이런식으로 해서 사용할 수 있다.

아래는 이해를 돕기위한 cpluscplus의 std::iterator 예제이다.

// std::iterator example
#include <iostream>     // std::cout
#include <iterator>     // std::iterator, std::input_iterator_tag

class MyIterator : public std::iterator<std::input_iterator_tag, int>
{
  int* p;
public:
  MyIterator(int* x) :p(x) {}
  MyIterator(const MyIterator& mit) : p(mit.p) {}
  MyIterator& operator++() {++p;return *this;}
  MyIterator operator++(int) {MyIterator tmp(*this); operator++(); return tmp;}
  bool operator==(const MyIterator& rhs) const {return p==rhs.p;}
  bool operator!=(const MyIterator& rhs) const {return p!=rhs.p;}
  int& operator*() {return *p;}
};

int main () {
  int numbers[]={10,20,30,40,50};
  MyIterator from(numbers);
  MyIterator until(numbers+5);
  for (MyIterator it=from; it!=until; it++)
    std::cout << *it << ' ';
  std::cout << '\n';

  return 0;
}

std::iterator_traits

반복자의 속성을 정의하는 특성 클래스이다.

traits의 사전적 의미는 기능/속성을 의미한다.
iterator_traits는 iterator의 기능/속성을 의미한다.

표준 알고리즘은 해당 "iterator_trates" 인스턴스화의 멤버를 사용하여 전달된 반복자의 특정 속성과 이들이 나타내는 범위를 결정한다.

iterator_trates 클래스는 최소 아래와 같은 멤버들을 가지고 있는 타입의 템플릿 특수화를 정의 해야한다.(?)
For every iterator type, a corresponding specialization of iterator_traits class template shall be defined, with at least the following member types defined

difference_type
value_type
pointer
reference
iterator_category

std::iterator의 템플릿 매개변수들이다.

참고로 적어도 순방향 반복자가 아닌 출력 반복자의 경우, 이러한 멤버 유형 중 하나(iterator_category 제외)는 void로 정의될 수 있다.

iterator_traits 클래스 템플릿은 이러한 유형을 반복자 유형 자체에서 가져오는 기본 정의와 함께 제공됩니다(아래 참조). 또한 pointer (T)와 const point (const T)가 특수화 되어있다.

template <class Iterator> class iterator_traits;
template <class T> class iterator_traits<T*>;
template <class T> class iterator_traits<const T*>;

모든 사용자 지정 클래스는 기본 클래스 std::iterator를 공개적으로 상속하는 경우 iterator_traits의 유효한 인스턴스화를 가집니다.

멤버	일반적 정의	T* 특수화	const T* 특수화
difference_type	Iterator::difference_type	ptrdiff_t	ptrdiff_t
value_type	Iterator::value_type	T	T
pointer	Iterator::pointer	T*	const T*
reference	Iterator::reference	T&	const T&
iterator_category	Iterator::iterator_category	random_access_iterator_tag	random_access_iterator_tag

모든 반복자 유형에 대해 정보를 가져오는 일관된 방법이 필요하다. 그리고 iterator_tarits는 템플릿 특수화를 사용하여 위의 표와 같이 일관된 방식을 제공한다.

그리하여 이러한 정보들을 사용하여 알고리즘을 반복자 종류에 맞게 최적화 시킬 수 있다.

템플릿은 사용자 정의 반복자를 위해 특수화할 수 있으므로 반복자에 대한 정보는 유형이 일반적인 'typedefs'를 제공하지 않더라도 검색할 수 있다.

std::reverse_iterator

이 클래스는 bidirectional , random_access 반복자의 반대방향 반복자이다.

원래 반복자(std::reverse_iterator::base)의 복사본은 내부적으로 유지되며 reverse_iterator에서 수행되는 연산을 반영하기 위해 사용된다.
현재 상태의 베이스 반복자의 복사본은 멤버 베이스(std::reverse_iterator::base)를 호출하여 언제든지 얻을 수 있습니다.

reverse_iterator의 end()는 컨테이너 요소의 첫부분의 이전 부분을 가리키고, begin()은 맨 마지막 요소를 가리킨다. 증간연산자나, 산술 연산자 또한 반대방향을 가리키게된다.

template <class Iterator> class reverse_iterator;

템플릿 매개변수로 양뱡한 반복자 혹은 random_access 반복자가 쓰인다.

멤버 타입으로는

typedef typename Iterator iterator_type; // Iterator's type
typedef typename iterator_traits<Iterator>::iterator_category iterator_category; // Preserves Iterator's category
typedef typename iterator_traits<Iterator>::value_type value_type; // Preserves Iterator's value type
typedef typename iterator_traits<Iterator>::difference_type difference_type; // Preserves Iterator's difference type
typedef typename iterator_traits<Iterator>::pointer pointer; // Preserves Iterator's pointer type
typedef typename iterator_traits<Iterator>::reference reference; // 	Preserves Iterator's reference type

이런 것들을 가지고 있으며

연산자는

*
+
++
+=
-
--
-=
->
[]
이런것들을 사용할 수 있다.

또한 reverse_iterator는 base()라는 함수를 사용할 수 있는데,

iterator_type base() const;

템플릿 매개변수로 받은 반복자의 타입의 반복자(복사본)을 리턴해주는 함수이다.

만약 reverse_iterator에 컨테이너의 첫 원소를 가리키게 했으면, reverse_iterator는 컨테이너의 마지막 원소를 가리키고 있는 상태이다. 하지만 base()함수를 사용하면 다시 원래대로 첫번째 원소를 가리키는 것이라고 보면된다. 반전된걸 다시 반전시켜주는 그런 의미이다.?

revser_iterator는 구조가 정말 자세하게 문서가 작성되어 있다.
먼저 생성자는 총 3개가 있다.

default (1)          reverse_iterator();
initialization (2)	 explicit reverse_iterator (iterator_type it);
copy (3)	         template <class Iter>
  reverse_iterator (const reverse_iterator<Iter>& rev_it);

기본 생성자 - 개체를 가리키지 않는 역방향 반복자를 구성합니다.
내부 기본 반복자 값이 초기화됩니다.

초기화 생성자 - 원래 반복자로부터 역방향 반복기를 구성합니다. 생성된 객체의 동작은 원본을 복제하지만, 가리키는 요소를 역순으로 반복한다.

복사/ 타입 캐스트 생성자 - 다른 역방향 반복자로부터 역방향 반복자를 구성합니다. 생성된 개체는 rev_it과 동일한 반복자?를 유지합니다.

reverse_iterator에는 신기하게도 소멸자가 없다.

ft_container에서

사실 위에 써놓은 것 처럼 처음에는 iterator를 상속을 받아 input_iterator, random_access_iterator등등을 구현하는 방식으로 생각하고 그렇게 구현을 했었는데, 스터디원들과 모여서 얘기를 하다 보니까 원래 정석은 그게 맞지만 실제 코드내에는 또 다른 이터레이터가 구현이 되어있고 그걸 사용을 한다고 한다. (코드를 볼수는 없다고 한다.) 하지만 우리는 그 이터레이터를 구현을 못하기 때문에 그냥 vector면 vector이터레이터를 구현을 하고 map이면 map이터레이터를 구현하는 방식으로 가야한다고 한다고 한다.

hyenam

공부한 걸 정리하고 있습니다.

이전 포스트

서브젝트에 나온 모르는 개념들

다음 포스트