iterator(반복자) 란?

STL 에서 iterator 는 무엇이고, 어떤 종류의 iterator 를 가지고 있는지 간단히 알아보자.


iterator (반복자)

STL 에서 반복자는 원소들의 범위를 다루는 표준 방법이다. 포인터와 비슷하게 동작하는 클래스 템플릿 타입의 객체로, 반복자 iter 가 객체를 가리킨다면 역참조(*iter)해서 객체에 대한 참조를 얻을 수 있다. 또한, iter 가 클래스 객체를 가리키고 있따면 객체의 멤버를 iter->member 형태로 접근 가능하다.

반복자는 컨테이너의 종류와 상관없이 STL 알고리즘들이 원소들을 사용할 수 있도록 해준다. 따라서, STL 알고리즘은 컨테이너 내부에 어떤 방식으로 데이터가 구성되어 있는지 몰라도 상관없다.

반복자는 원소들의 범위를 정의하는대, 범위의 첫 번째 원소는 begin, 마지막 원소를 가리키는 end 반복자로 표현할 수 있다. 주의할 점은 end 반복자는 마지막 원소가 아니라 마지막 원소에서 한 더 지나친 위치를 가리킨다는 것이다. 즉, end 반복자는 어떤 원소도 가리키지 않는 영역이므로 역참조 될 수 없다.


반복자 얻기

컨테이너의 반복자는 컨테이너 객체의 멤버 함수인 begin(), end() 또는 const 반복자를 반환하는 cbegin(), cend() 을 호출해서 얻을 수도 있고, 전역 함수 std::begin(), std::end() 또는 std::cbegin(), std::cend() 에 컨테이너를 인자로 넣어서 얻을 수도 있다. 아래의 이미지는 반복자가 동작하는 방식을 나타낸 것이다.

STL 에서 제공하는 컨테이너는 3가지로 구분할 수 있다.

  • 순차 컨테이너 – 객체들을 선형(linear) 로 저장한다. 선형이라는 것은 반드시 연속된 메모리로 저장될 필요가 없다는 뜻을 의미한다. 멤버 함수, 반복자 또는 상황에 따라서 첨자 연산자와 인덱스를 사용하여 컨테이너에 저장된 객체에 접근할 수 있다. (array, vector, deque, list, forward_list 가 대표적이다.)
  • 연과 컨테이너 – 객체들을 연관된 키와 함께 저장한다. 키를 이용해서 연관 컨테이너에서 객체를 가져올 수도 있고, 반복자를 사용해서도 연관 컨테이너에서 객체들을 가져 올 수 있다. (map, multimap, unordered_map, unordered_multimap 이 대표적이다.)
  • 컨테이너 어댑터 – 순차 컨테이너나 연관 컨테이너에 저장된 데이터에 접근하는 다른 방법을 제공한다. 컨테이너의 기존 인터페이스를 확장하기 때문에 이런 클래스 템플릿을 어댑터 클래스라고 부른다. (stack, queue, priority_queue 가 대표적이다.)


반복자의 5가지 카테고리

반복자는 5가지 카테고리로 나눌 수 있는데, 반복자 타입이 지원하는 카테고리는 iterator 템플릿의 타입 매개변수에 쓰인 인수 값으로 식별할 수 있다.

  • 읽기 반복자 – 읽기 반복자는 객체에 대한 읽기 권한을 갖는다. 읽기 반복자가 가리키는 값에 대한 참조를 얻는 *iter 를 반드시 지원해야 하며, 한 번 반복자를 증가시키면 이전 원소에 접근하려 할 때는 새 반복자를 사용해야 한다. 가능한 연산은 다음과 같다. ++iter, iter++, iter1 == iter2, iter1 != iter2, *iter
  • 출력 반복자 – 객체에 대한 쓰기 권한을 가진다. 출력 반복자라면 새로운 값을 할당할 수 있어야 하기 때문에 *iter = value 가 가능해야 한다. 가능한 연산은 다음과 같다. ++iter, iter++, *iter
  • 순방향 반복자 – 입력 반복자와 출력 반복자의 기능에 몇 번이고 쓸 수 있는 기능을 더한 것이다. 따라서, 원소를 읽거나 쓰는 작업에 순방향 반복자를 몇 번이고 원하는 만큼 재사용할 수 있다.
  • 양방향 반복자 – 순방향 반복자와 같은 기능에 역방향으로 이동할 수 있다. 따라서, 가능한 연산은 다음과 같다. –iter, iter–
  • 랜덤 엑세스 반복자 – 양방향 반복자와 같은 기능에 원소들에 마음대로 접근할 수 있는 기능을 더한 것으로 다음과 같은 연산을 지원한다.
    • 정수만큼 증가/감소 – iter + n, iter – n, iter += n, iter -= n
    • 정수로 인덱스 접근 – iter[n], *(iter+n)
    • 두 반복자의 차이 – iter1 – iter2
    • 반복자 비교 – iter1 < iter2 …

각 반복자 카테고리는 iterator 템플릿에 타입 인수로 사용된 빈 클래스인 반복자 태그 클래스로 확인할 수 있다. 해당 클래스의 목적은 특정 반복자 타입이 무엇을 할 수 있는지 지정하고 iterator 템플릿 타입 인수로 사용하는 것이다. 아래는 반복자 태그 클래스들 이고, 상속 구조로 되어 있다. 따라서, 반복자 카테고리를 누적하는 형태인 것이다.

  • input_iterator_tag
  • output_iterator_tag
  • forward_iterator_tag 는 input_iterator_tag 에서 파생
  • bidirectional_iterator_tag 는 forward_iterator_tag 에서 파생
  • random_access_iterator_tag 는 bidirectional_iterator_tag 에서 파생


기타 반복자

스트림 반복자는 I/O 스트림에 연결된 반복자를 얻을 수 있으며, ostream_iterator 는 출력에 istream_iterator 는 입력에 사용된다.

반복자 어댑터는 표준 반복자에 특별한 동작을 제공하는 클래스 템플릿으로 역방향 반복자, 삽입 반복자, 이동 반복자가 있다. 역방향 반복자는 말 그대로 표준 반복자의 반대로 동작한다. rbegin(), rend() 와 같이 r이 붙으면 역방향 반복자라고 생각하면 된다.

삽입 반복자는 back_insert_iterator, front_insert_iterator, insert_iterator 가 존재하고, 이동 반복자는 클래스 객체의 범위를 대상 범위로 이동할 때 사용한다. 이동 반복자는 복사를 수행하지는 않는 이유는 입력 반복자로 사용한 이동 반복자는 반복자가 가리키는 객체를 우측값(rvalue) 로 변환하기 때문에 복제하지 않고 이동하는 것이 가능하기 때문이다.




Reply