39-2-다.순방향, 양방향 반복자
순방향 반복자(Foward Iterator)는 입력 출력이 모두 가능한 반복자이다. 입력, 출력 반복자는 둘 중 하나만 가능한데 비해 순방향 반복자는 읽기, 쓰기가 모두 가능하다. 이름이 의미하듯이 순방향으로 이동 가능하다는 조건도 포함된다. 순방향으로 이동 가능하다는 것은 ++ 연산자를 정의한다는 뜻인데 전위형, 후위형 모두 정의되어 있으므로 ++it, it++ 두 형태를 자유롭게 사용할 수 있다. 그러나 -- 연산자가 정의되어 있지 않으므로 역방향으로는 이동할 수 없다.
입출력을 다 할 수 있다는 것 외에도 순방향 반복자가 입력, 출력 반복자와 다른 점은 같은 위치를 여러 번 읽고 쓸 수 있다는 점이다. 반복자가 컨테이너내의 요소 하나를 가리키고 있을 때 외부에서 특별한 조작을 하지 않으면 이 반복자는 그 요소를 계속 가리킨다. 그래서 반복자를 저장해 놓았다가 이 반복자가 가리키는 위치에서 언제든지 재순회가 가능하다.
반면 입력, 출력 반복자는 이런 특성이 없어 한 위치에 대해 딱 한 번씩만 읽고 쓰기가 가능하다. 키보드는 사용자가 키를 누를 때 그 값을 받아 놓지 않으면 한 번 읽은 내용을 다시 읽지 못한다. 입력되는 시점에 딱 한 번만 읽을 수 있다. 콘솔 화면이나 프린터는 일단 출력해 버리면 더 이상 수정 불가능하다. 이미 출력해 버린 문자를 다른 문자로 바꿔서 재출력할 수는 없다.
순방향 반복자는 한 위치를 여러 번 읽고 쓸 수 있기 때문에 다중 패스 알고리즘을 지원한다. 다중 패스 알고리즘은 구현을 위해 컨테이너를 여러 번 스캔해야 하는데 대표적으로 부분 일치 구간을 검색하는 search 알고리즘을 들 수 있다. search는 표준 strstr 함수와 동작이 비슷한데 부분 일치 구간을 찾기 위해서는 검색 대상 구간과 완전히 일치하는 부분을 찾을 때까지 컨테이너의 각 요소들을 여러 번 읽어야 한다. 입력 반복자는 읽기는 가능하지만 같은 위치를 두 번 읽을 수 없으므로 이런 알고리즘 구현에는 적합하지 않다.
표준 STL에는 구현되어 있지 않지만 단순 연결 리스트(slist)를 가리키는 반복자가 대표적인 순방향 반복자이다. 단순 연결 리스트는 읽기 쓰기가 가능하며 한 노드를 여러 번 읽을 수도 있다. 그러나 단순 연결 리스트의 노드는 다음 노드를 가리키는 링크 하나밖에 없으므로 전진만 가능하며 후진은 불가능하다. 이 조건에 맞는 반복자가 바로 순방향 반복자이다.
양방향 반복자(Bidirectional Iterator)는 역방향으로도 이동이 가능한 반복자이다. 순방향 이동을 위한 ++ 연산자는 물론이고 역방향의 이동을 위한 -- 연산자도 전위형, 후위형으로 각각 구현되어 있다. 역방향으로 검색한다거나 모든 요소의 순서를 반대로 뒤집을 때는 앞뒤로 자유롭게 이동해야 하므로 역방향 반복자가 필요하다. STL 컨테이너 중 이중 연결 리스트로 구현되어 있는 list가 양방향 반복자를 제공한다. 양방향 반복자는 순방향 반복자의 기능을 포함한다.
다음 두 알고리즘은 각각 순방향 반복자와 양방향 반복자를 요구한다. 함수의 원형에 FwdIt, BiIt라는 반복자 타입이 분명히 명시되어 있다.
void replace (FwdIt first, FwdIt last, const Type& Old, const Type& New);
void reverse(BiIt first, BiIt last);
replace는 컨테이너의 Old값을 찾아 New 값으로 교체한다. 찾는 값이 맞는지 확인하기 위해 반복자를 읽어야 하며 맞을 경우 New로 바꾸기도 해야 하므로 읽기 쓰기가 모두 필요하다. 또한 대체 동작을 여러 번 할 필요는 없으므로 구간의 처음부터 끝까지 한 번만 순회하면서 모든 작업을 마칠 수 있으며 한 번 지나온 위치를 다시 검색할 필요는 없다. 그래서 replace가 요구하는 최소의 반복자는 순방향 반복자이다.
reverse는 구간내의 요소들을 반대로 뒤집어 재배치하는데 읽기 쓰기가 모두 가능해야 하며 양쪽 끝에서 동시에 순회를 시작하여 값을 교환해야 하므로 반복자가 증가, 감소를 모두 지원해야 한다. 그래서 reverse는 순방향 반복자로는 구현될 수 없으며 최소한 양방향 이동을 지원해야 한다. 다음 예제는 두 알고리즘을 테스트한다.
|
예 제 : fwdbiiterator |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<typename C> void dump(const char *desc, C c) { cout.width(12);cout << left << desc << "==> ";
copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }
void main()
{
int ari[]={78,85,95,93,86,60,72,99,56,85};
vector<int> vi(&ari[0],&ari[10]);
dump("원본",vi);
replace(vi.begin(),vi.end(),85,100);
dump("대체후",vi);
reverse(vi.begin(),vi.end());
dump("뒤집은 후",vi);
}
벡터에 점수값들을 무작위로 나열해 놓고 대체 및 뒤집기를 해 보았다. replace로 85점짜리를 찾아 100으로 대체한 후 reverse로 벡터를 통째로 뒤집는다. 출력 결과는 다음과 같다. 벡터를 덤프할 때는 앞 항에서 소개한 dump 함수를 사용했는데 이미 살펴본 소스이므로 앞으로는 활용만 하기로 하자.
원본 ==> 78 85 95 93 86 60 72 99 56 85
대체후 ==> 78 100 95 93 86 60 72 99 56 100
뒤집은 후 ==> 100 56 99 72 60 86 93 95 100 78
최초 ari 배열에 초기화된 점수들이 출력되었고 85가 100으로 바뀐 벡터가 그 다음줄에 출력되었으며 마지막줄에 순서가 뒤집어진 벡터가 출력되었다. 두 알고리즘이 어떻게 동작할지 상상해 보자.
replace는 전진 이동하며 읽고 쓰기만 반복하므로 순방향 반복자이면 충분하다. 반면 reverse는 한쪽은 앞에서 뒤로, 한쪽은 뒤에서 앞으로 이동하면서 값을 교환(읽기 + 쓰기)해야 하므로 양방향으로 이동할 수 있어야 한다. 이 그림에서 보다시피 두 알고리즘이 요구하는 반복자의 기능이 다르다. 헤더 파일을 열어서 구현된 코드를 살펴보면 이 알고리즘들이 어떻게 동작하며 왜 순방향, 역방향 반복자를 요구하는지 확실히 알 수 있다.