반복자(iterator)_1

반복자는 포인터와 유사한 객체로서 STL 알고리즘이 컨테이너에 저장된 객체들의 시퀀스를 순회할 때 사용한다. 반복자는 컨테이너와 제네릭 알고리즘 사이를 이어주는 중간자로서, STL 설계에 있어서 매우 중심적인 역할을 담당하고 있다. 이러한 반복자 덕분에 데이터 구조의 저장방식에 관계없이 알고리즘을 구현할 수 있는 것이다. 그러나 효율성을 위해서는 모든 제네릭 알고리즘이 모든 컨테이너와 작동이 가능하도록 할 수는 없다(즉, 제네릭 알고리즘의 범용성이 제한된다). 그렇다면 주어진 제네릭 알고리즘과 컨테이너가 상호간에 작동이 가능한지는 어떻게 알 수 있는가? 이 물음에 답변하기 위해서는, 우선 STL 이면에 깔려 있는 핵심적인 기술 개념을 하나 알아둬야 할 필요가 있다. 그것은 반복자가 다음 다섯 가지의 부류 즉, 입력 반복자, 출력 반복자, 순방향 반복자, 양방향 반복자, 임의 접근 반복자로 분류되어 있다는 점이다.

 

각각의 반복자 종류에 관한 설명에 들어가기에 앞서, 반복자 구간(iterator range)과 이의 표기법에 관해 알아보기로 하자. STL의 모든 알고리즘은 반복자를 통해서 시퀀스를 접근하는데, 보통은 시퀀스의 시작을 가리키는 first와 시퀀스의 끝을 가리키는 last로 구성된 반복자 한 쌍을 사용한다. 반복자 쌍으로 시퀀스를 결정하는 이러한 방식을 간결하게 표현하기 위해서 반복자 구간이라는 개념을 사용하는데, first에서 last까지의 구간은 first부터 출발해서 last에 도달할 때까지 operator++ 연산을 반복 적용하여 얻은 반복자들로 구성된다. 여기서 last는 구간에서 제외된다는 점에 유의해야 한다. 구간은 다음과 같이 표기한다.

 

[first, last)

 

그리고 이 구간은 last가 first로부터 도달 가능해야 유효(valid)한 구간이 된다. 모든 STL 알고리즘은 인자로 넘겨받은 구간이 유효하다는 가정 하에 작업을 수행하며, 유효하지 않은 반복자 구간을 사용한 수행된 알고리즘의 결과는 정의되어 있지 않다.

 

특별히, fisrt == last 인 구간은 빈 구간(empty range)이라고 한다. 빈 구간도 물론 유효한 구간이긴 하지만, 이 구간에는 유효한 데이터를 가리키는 반복자가 전혀 포함되어 있지 않다.

 

 

1. 입력 반복자

STL 반복자를 종류별로 구분하여 정의한 것은 이를 필요로 하는 알고리즘의 요구를 반영하기 위해서이다. STL의 제네릭 find 알고리즘은 배열, 벡터, 리스트를 비롯한 여러 데이터 구조에서 원하는 값을 찾아내고자 할 때 사용한다. 뿐만 아니라, 입력 스트림 반복자라 불리는 반복자를 이용하면, find 알고리즘을 이용하여 입력 스트림을 검색할 수도 있다. find 알고리즘은 다음과 같이 템플릿 함수로 간단하게 정의할 수 있다.

template<typename InputIterator, typename T> InputIterator find(InputIterator first, InputIterator last, const T& value) {     while( fisrt! = last && *first != value )         ++first;     return first; }

위 코드에서 InputIterator 객체가 사용된 표현식들을 살펴보자.

- first != last - ++first - *first

find가 제대로 동작하기 위해서는 위 표현식들이 다음과 같은 의미를 가지도록 정의되어 있어야 한다.

- first != last는 first가 last와 동일하지 않은 경우에 true를 리턴해야 하며, 동일한 경우에는 false를 리턴해야 한다. - ++first는 first의 값을 하나 증가시키고, 증가된 값을 리턴해야 한다. - *first는 first가 가리키는 값을 리턴해야 한다.

그리고 find 알고리즘을 효율적으로 수행할 수 있으려면, 이 연산들이 각각 상수 시간 내에 수행되어야만 한다.

 

위에 열거한 요구 사항들은 입력 반복자(input iterator) 부류의 정의에서 요구하는 요구 사항과 거의 일치하는 것들이다. 입력 반복자가 되기 위해서는 == 연산자와 후위 ++ 연산자, 이 두 가지가 추가로 정의 되어 있어야 한다.

 

물론, 방금 언급한 요구 사항들은 일반 포인터 타입에도 똑같이 적용되는 것들이다. 하지만 일반 포인터 타입에는 입력 반복자 정의에서는 요구하지 않는 특성들이 많다. 예를 들어, 입력 반복자에는 *first = ... 을 통해 특정 위치에 값을 대입할 수 있어야 된다는 요구 사항은 없다. 특수한 입력 반복자라면 이 연산을 지원할 수도 있겠지만, 반드시 충족시켜야 하는 요구사항은 아니다.

 

여기서 유의할 점이 하나 있는데, 입력 반복자라는 용어는 한 가지 타입을 지칭하는 것이 아니라는 것이다. 앞에서 언급한 기본적인 요구 사항들을 만족하기만 하면, 그러한 타입들을 모두 입력 반복자라고 부르는 것이다.

 

배열과 리스트 반복자의 경우에는 입력 반복자 연산 이외의 다른 연산들도 지원이 되는데, 예를 들면, 반복자가 참조하는 위치에 값을 대입하는 것이 가능하다. 그러나 입력 스트림 반복자에서는 입력 반복자 연산들만이 지원된다.

 

 

2. 출력 반복자(output iterator)

출력 반복자는 시퀀스에 값을 쓰는 것은 가능하지만 시퀀스로부터 값을 읽는 기능은 요구하지 않는다. 따라서, first가 출력 반복자라면 *first = ... 와 같이 사용할 수는 있지만, 반복자 first가 가리키는 값을 얻기 위해서 표현식에 *first를 사용할 수 있다는 것은 보장하고 있지 않다. 입력 반복자의 요구 조건과 또 하나 다른 점은 출력 반복자에 == 또는 != 연산자가 반드시 정의되어 있을 필요가 없다는 점이다. 하지만 전위 ++ 연산과 후위 ++연산에 관해서는 입력 반복자와 동일한 요구 조건을 가지고 있다. 입력 반복자에서처럼, 출력 반복자라는 용어도 그 자체로 타입을 표현하고자 하는 것이 아니다. 대신에, 이러한 요구 조건들을 만족하는 타입들은 모두 출력 반복자라고 부르는 것이다.

 

예를 들어, 시퀀스를 다른 시퀀스로 복사하는 STL copy 알고리즘을 살펴보자.

template<typename InputIterator, typename OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) {     whie(first!=last)     {         *result = *first;         ++first;         ++result;     }     return result; }

 

STL은 출력 스트림 반복자(ostream iterator)라 불리는 특별한 출력 반복자를 제공하는데, 출력 스트림에 값을 쓸 때는 이 반복자를 사용한다. 예를 들어, 다음 코드는 리스트의 원소들을 출력 스트림 cout로 출력한다. 

list<int> list1; // list1에 값을 삽입하는 코드   // 출력 스트림 반복자, out을 선언 ostream_iterator<int> out(cout, "\n");   copy(list1.begin(), list1.end(), out);

ostream_iterator 생성자에 사용되는 인자로는 출력 스트림 객체와 출력 스트림으로 출력되는 값들 사이에 함께 삽입되어 출력될 문자열이 사용된다. 위 코드에서는 값이 출력될 때마다 서로 다른 줄에 쓰여지도록 하기 위해서, 개행(newline) 문자를 사용하였다.

 

 

3. 순방향 반복자(forward iterator)

순방향 반복자는 입력 반복자인 동시에 출력 반복자인 반복자를 말하는데, 이것은 결과적으로 읽기와 쓰기가 모두 가능하고 한쪽 방향으로의 순회가 가능하다는 것을 의미한다. 이외에도 순방향 반복자는 입력 반복자와 출력 반복자의 요구 사항에는 포함되지 않은 성질을 하나 가지고 있다. 순방향 반복자를 저장한 뒤에, 이를 이용하여 동일한 위치에서 순회를 다시 시작할 수 있다. 이러한 성질 때문에 find와 merge 같은 단일 패스 알고리즘에서뿐만 아니라,, 다중 패스 알고리즘에서도 순방향 반복자를 사용할 수 있게 된다.

 

시퀀스로부터 값을 읽어서 시퀀스에 값을 쓰는 알고리즘을 예로 들자면, replace 알고리즘을 생각해 볼 수 있다. 이 알고리즘은 구간 [first, last)에서 값이 x인 모든 원소를 찾아 y로 치환한다.

template<typename ForwardIterator, typename T> void replace(ForwardIterator first, ForwardIterator last, const T& x, const T& y) {     while(first != last)     {         if(*first==x)             *first = y;         ++first;     } }

이 알고리즘은 다양한 데이터 구조와 함께 사용할 수 있는데, 여기서 템플릿 인자인 ForwardIterator에 사용되는 타입은 반드시 순방향 반복자 부류의 요구 사항을 만족시키는 것이어야 한다.

물론, 배열에 함께 사용되는 일반 포인터 타입은 순방향 반복자 부류의 요구 사항을 만족하기 때문에 다음과 같이 사용할 수 있다.

 

int a[100];  //... a[0], ..., a[99]를 초기화 하는 코드   // 배열 내의 모든 5를 6으로 치환 replace(&a[0], &a[100], 5, 6);

 

deque<T>::iterator 타입도 순방향 반복자의 요구 사항을 모두 충족하고 있기 때문에, replace 알고리즘을 덱에도 사용할 수 있다.

deque<char> deque1;   // ... deque1에 문자들을 삽입하는 코드    // deque1 내의 모든 'e'를 'o'로 치환 replace(deque1.begin(), deque1.end(), 'e', 'o');

 

 

4. 양방향 반복자(bidirectional iterator)

양방향 반복자는 순방향 반복자와 유사하지만, 양방향으로 이동이 가능하다는 점에서 차이가 난다. 다시 말해, 양방향 반복자는 모든 순방향 반복자 연산을 지원할 뿐만 아니라, 순회 방향을 뒤집을 수 있는 -- 연산을 추가로 지원한다.

 

양방향 반복자에는 operator--의 전위 버전과 후위 버전이 모두 정의되어 있어야 한다. 여기서, 전위 버전은 반복자를 감소시키되 감소시키기 이전 값을 리턴한다. operator--의 전위 버전과 후위 버전 모두 상수 시간 내에 수행되어야 한다.

 

반대 방향으로 시퀀스를 순회하는 기능은 매우 중요한데, 왜냐하면 일부 알고리즘에서는 이 기능 없이는 효율적인 수행이 불가능하기 때문이다. 예를 들어, 알고리즘은 시퀀스의 담긴 원소들의 순서를 거꾸로 뒤집을 때 사용하는데, 이 때 반드시 양방향 반복자가 필요하다.

예를 들어, 배열에서 사용되는 일반 포인터는 양방향 반복자의 모든 요구 사항을 만족시키고 있으므로, 다음과 같이 사용할 수 있다.

int a[100]; // ... a[0], ... , a[99]를 초기화하는 코드   //배열에 속한 값들의 순서를 뒤집는다. reverse(&a[0], &a[100]);

STL의 list 컨테이너도 양방향 반복자를 제공하기 때문에, 다음과 같이 reverse와 함께 사용할 수 있다.

 

list<int> list1; // ... list1에 값들을 삽입하는 코드   // list에 속한 값들의 순서를 뒤집는다. reverse(list1.begin(), list1.end());

list 클래스가 양방향 반복자를 지원한다는 것은 리스트가 이중 연결 리스트(doubly linked list)로 구현되었다는 것을 의미한다.

단인 연결 리스트(singly linked list)로는 operator--을 효율적으로 구현할 수 없다.(즉, 단일 연결 리스트로는 상수 시간 내에 수행되도록 구현할 수 없다는 의미).

 

따라서, 양방향 반복자를 사용해야 한다는 요구 사항이 있기 때문에 시퀀스를 양방향으로 순회하내야 하는 reverse와 같은 알고리즘이 효율적으로 수행될 수 있는 것이다.

 

 

5. 임의 접근 반복자(random access  iterator)

앞에서 살펴본 네 가지 부류의 데이터 구조만으로는 STL의 모든 알고리즘을 충분히 설명할 수 없다. 어떤 알고리즘은 효율적인 수행을 위해서 시퀀스 내의 어떠한 위치라도 다른 임의의 위치로부터 상수 시간 내에 도달 가능(reachable)해야 된다는 더 강력한 요구 사항을 가진 반복자를 필요로 한다.

임의 접근 반복자는 양방향 반복자에서 지원하는 모든 연산을 지원해야 하며, 추가로 다음 것들도 지원 가능해야 한다.

(다음에서, r과 s는 임의 접근 반복자이며, n은 정수 표현식이다)

- 정수 덧셈과 뺄셈 : r+n, n+r, r-n으로 표현 - n개 원소만큼 떨어진 위치를 접근 : r[n]으로 표현하며, *(r+n)과 동일한 의미 - 양방향으로의 "빅 점프(big jump)" : r+=n, r-=n으로 표현 - 반복자 뺄셈 : r-s로 표현하며 정수 값을 리턴 - 비교 연산 : r<s, r>s, r<=s, r>=s로 표현하며, bool 값을 리턴

 

벡터나 덱과 같은 STL의 임의 접근 데이터 구조에서는 이러한 요구 사항들을 충족하는 반복자들을 제공함으로써, 상수 시간 내에 데이터 구조내의 임의의 위치에 도달할 수 있도록 하고 있다.

 

 

6. STL 반복자 계층 구조 : 알고리즘과 컨테이너의 효율적인 결합

반복자의 개념과 STL에서 반복자가 담당하고 있는 역할을 이해하기 위해서는 반복자를 입력/출력, 순방향, 양방향, 임의 접근 반복자 부류로 분류한 이유를 반드시 이해하고 넘어가야 한다. 이렇게 분류된 반복자 부류들은 다음과 같은 계층 관계를 가지고 있다.

- 순방향 반복자는 입력 반복자이자 출력 반복자이다. - 양방향 반복자는 순방향 반복자이며, 따라서 입력 반복자이자 출력 반복자이다. - 임의 접근 반복자는 양방향 반복자이며, 따라서 순방향 반복자인 동시에 입력 반복자이자 출력 반복자이다.

 

이러한 계층 관계는 다음 의미를 내포하고 있다.

- 입력 또는 출력 반복자를 필요로 하는 알고리즘은 순반향이나 양방향 또는 임의 접근 반복자와도 함께 사용할 수 있다. - 순방향 반복자를 필요로 하는 알고리즘은 양방향 또는 임의 접근 반복자와도 함께 사용할 수 있다. - 양방향 반복자를 필요로 하는 알고리즘은 임의 접근 반복자와도 함께 사용할 수 있다.

 

따라서, 반복자 부류들은 컨테이너 스펙과 알고리즘 스펙에서 다음과 같이 사용되고 있다.

- 컨테이너 클래스에 대한 설명에는 컨테이너 클래스가 제공하는 반복자 부류가 명시되어 있다. - 제네릭 알고리즘에 대한 설명에는 주어진 알고리즘과 함께 사용할수 있는 반복자 부류가 명시되어 있다.

 

반복자 계층 구조는 STL 설계에 담겨진 기본 개념을 잘 보여주고 있다. 즉, STL 컨테이너와 알고리즘 인터페이스는 효율적인 조합은 허용하되, 비효율적인 조합은 되도록 피할 수 있도록 설계되었다는 것이다. 효율적인 조합은 컴파일 에러가 발생하지 않는다. 비효율적인 조합이라고 해서 모두 컴파일 에러가 발생하는 것은 아니지만, 대부분의 경우 컴파일 에러가 발생하며, 컴파일 에러를 방지하려면, 프로그래머가 일부 연산을 추가로 코딩해야 하므로, 많은 노력이 필요하다.

 

 

 

 

 

 

- STL 튜토리얼·레퍼런스 가이드 제2판 中 -