39-2-라.임의 접근 반복자

임의 접근 반복자(Random Iterator)는 최상위 레벨의 반복자이며 제공하는 기능이 가장 많다. 양방향 반복자의 모든 기능을 포함하므로 * 연산자로 읽기, 쓰기와 ++, -- 연산자로 앞 뒤로 이동하기, 같은 위치를 여러 번 액세스 하기 기능을 제공한다. 여기에 임의 위치로 이동할 수 있는 기능이 추가로 제공되는데 거리에 상관없이 항상 상수 시간내에 이동 가능하다.

양방향 반복자는 ++, -- 가 가능하지만 항상 한칸씩만 앞 뒤로 이동할 수 있는 것과 비교된다. 임의 위치로 곧장 이동할 수 있다는 것은 반복자에 임의의 정수를 더하는 +n 연산을 제공한다는 뜻이다. 포인터에 +n 연산을 적용하면 n*sizeof(타입) 만큼 즉시 이동하는데 임의 접근 연산자가 바로 이 기능을 제공하며 +n에 의해 현재 위치에서 n만큼 떨어진 요소로 곧장 이동할 수 있다.

+n 연산이 가능하면 추가로 가능해지는 연산이 여러 개 생긴다. -n은 음수를 더하는 것과 같으므로 당연히 가능하며 [ ] 연산자는 *와 +n연산의 조합인 *(it+n) 연산이므로 역시 지원된다. [ ] 연산자를 사용하면 지정한 임의의 위치값을 바로 읽고 쓸 수도 있다. 또한 복합 대입 연산자 +=, -=도 지원되는데 모두 +n으로부터 파생되는 연산들이다.

임의 접근 반복자가 +n을 지원할 수 있는 이유는 컨테이너의 요소들이 배열처럼 인접하게 배치되어 있기 때문이다. 요소의 크기가 일정하고 서로 이웃해 있으므로 이동하고 싶은 거리에 요소 크기를 곱한만큼 더하기만 하면 즉시 이동 가능하다. 배열을 가리키는 포인터를 생각해 보면 쉽게 이해할 수 있다.

같은 배열내의 임의 접근 반복자끼리는 뺄셈도 가능하다. 두 반복자 사이에 있는 요소들이 같은 크기로 모여 있으므로 뺄셈 결과는 구간내의 요소 개수를 나타내는 정수값이다. 또한 요소들이 선형적으로 배치되어 있으므로 반복자끼리 대소 비교도 가능하다. 번지값이 큰 반복자가 항상 더 뒤쪽에 있으므로 대소 비교에 의해 반복자의 전후를 명확하게 알 수 있다.

링크에 의해 연결되어 있는 list 컨테이너는 임의 접근이 불가능하므로 양방향 반복자를 제공한다. 연결 리스트의 노드들이 인접해 있지 않고 메모리 여기 저기에 흩어져 있으므로 +n 연산이 불가능하며 링크를 따라 한칸씩 점진적으로 이동할 수밖에 없다. 또한 반복자의 번지만으로 전후를 판별할 수 없으므로 대소 비교도 불가능하며 반복자끼리 뺄셈을 통해 구간의 요소 개수를 구할 수도 없다. 임의 접근이 아닌 반복자로 +n 연산을 하거나 두 반복자의 거리를 구하고 싶다면 다음 두 함수를 사용한다.

void advance(InIt &first, int off);

int distance(InIt first, InIt last);

advance는 반복자를 off만큼 뒤쪽으로 이동시키는데 off가 음수일 수도 있으므로 앞쪽으로도 이동할 수 있다. 이 함수를 사용하면 입력 반복자(따라서 순방향, 양방향도)에 +n 연산이 가능해진다. distance는 두 반복자 사이의 거리를 구하여 정수값을 리턴한다. 예제를 통해 두 함수를 간단히 테스트해 보자. 소스에서 주석 처리되어 있는 줄은 에러가 발생하는 부분이다.

예 제 : advance

#include <iostream>

#include <list>

using namespace std;

void main()

{

int ari[]={1,2,3,4,5,6,7};

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

list<int>::iterator it=li.begin();

printf("%d\n",*it); // 읽을 수 있다.

printf("%d\n",*(++it)); // 한칸 전진 가능

// printf("%d\n",it[3]); // 에러:임의 위치를 읽지는 못함

// it+=3; // 에러:임의 위치로 이동하지 못함

advance(it,3); // advance로 이동 가능

printf("%d\n",*it);

// printf("거리=%d\n",li.end()-li.begin()); // 에러:반복자끼리 뺄셈은 안됨

printf("거리=%d\n",distance(li.begin(),li.end())); // distance로 거리를 구하는 것은 가능

}

리스트 컨테이너가 제공하는 양방향 반복자는 +n을 지원하지 않으므로 [ ] 연산자로 임의 위치를 읽거나 +=n으로 임의 위치로 이동할 수 없으며 반복자끼리 뺄셈을 할 수도 없다. 그러나 advance와 distance 함수를 사용하면 가능하기는 하다. 실행 결과는 다음과 같다.

1

2

5

거리=7

이 결과를 보면 양방향 반복자도 임의 접근이 가능한 것처럼 보이며 실제로 가능하기도 하다. 그러나 속을 들여다 보면 엄청난 꽁수가 숨어 있음을 발견할 수 있다. 다음은 advance 함수의 구현 코드인데 어떻게 +n 연산을 수행하는지 보자.

void advance(InIt &first, int off)

{

for (;off > 0;--off) { ++first; }

for (;off < 0;++off) { --first; }

}

off의 부호에 따라 두 루프 중 하나를 실행하는데 양수인 경우만 보면 off를 계속 감소시키면서 first 반복자를 계속 증가시킨다. 결국 ++first를 off만큼 반복함으로써 first를 off만큼 뒤쪽으로 이동시키는 것이다. 리스트의 반복자에 이 함수를 적용하면 링크를 따라 다음 노드로 이동하기를 off만큼 반복하는 단순 무식한 짓을 하게 된다.

진짜 임의 접근이 가능한 반복자는 +n을 한 번에 수행할 수 있는데 비해 양방향 반복자는 off만큼 반복해야 하므로 수행 속도는 감히 비교가 되지 않는다. 임의 접근 반복자는 it[30000]을 한 번에 바로 찾아 가지만 양방향 반복자는 다음 링크 찾아 3만리를 가야 하므로 진정한 의미의 +n 연산을 지원한다고 볼 수 없다. advance와 distance는 꼭 필요할 경우에 사용할 수는 있지만 n이 커지면 효율이 떨어진다는 점을 알아야 한다.

이런 의미에서 볼 때 임의 접근 반복자는 단순히 임의 접근이 가능하다는 정도로 정의하는 것보다 상수 시간내에 원하는 곳으로 즉시 이동할 수 있는 반복자로 정의하는 것이 옳다. 요소들이 인접해 있는 벡터는 임의 접근 반복자를 제공하며 정적 배열의 위치를 가지는 포인터도 완벽한 임의 접근 반복자이다.

임의 접근 반복자는 가장 기능이 많은 최상위의 반복자이며 모든 반복자의 기능을 다 포함한다. 그래서 STL의 모든 알고리즘과 함께 사용할 수 있다. 반면 임의 접근 반복자를 요구하는 알고리즘은 임의 접근 반복자만 사용할 수 있다. 대표적으로 sort가 있는데 효율적인 정렬을 위해서는 요소끼리 비교, 교환을 많이 해야 하며 이때 빠른 속도로 요소 사이를 이동할 수 있어야 한다. 또한 이분 검색을 하는 binary_search알고리즘도 임의 접근 반복자를 요구한다.