39-2-마.반복자와 알고리즘

여기까지 다섯 가지 레벨의 반복자를 살펴 봤는데 반복자 수준에 따라 적용 가능한 연산의 종류가 달라진다. 상위 반복자는 하위 반복자를 포함하므로 반복자끼리는 다음과 같은 계층을 구성한다.

이 그림에 의할 것 같으면 입력, 출력 반복자는 배타적이며 서로 포함 관계가 아니다. 입력 반복자는 출력에 쓸 수 없고 출력 반복자는 입력에 쓸 수 없다. 순방향 반복자는 입력, 출력 반복자의 기능을 포함하며 여기에 같은 위치를 여러 번 액세스 하는 기능을 추가로 가진다. 순방향 반복자는 입력, 출력을 겸하므로 InIt, OutIt를 요구하는 알고리즘에도 사용할 수 있다.

양방향 반복자는 순방향 반복자의 기능에 역방향으로 이동하는 -- 연산자를 추가로 가진다. 임의 접근 반복자는 양방향 반복자에 +n 연산을 추가로 정의하며 이 연산이 추가됨에 따라 [ ], += 등도 가능해진다. 또한 요소들이 인접해 있음에 따라 반복자끼리의 뺄셈과 대소 비교까지도 가능하다. 상위의 반복자는 하위 반복자의 기능을 포함하므로 하위 반복자를 요구하는 알고리즘에는 더 상위의 반복자를 항상 사용할 수 있다. 양방향 반복자는 입력이나 순방향을 요구하는 알고리즘에 별 제약없이 사용할 수 있으며 임의 접근 반복자는 모든 알고리즘에 사용 가능하다.

그러나 역은 성립하지 않는다. 양방향 반복자를 요구하는 알고리즘에 입력이나 순방향 반복자를 쓸 수는 없으며 임의 접근 반복자가 필요한 곳에는 하위의 반복자를 사용할 수 없다. STL의 모든 컨테이너는 자신이 제공하는 반복자의 종류를 명시하고 있으며 알고리즘은 요구하는 최소의 반복자를 명시하고 있다. 그래서 컨테이너와 알고리즘은 최적의 결합만 가능하다.

이 둘이 맞거나 아니면 더 상위의 반복자여야만 컨테이너와 알고리즘이 효율적으로 결합할 수 있다. 예를 들어 리스트는 임의 접근이 불가능하여 양방향 반복자를 제공하므로 sort나 binary_search 알고리즘을 적용할 수 없다. 요구 사항에 맞지 않는 반복자를 전달하면 컴파일 중의 에러로 처리된다. 이를 테스트해 보기 위해 양방향 반복자를 제공하는 리스트에 임의 접근 반복자를 요구하는 sort 알고리즘을 적용해 보자.

예 제 : wrongiter

#include <iostream>

#include <list>

#include <algorithm>

using namespace std;

void main()

{

int ari[]={2,8,5,1,9};

list<int> li(&ari[0],&ari[5]);

sort(li.begin(),li.end());

}

sort 함수는 정렬 구간의 길이를 구하기 위해 반복자끼리 뺄셈을 하기도 하고 값을 비교 및 교환하기 위해 수시로 [ ] 연산자를 사용하는데 양방향 반복자에는 이 연산들이 정의되어 있지 않으므로 에러로 처리된다. 템플릿 인수로 전달된 반복자 타입이 sort 함수 템플릿 본체의 코드를 모두 지원하지 못하는 것이다. 반복자끼리 뺄셈이 가능한 경우는 임의 접근 반복자뿐이므로 sort는 반드시 임의 접근 반복자와 함께 사용해야 한다.

이런 불가능한 또는 비효율적인 조합에 대해 STL은 컴파일 중에 타입 불일치 에러를 발생시킨다는 점이 중요하다. 컴파일 에러는 개발 중에 원인을 분명히 알 수 있으므로 실행중의 에러보다는 훨씬 더 수정하기 쉽다. 또한 타입 점검이 컴파일 중에 수행되므로 실행시의 효율이 더 좋아질 수 있는 것이다.