[C++] iterator에 대하여 (반복자)

🟡 반복자의 정의

반복자 : 컨테이너의 한 지점을 가리키는 객체.
컨테이너의 종류와 내부 구조에 상관없이 한 요소를 가리키는 목적으로 반복자라는 동일한 장치를 일관된 방법으로 사용할 수 있다.

컨테이너에 대해 알고리즘을 적용하는 등 저장된 요소에 접근해야할 때는 반복자가 필요하다.
즉 반복자가 알고리즘과 컨테이너의 연결 매개체로 존재한다.
그리고 반복자를 통해서 여러 종류의 컨테이너를 동일한 알고리즘을 적용해서 사용할 수 있다.
그에 대한 예시로 STL 알고리즘에서는 container 정보가 아니라 iterator 정보만을 전달해서 사용하도록 하고 있다.

🟡 STL 알고리즘과 컨테이너를 잇는 '반복자'

stl 알고리즘이 받는 반복자는 단일 요소보다는, 반복자 구간을 받아들여서 구간 내의 모든 요소에 대해서 적용한다.
ex) find, sort 알고리즘 원형은 다음과 같다.

InIt find(InIt first, InIt last, const T& val);

void sort(RanIt first, RanIt last);

반복자 구간?

STL 세계에서는 first 부터 last 이전까지의 범위에 대해서 해당 구간이라고 말한다. (모든 컴퓨터 세계에서도 맞다. 왜냐면 모든 숫자가 0부터 시작하기 때문이다. 🌟)

따라서 end 멤버함수를 사용했을 때 반환받는 객체도,,끝다음 점 : past the end라고 해서 마지막 요소의 다음을 의미한다. 이 지점은 실제 컨테이너의 내부는 아니고 끝을 지난 지점이지만, 순회나 에러 처리에 아주 유용하다:

 

이를 통해서 find 함수의 결과로 찾았는지 찾지 못했는지 확인할 때 

반환값이 end와 같다면 못 찾은 것,

아니라면 찾기에 성공한 것

으로 간주할 수 있는 유리함이 있다.

실제로 find 함수가 구현되어있는 꼴은 다음과 같다. (출처 : cplusplusreference.com)

template<class InputIt, class T>
constexpr InputIt find(InputIt first, InputIt last, const T& value)
{
    for (; first != last; ++first)
        if (*first == value)
            return first;
 
    return last;
}

그리고 이 함수를 사용하는 예시는 다음과 같다. 

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    std::vector<int> v {1, 2, 3, 4};
    int n1 = 3;
    int n2 = 5;
 
    auto result1 = std::find(begin(v), end(v), n1);
    auto result2 = std::find(begin(v), end(v), n2);
 
    (result1 != std::end(v))
        ? std::cout << "v contains " << n1 << '\n'
        : std::cout << "v does not contain " << n1 << '\n';
 
    (result2 != std::end(v))
        ? std::cout << "v contains " << n2 << '\n'
        : std::cout << "v does not contain " << n2 << '\n';

}

그리고 구간의 요소 개수를 셀 때도 단순히 last - first 하는 방법으로 구할 수 있다.

 

 

🟡 반복자의 종류

STL이 반복자를 기능별로 분류하는 이유는 알고리즘의 적용 조건을 제한하기 위해서이다.

 

알고리즘은 내부 구현을 위해 컨테이너의 값에 접근할 때 반복자를 통해서 접근한다고 말했었다. 

이때 반복자의 기능을 사용할텐데, 어떤 기능이 요구되느냐에 따라서 반복자의 종류가 나뉘어진다. 

알고리즘에서 필요한 반복자의 종류를 명시해둔다.

 

 

반복자의 종류는 다음과 같다.

반복자	약어	설명
입력	InIt	오로지 입력만 가능하며 쓸 수는 없다.
출력	OutIt	출력만 가능하며 읽지는 못한다.
순방향	FwdIt	입출력이 모두 가능하다. 전진만 가능하다.
양방향	BiIt	앞뒤로 이동할 수 있다. 감소 연산자를 정의한다.
임의 접근	RanIt	임의의 요소를 참조할 수 있다. [ ] 연산자를 정의한다.

 

 

알고리즘에서 필요한 반복자를 명시해둔다고 했다.

find와 sort 알고리즘의 원형을 다시 한 번 더 보자.

InIt find(InIt first, InIt last, const T& val);

void sort(RanIt first, RanIt last);

find는 검색 중에 값을 읽기만 하고 순차적으로 값을 점검하므로 입력 반복자를 요구한다. 원형의 first, last에 InIt라는 반복자 타입이 분명히 명시되어 있다. 

반면 sort의 원형에는 RanIt 반복자 타입이 명시되어 있으므로 이 함수로 정렬을 하려면 임의 접근 반복자를 제공해야 한다.

 

알고리즘이 요구하는 반복자 타입은 최소한의 요구사항이므로 더 상위의 반복자도 사용할 수 있다. 임의 접근 반복자는 입력 반복자의 모든 기능을 지원하므로 find 알고리즘에도 당연히 사용할 수 있다.

 

 

 

🟡 반복자의 종류 - 자세히

🔵 input iterator

입력 반복자(Input Iterator)는 가장 기본적인 기능만 제공하는 반복자이다. 반복자이므로 컨테이너의 한 위치를 가리키는 것은 당연하고 반복자가 가리키는 위치의 요소를 * 연산자로 읽을 수도 있다. 읽는 것만 가능하므로 * 연산자를 사용하더라도 요소의 값을 변경하는 것은 불가능하다. 

 

🔵 output iterator

* 연산자를 사용하여 요소의 내용을 변경할 수 있는 반복자이다. 쓰기가 가능하다면 보통 읽기도 가능하지만 읽는 기능은 없어도 상관없다

 

-> 두 유형의 반복자는 입출력 스트림에만 적용된다. STL 컨테이너들은 모두 읽기, 쓰기가 동시에 가능하므로 이 두 유형보다 더 높은 레벨의 반복자를 지원한다. 

 

🔵 forwad iterator

일단 읽기, 쓰기가 둘다 가능하다.

그리고 ++ 연산자를 정의해서 앞으로 전진이 가능하다. 전위형, 후위형 모두 구현되어 있으므로 it++, ++it 모두 사용가능하다.
단, --연산자는 구현되어있지 않고 역방향으로 이동이 불가능하다. 

 

🔵 bidirectional iterator

읽기, 쓰기가 들다 가능하다. 

그리고 foward iterator와 다르게 역방향으로 이동하는 --연산자도 구현되어있다.

STL에서 제공하는 이중 연결리스트 list 가 대표적이다.

 

ex) <biIt, FwdIt iterator를 입력받는 STL 알고리즘 2개>

void replace (FwdIt first, FwdIt last, const Type& Old, const Type& New);

void reverse(BiIt first, BiIt last);

• replace 함수 :
  매개변수로 받은 반복자first ~ last를 통해 구간을 순회하면서 old를 찾아서 New로 대체한다. 
  읽기, 쓰기가 가능해야 하고, 전진만해도 상관없으므로 foward Iterator가 젹혀있다.
• reverse 함수:
  구간 내의 요소들을 모두 반대로 뒤집어서 재배치하는 함수로, 
  읽기, 쓰기 뿐만 아니라 역행도 가능해야 한다. 따라서 bidirectional Iterator가 적혀있다. 

 

🔵 random iterator

최상위 레벨의 반복자이며 제공하는 기능이 가장 많다.

양방향 반복자의 모든 기능을 포함하고 있다.

따라서 * 연산자로 읽기, 쓰기와 ++, -- 연산자로 앞 뒤로 이동하기, 같은 위치를 여러 번 액세스 하기 기능을 제공한다.

여기에 추가로 임의 위치로 이동할 수 있는 기능이 추가로 제공되는데 거리에 상관없이 항상 상수 시간내에 이동 가능하다.

 

임의 접근이 가능한 이유는  컨테이너의 요소들이 배열처럼 인접하게 배치되어 있기 때문이다.

요소의 크기가 일정하고 서로 이웃해 있으므로 이동하고 싶은 거리에 요소 크기를 곱한만큼 더하기만 하면 즉시 이동 가능하다.  이렇게 포인터 연산처럼 원하는 위치에 + (n * sizeof()) 를 사용하면 원하는 위치에 접근할 수 있는 것이다. 

 

ex) <random iterator 를 사용하는 함수>

 

void advance(InIt &first, int off);
int distance(InIt first, InIt last);

• advance 함수
  : 입력받은 반복자를 off만큼 이동시킨다. 음수일 수도 있으므로 역행도 가능하다.
• distance 함수
  : 두 반복자 사이의 거리를 계산해서 정수값을 반환한다. 
  (반복자끼리 뺄셈은 안되지만 distance 함수를 통해 두 반복자간 거리를 구하는 것이 가능)

 

 

 

 

🟡 반복자 사용 시 주의점

반복자에 대해서 주의할 점은 STL알고리즘은 반복자의 유효성을 전혀 점검하지 않고 항상 유효하다고 가정한다는 점이다. 반복자가 틀린 위치를 가리키고 있을 경우의 결과는 정의되어 있지 않다.
STL도 결국 범위를 점검하지 않는 C언어의 한계는 벗어나지 못했는데 그 이유는 성능이다. 하지만 반복자는 보통 증가, 감소에 의해 구간내에서만 움직이므로 큰 문제가 되지 않고 있다.

 

참고  :http://www.soen.kr/