39-1-나.반복자 구간

모든 알고리즘 함수들은 작업 대상을 전달받기 위해 반복자를 인수로 받아들인다. 특정한 단일 요소에 대해 적용되는 알고리즘은 대상 요소 하나만을 받아들이지만 대개의 경우는 두 개의 반복자로 표현되는 반복자 구간(iterator range)을 받아들여 구간내의 모든 요소에 대해 적용된다. 가장 자주 사용되는 find, sort함수의 원형을 보자.

 

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

void sort(RanIt first, RanIt last);

 

둘 다 first, last 두 개씩의 반복자를 받으므로 반복자 구간에 대해 동작한다. 임의의 값을 찾기 위해서는 검색 범위가 지정되어야 하며 정렬이라는 것도 복수 개의 요소들을 기준에 따라 재배치하는 것이므로 구간이 전달되는 것이 합당하다. 통상 구간의 시작점은 first라는 이름을 쓰고 끝은 last라는 이름을 쓰는데 first와 last가 지정하는 반복자 구간에 first는 포함되지만 last는 포함되지 않는다. 그래서 first, last 구간의 정확한 의미는 다음 그림과 같다.

이 구간을 수학적으로 표현하면 first <= range < last와 같이 표기할 수 있으며 STL에서는 닫힌 괄호와 열린 괄호를 사용하여 [first, last)로 표기하기도 하는데 이 책은 간단하게 first ~ last로 표기하기로 한다. 일상 생활에서는 a ~ b범위를 칭하면 통상 a이상 b이하를 의미하며 b도 포함된다. 담임 선생님이 오늘은 5번부터 10번까지 화장실 청소를 하라면 10번 학생도 당번에 포함되는 것이 상식적이다. 그러나 STL의 세계에서는 범위의 끝은 제외하는 것이 상식이다.

이는 비단 STL에서만 그런 것이 아니라 모든 프로그래밍 언어와 운영체제 등에도 공통적으로 적용되는 범위 규칙이다. 즉, 디지탈의 세계에서 범위를 칭하면 항상 끝은 범위에 포함되지 않는 것으로 취급한다. 왜냐하면 컴퓨터에서 숫자는 0부터 시작(Zero Base)되기 때문에 끝을 제외해야 제외된 끝과 개수가 일치하기 때문이다. 예를 들어 크기 10의 배열 ar[10]을 0으로 채우는 코드는 보통 다음과 같이 루프를 작성한다.

 

for (i=0; i<10; i++) ar[i]=0;

 

조건식이 i<10로 되어 있어 10은 처리 대상에 포함되지 않는다. 10이 제외되어야 ar[i]=0; 처리 회수가 10이 되며 사실 ar[10]은 존재하지도 않는다. 조건식을 i <= 10 이렇게 썼다가는 무슨 봉변을 당하게 될지 모른다. ar 배열의 마지막 요소가 9라고 해서 조건식을 i<=9로 쓰지는 않는데 기능적으로 똑같은 루프라 하더라도 끝을 포함하면 여러 모로 불편해진다.

STL 함수들도 내부적으로 루프를 많이 사용하는데 모두 이런 식으로 작성되어 있다. STL의 모든 컨테이너는 시작점과 끝다음점을 조사하는 begin, end 멤버 함수를 제공한다. 끝다음점(past the end)이란 마지막 요소의 다음을 의미하는데 배열의 경우는 배열 크기와 같은 첨자가 될 것이고 연결 리스트의 경우 tail 위치가 될 것이다. 이 지점은 실제 컨테이너의 내부는 아니며 이미 끝을 지난 지점이지만 순회나 에러 처리에 아주 유용하다. 끝다음점 직전까지만 순회하면 지정한 구간의 모든 요소를 안전하게 방문할 수 있다. find 함수의 구현 코드를 보자.

 

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

{

     for (;first != last; ++first) {

          if (*first == val) break;

     }

     return first;

}

 

first가 계속 증가하면서 컨테이너의 다음으로 이동하는데 조건식이 first != last로 되어 있다. 따라서 first가 last가 아닌 동안 순회를 반복하며 last에 도달했을 때 루프를 탈출하므로 결국 last는 처리 대상에서 제외된다. 조건식을 first < last로 대소 비교하지 않고 first != last로 부등 비교를 하는 점에 주목하도록 하자. 제어 변수가 정수일 때는 다음처럼 부등 비교를 하는 경우가 별로 없으며 이렇게 루프를 짜 본 경험도 없을 것이다.

 

for (i=0; i!=10; i++) ar[i]=0;

 

정수 루프에는 i < 10이 정석인데 이렇게 하면 증감식이 i+=3으로 갑자기 바뀌더라도 무난히 루프를 빠져 나갈 수 있다. 그러나 반복자는 대소 비교를 하지 않고 항상 부등 비교를 하는데 왜 그런가 하면 일반화된 반복자는 대소 비교가 가능하지 않기 때문이다. 리스트의 반복자는 메모리 여기 저기에 흩어져 있는 노드의 포인터인데 앞쪽 노드가 반드시 앞쪽 번지에 있다고 보장할 수 없다. 그래서 부등 비교를 할 수밖에 없으며 또한 반복자는 절대 두 칸 이상 이동하지 않으므로 부등 비교를 해도 안전하다. 만약 last도 처리 대상에 포함된다면 루프는 좀 더 복잡해지고 게다가 에러 처리 방법이 묘연해진다.

 

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

{

     for (;; ++first) {

          if (*first == val) return first;

          if (first == last) break;

     }

     return ???;

}

 

last의 값도 검색 대상이므로 일단 비교를 한 후 last이면 break해야 한다. last까지 검색을 했는데 값이 발견되지 않았다면 이때는 실패의 의미로 과연 어떤 값을 리턴해야 할까? 반복자는 포인터의 NULL에 해당하는 특이값이 없어 마땅히 실패를 알리 방법이 없다. last가 범위에서 제외된다면 last를 리턴하는 것이 검색 실패의 뜻으로 사용될 수 있는데 구간 끝을 지나서 검색되었다는 것은 자연스럽게 없다는 뜻이 되는 것이다.

범위에서 끝이 제외됨에 따라 구간의 길이를 계산하는 방법도 명료해진다. last와 first를 단순히 뺄셈하기만 하면 구간에 포함된 요소의 개수가 나오며 first와 last가 같으면 구간의 길이는 0이다. 알고리즘 함수들은 최초 first != last를 점검하므로 구간 길이가 0이면 아무 것도 하지 않고 바로 리턴한다. 이런 여러 가지 논리적인 장점이 있기 때문에 구간을 표현할 때 끝점은 제외하는 규칙을 쓰는 것이다.

STL을 쓰는 동안 범위의 규칙을 항상 염두에 두어야 하는데 3번 요소부터 7번 요소까지 검색하고 싶다면 필요한 검색 구간은 3~8까지이다. 3~7까지 검색하면 7번 요소는 검색 대상에서 제외됨을 유의하도록 하자. 알고리즘은 항상 지정한 구간에서만 실행된다. 보통 begin ~ end까지 적용하는 경우가 많지만 원한다면 일부 구간에 대해서만 적용할 수도 있다. sort 예제를 다음과 같이 수정해 보자.

 

sort(vi.begin()+1,vi.end()-1);

 

다섯 개의 요소 중 중간의 세 요소만 정렬될 것이다. 정렬 결과는 2, 1, 5, 8, 9가 되며 가운데 8, 5, 1만 정렬되고 양쪽 끝의 2와 9는 정렬 대상에서 제외된다. 일부 구간에 대해서만 검색을 한다거나 뒤집기를 할 수도 있다.

반복자에 대해 마지막으로 주의해야 할 점은 STL 알고리즘은 반복자의 유효성을 전혀 점검하지 않으며 항상 유효하다고 가정한다는 점이다. 반복자가 틀린 위치를 가리키고 있을 경우의 결과는 정의되어 있지 않은데 재수 없으면 다운될 수도 있다. STL도 결국 범위를 점검하지 않는 C언어의 한계는 벗어나지 못했는데 그 이유는 물론 성능이다. 반복자를 참조할 때마다 범위를 일일이 점검하다가는 엄청난 희생을 감수해야 한다. 그러나 반복자는 보통 증가, 감소에 의해 구간 내에서만 움직이므로 큰 문제가 되지는 않는다.