39장 반복자

39-1 반복자의 정의

가. 반복자의 정의

반복자는 컨테이너의 한 지점을 가리키는 객체이다. 배열의 첨자나 연결 리스트의 노드 포인터도 이런 역할을 하지만 반복자는 기존의 포인터에 비해 훨씬 더 일반화된 개념이다. 컨테이너의 종류와 내부 구조에 상관없이 한 요소를 가리키는 목적으로 반복자라는 동일한 장치를 일관된 방법을 사용할 수 있다.

컨테이너에 대해 어떤 작업을 하고 싶다면 먼저 이 컨테이너에 저장되어 있는 요소에 접근해야 하므로 순회가 꼭 필요하다. 알고리즘이란 컨테이너 자체에 대해 적용되는 것이 아니라 결국은 컨테이너의 요소들에 적용되는 것이므로 요소를 읽고 쓸 수 있어야 하는데 이를 위해 반복자가 사용된다.

반복자를 관리하는 기본적은 방법은 ++, --, *, ==, >, < 등의 연산자이며 이 연산자들은 모든 반복자에 대해 동일한 의미를 가진다. 이처럼 반복자를 사용하는 방법이 일반화되어 있기 때문에 컨테이너의 내부 구조에 상관없이 동일한 방법으로 읽기, 이동, 대입, 비교가 가능하다. 알고리즘의 내부 코드는 컨테이너에 대해 전혀 모르며 컨테이너를 직접 다루지도 않고 오로지 반복자를 통해서만 컨테이너의 요소를 접근한다.

그래서 동일한 코드로 작성되어 있는 알고리즘을 여러 개의 컨테이너에 똑같이 적용할 수 있다. 예를 들어 find는 지정한 구간을 순서대로 순회하며 값을 검색하는데 벡터나 리스트의 내부 구조가 완전히 다르지만 반복자가 *연산자와 ++연산자, 비교 연산자 등만 잘 정의한다면 두 컨테이너를 동일한 방법으로 검색할 수 있는 것이다. 요소들이 어떤 모양을 가지든지 *연산자로 읽을 수 있고 요소들 간의 배치 관계에 상관없이 ++만 하면 다음 요소로 이동 가능하다.

영어 원문으로는 이터레이터(iterator)라고 하는데 흔히 반복자로 번역하여 사용되고 있다.

나. 반복자 구간

대개의 경우 두 개의 반복자로 표현되는 반복자 구간(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 <= range < last와 같이 표기할 수 있다.

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가 last가 아닌 동안 순회를 반복하며 last에 도달했을 때 루프를 탈출하므로 결국 last는 처리 대상에서 제외된다.

반복자는 대소 비교를 하지 않고 항상 부등 비교를 하는데 일반화된 반복자는 대소 비교가 가능하지 않기 때문이다. 리스트의 반복자는 메모리 여기저기에 흩어져 있는 노드의 포인터인데 앞쪽 노드가 반드시 앞쪽 번지에 있다고 보장할 수 없다. 그래서 부등 비교를 할 수밖에 없으며 또한 반복자는 절대 두 칸 이상 이동하지 않으므로 부등 비교를 해도 안전하다. 만약 last도 처리 대상에 포함된다면 루프는 좀 더 복잡해지고 에러 처리 방법이 묘연해진다.

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

{

for(;; ++first)

if(*first == val) return first;

if( first == last) break;

}

return ????;

}

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

STL을 쓰는 동안 범위의 규칙을 항상 염두에 두어야 하는데 3번 요소부터 7번 요소까지 검색하고 싶다면 필요한 검색 구간은 3~8까지이다. 보통 begin ~ end 까지 적용하는 경우가 많지만 원한다면 일부 구간에 대해서만 적용할 수도 있다.

반복자에 대해 마지막으로 주의해야 할 점은 STL 알고리즘은 반복자의 유효성을 전혀 점검하지 않으며 항상 유효하다고 가정한다는 점이다. 반복자가 틀린 위치를 가리키고 있을 경우의 결과는 정의되어 있지 않은데 재수 없으면 다운될 수도 있다.

39-2 반복자의 종류

가. 반복자의 기능

처리 대상을 지정하거나 검색 결과를 리턴하며 두 개씩 짝을 이루어 구간을 지정하기도 한다. 이외에 가리키는 요소를 읽어오는 *연산자, 앞뒤 요소로 이동할 수 있는 ++, --연산자를 제공하며 임의 위치로 이동하거나 반복자끼리 비교 및 대입도 가능하다.

그러나 모든 반복자가 이런 기능들을 한꺼번에 가지는 것은 아니며 어떤 연산이 제공되는가에 따라 다음과 같이 분류할 수 있다.

반복자	약어	설명
입력	InIt	오로지 입력만 가능하며 쓸 수는 없다
출력	OutIt	출력만 가능하며 읽지는 못한다
순방향	FwdIt	입출력이 모두 가능하다. 전진만 가능하다
양방향	BiIt	앞뒤로 이동할 수 있다. 감소 연산자를 정의한다
임의 접근	RanIt	임의의 요소를 참조할 수 있다.[ ] 연산자를 정의한다

STL이 반복자를 기능별로 분류하는 이유는 알고리즘의 적용 조건을 제한하기 위해서이다. 알고리즘은 내부 구현을 위해 반복자의 여러 기능을 활용하는데 어떤 기능이 사용되는가에 따라 요구되는 반복자가 다르다. 만약 해당 반복자가 알고리즘이 요구하는 기능을 제공하지 못한다면 이 반복자로는 그 알고리즘을 호출할 수 없다.

알고리즘 함수들은 모두 함수 템플릿으로 정의되어 있으며 반복자 타입을 템플릿 인수로 받아들인다. 각 알고리즘의 원형에는 반복자에 대한 최소한의 요구 사항이 명시되어 있으므로 원형을 보면 어떤 반복자가 필요한지 쉽게 알 수 있다.

나. 입력 및 출력 반복자

입력 반복자(Input Iterator)는 가장 기본적인 기능만 제공하는 반복자이다. 반복자이므로 컨테이너의 한 위치를 가리키는 것은 당연하고 반복자가 가리키는 위치의 요소를 *연산자로 읽을 수도 있다. 읽는 것만 가능하므로 *연산자를 사용하더라도 요소의 값을 변경하는 것은 불가능하다.

a = *it // 가능

*it = a // 불가능

전위형, 후위형의 ++ 연산자를 사용하여 다음 요소로 이동하는 기능도 가지고 있으며 같은 타입의 반복자와 상등 비교도 가능하다.

find 알고리즘이 요구하는 연산자가 바로 입력 반복자(InIt)인데 값을 읽기 위한 *연산자, 다음 요소로 이동하는 ++연산자, 그리고 끝낼 시점을 결정하기 위한 !=연산자밖에 없다.

검색이란 단순히 값을 읽기만 하는 동작이므로 요소의 값을 변경하는 기능은 필요치 않으며 순차 검색을 하므로 앞으로 전진하는 기능만 있으면 된다.

   

출력 반복자는 *연산자를 사용하여 요소의 내용을 변경할 수 있는 반복자이다. 쓰기만 가능하면 출력 반복자라고 할 수 있으며 읽기 기능이 필수는 아니다. 다음 요소로 이동하는 ++연산자도 지원해야 한다. 그러나 입력과는 달리 ==, != 연산자는 필수가 아니다, 즉 전진하면서 기록 가능하다는 조건만 만족하면 출력 반복자라고 할 수 있다.

*it = a; // 가능

a = *it; // 꼭 필요치 않음

반복자 구간끼리 복사하는 copy알고리즘에 입력, 출력 반복자가 동시에 나타난다.

OutIt copy(InIt first, InIt last, OutIt result)

{

while( first != last )

{

*result++=*first++;

}

return result;

}

이 함수는 first ~ last 구간을 result에 복사한다.

두 유형의 반복자는 입출력 스트림에만 적용된다. STL 컨테이너들은 모두 읽기, 쓰기가 동시에 가능하므로 이 두 유형보다 더 높은 레벨의 반복자를 지원한다. 입출력 스트림도 문자들의 집합이므로 일종의 컨테이너라고 할 수 있는데 키보드가 제공하는 반복자는 입력만 가능하다. 키보드로 들어오는 문자값은 읽을 수만 있을 뿐이지 쓰기는 가능하지도 않고 필요하지도 않다.

입력, 출력 반복자의 일종인 입출력 스트림 반복자는 콘솔에 연결된 반복자이다. 통산 표준 입출력 객체인 cin, cout에 대해 사용하지만 임의의 스트림 객체에 대한 반복자로도 사용할 수 있다. i(o)stream_iterator 클래스로 정의되어 있으며 이 반복자를 사용하면 표준 입력(키보드)으로 입력받은 내용을 순회하면서 읽어낼 수 있고 표준 출력(모니터)으로 문자를 출력할 수도 있다.

• 예제 ostream_iterator

#include <iostream> #include <list>     using namespace std;     void main() { int ari[] = { 1,2,3,4,5 }; list<int> li(&ari[0], &ari[5]);     ostream_iterator<int> oit(cout,","); copy( li.begin(), li.end(), oit); }

이 코드는 아마 *oit = *first로 되어 있을 텐데 출력 스트림에 반복자에 대한 = 연산이 cout << 연산으로 중복 정의되어 있어 화면으로 출력될 것이다.

입력 스트림 반복자를 사용하면 키보드로부터 특정 타입의 자료를 연속적으로 읽어 원하는 작업을 할 수 있다.

• 예제 istream_iterator

#include <iostream> #include <vector> #include <algorithm> using namespace std;     template<typename C> void dump(const char *dest, C c) { cout.width(12); cout << left << dest << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }     void main() { vector<int> vi(16); istream_iterator<int> iit(cin); copy( iit, istream_iterator<int>(), vi.begin()); dump("입력 후", vi); }

istream_iterator는 템플릿 인수로 입력받을 타입을 지정하며 생서자로는 입력 스트림 객체를 지정한다. 예제의 iit는 정수형을 cin으로부터 입력받는 객체로 선언되었다. istream_iterator의 디폴트 생성자는 스트림 끝을 나타내는 반복자를 반복자를 생성하는데 이 반복자는 키보드 입력 종료를 의미한다.

   

입출력 스트림 반복자에는 그 외에도 좀 더 저수준의 i(o)streambuf_iterator 클래스도 있는데 버펄르 직접 조작하며 문자 단위로 입출력을 수행하므로 성능이 훨씬 더 좋다. 이 클래스들도 나름대로 실용성이 있기는 하지만 어차피 콘솔 환경에서 프로그래밍하는 시대는 지났으며 iostream은 아직까지도 표준대로 구현되지 않은 컴파일러가 많아 이식성에도 불리하므로 애써 연구해볼 가치가 떨어진다.

다. 순방향, 양방향 반복자

순방향 반복자(Forward Iterator)는 입력 출력이 모두 가능한 반복자이다. 이름이 의미하듯이 순방향으로 이동가능하다는 조건이 있다. 순방향으로 이동한다는 것은 ++연산자를 정의한다는 뜻인데 전위형, 후위형 모두 정의되어 있으므로 ++it, it++ 두 형태를 자유롭게 사용할 수 있다.

반복자가 컨테이너 내의 요소 하나를 가리키고 있을 때 외부에서 특별한 조작을 하지 않으면 이 반복자는 그 요소를 계속 가리킨다. 그래서 반복자를 저장해 놓았다가 이 반복자가 가리키는 위치에서 언제든지 재순회가 가능하다.

순방향 반복자는 한 위치를 여러 번 읽고 쓸 수 있기 때문에 다중 패스 알고리즘을 지원한다. 다중 패스 알고리즘은 구현을 위해 컨테이너를 여러 번 스캔해야 하는데 대표적으로 부분 일치 구간을 검색하는 search알고리즘을 들 수 있다. search는 표준 strstr함수와 동작이 비슷한데 부분 일치 구간을 찾기 위해서는 검색 대상 구간과 완전히 일치하는 부분을 찾을 때까지 컨테이너의 각 요소들을 여러 번 읽어야 한다.

표준 STL에는 구현되어 있지 않지만 단순 연결 리스트(Single Linked List)를 가리키는 반복자가 대표적인 순방향 반복자이다.

양방향 반복자(Bidirectional Iterator)는 역방향으로도 이동이 가능한 반복자이다. 순방향 이동을 위한 ++연산자는 물론이고 역방향의 이동을 위한 --연산도 전위형, 후위형으로 각각 구현되어 있다. STL 컨테이너 중 이중 연결 리스트로 구현되어 있는 list가 양방향 반복자를 제공한다.

다음 두 알고리즘은 각각 순방향 반복자와 양방향 반복자를 요구한다.

void replace(FwdIt first, FwdIt last, const Type& Old, const Type& New);

void reverse( BiIt first, BiIt last);

replace는 컨테이너의 Old 값을 찾아 New값으로 교체한다. 읽기 쓰기가 모두 필요하다.

reverse는 구간 내의 요소들을 반대로 뒤집어 재배치하는데 읽기 쓰기가 모두 가능해야 하며 양쪽 끝에서 동시에 순횔르 시작하여 값을 교환해야 하므로 반복자가 증가, 감솔르 모두 지원해야 한다.

• 예제 fwditerator

#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, 70, 99, 64, 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는 전진 이동하며 읽고 쓰기만 반복하므로 순방향 반복자이면 충분하다.

reverse는 한쪽은 앞에서 뒤로, 한쪽은 뒤에서 앞으로 이동하면서 값을 교환(읽기+쓰기)해야 하므로 양방향으로 이동할 수 있어야 한다.

라. 임의 접근 반복자

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

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

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

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

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

임의 접근이 아닌 반복자로 +n 연산을 하거나 두 바복자의 거리를 구하고 싶다면 다음 두 함수를 사용한다.

void advance(InIt &first, int off);

int distance(InIt first, InIt last);

advance는 반복자를 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함수의 구현 코드이다.

void advance(InIt &first, Int off)

{

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

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

}

진짜 임의 접근이 가능한 반복자는 +n을 한 번에 수행할 수 있는데 비해 양방향 반복자는 off만큼 반복해야 하므로 수행 속도는 비교가 되지 않는다.

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

마. 반복자와 알고리즘

상위 반복자는 하위 반복자를 포함하므로 반복자끼리는 다음과 같은 계층을 구성한다.

양방향 반복자는 입력이나 순방향을 요구하는 알고리즘에 별 제약없이 사용할 수 있으며 임의 접근 반복자는 모든 알고리즘에 사용 가능하다. 그러나 역은 성립하지 않는다.

• 예제 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 함수는 정렬 구간의 길이를 구하기 위해 반복자 끼리 뺄셈을 하기도 하고 값을 비교 및 교환하기 위해 수시로 [ ]연산자를 사용하는데 양방향 반복자에는 이 연산들이 정의되어 있지 않으므로 에러로 처리된다.

바. 반복자의 속성

알고리즘 함수들은 임의의 컨테이너에 대해 동작하므로 반복자만 인수로 전달받을 뿐 컨테이너에 대해서는 알지 못한다. 하지만 때로는 반복자의 특성을 알면 좀 더 효율적으로 동작 가능한 경우가 많다. 여기서 반복자의 특성에는 순방향인지 임의접근인지 등을 지정하는 반복자의 레벨이 가장 중요하고 그외 반복자가 가리키는 타입, 반복자의 거리를 표현하는 타입 등 반복자와 관련된 타입 정보들이 포함된다.

STL은 반복자의 특징을 표현하기 위해 iterator_traits 클래스와 이 클래스를 보조하는 여러 가지 타입 정보를 정의한다. 이 정보는 내부적으로 사용되기 때문에 최종 사용자가 굳이 알아야 할 필요는 없지만 STL을 더 잘 이해하기 위한 방편으로 내부를 분석해보자.

tamplate<class Iter>

struct iterator_traits {

typedef typename Iter::iterator_category iterator_category;

typedef typename Iter::value_type value_type;

typedef typename Iter::difference_type difference_type;

typedef typename Iter::pointer pointer;

typedef typename Iter::reference reference;

};

iterator_category는 반복자의 종류를 지정하며, value_type은 반복자가 가리키는 대상체의 타입이고, difference_type은 반복자끼리의 거리를 표현하는 타입이다. 반복자 타입 Iter를 템플릿 인수로 전달하면 Iter 반복자가 정의한느 타입을 약속된 이름으로 재정의하는 역할을 할뿐이다. 반복자의 종류는 다음과 같이 태그 이름이 정의되어 있다.

struct input_iterator_tag {};

struct output_iterator_tag {};

struct forward_iterator_tag : public input_iterrator_tag {};

struct bidirectional_iterator_tag : public forward_iterator_tag {};

struct random_access_iterator_tag : public bidirectional_iterator_tag {};

자기네들끼리 일종의 상속 계층을 구성하고 있다.

어디까지나 개념적인 상속 관계를 의미하는 것이지 실제로 반복자들이 상속 계층을 구성하는 것은 아니다.

각 컨테이너별로 정의되어 있는 반복자 타입들은 iterator_traits 클래스가 요구하는 타입들을 개별적으로 정의한다. 컨테이너별로 반복자의 특징이 달라지므로 이 타입들은 매 컨테이너마다 달라질 것이다.

class vector_iterator {

typedef random_access_iterator_tag iterator_category;

typedef T vaule_type;

...

   

class list_iterator {

typedef bidirectional_iterator_tag iterator_category;

typedef T value_type;

...

각 반복자 클래스가 이렇게 자신의 정체와 자신과 관련된 타입을 약속된 이름으로 밝혀 놓으면 iterator_traits 클래스는 이 이름들을 외부에서 일관되게 사용할 수 있도록 제공한다. 예를 들어 벡터에 대한 반복자와 리스트에 대한 반복자가 있을 때 반복자를 iterator_traits의 인수로 전달되면 반복자에 대한 여러 가지 특징을 얻을 수 있다.

vector<int>::iterator vit;

list<int>::iterator lit;

iterator_traits<vit>::iterator_category; // 임의 접근이다.

iterator_traits<lit>::iterator_category; // 양방향이다.

iterator_traits<vit>::value_type; // 정수를 가리킨다.

이런 정보들을 사용하면 알고리즘을 반복자 종류에 맞게 최적화시킬 수 있다. distance 알고리즘의 경우 입력, 순방향, 양방향 반복자인 경우 다음과 같이 구해질 것이다.

template<class InIt>

void distance_impl(InIt first, InIt last, input_iterator_tag) {

int d = 0 ;

while( ; first != last ; ++first ) ++d;

return d;

}

임의 접근이 가능한 반복자인 경우 뒤쪽 반복자에서 앞쪽 반복자를 빼기만 하면 단 번에 거리를 구할 수 있다.

template<class RanIt>

void distance_impl(RnaIt first, RanIt last, random_access_iterator_tag) {

return last - first;

}

반복자의 종류에 따라 distance_impl이라는 이름으로 함수를 오버로딩해 놓았다. 하지만 실제 거리를 구하는 함수는 아니고 사용자가 아는 함수는 distance인데 이 함수는 다음과 같이 구현된다.

template<class Iter>

int distance(Iter first, Iter last) {

return distance_impl(first, last, iterator_traits<Iter>::iterator_categyr());

}

distance_impl이라는 함수를 호출하되 세 번째 인수로 반복자의 종류를 전달하는 것이다. 순방향이나 양방향에 대해서는 별도로 함수를 정의하지 않는데 이 부류의 태그가 입력 반복자 태그의 파생 클래스이므로 굳이 함수를 따로 정의할 피요가 없다. 부모는 자식을 대입받을 수도 있고 가리킬 수도 있다. 이런 문법적인 이점을 활용하기 위해 반복자 태그가 계층을 이루고 있는 것이다.

결국 반복자 태그라는 것은 어떤 유용한 정보를 담는 구조체가 아니라 단순히 타입만을 정의함으로써 오버로딩된 함수 중 적절한 함수를 선택하는 역할을 한다. 이 선택에 관여하는 클래스는 모두 빈 클래스이므로 단 1바이트도 불필요하게 사용되지 않았다. 뿐만 아니라 타입이란 컴파일 중에만 사용되는 정보이며 모든 선택은 컴파일 중에 일어나므로 실행시의 효율 감소도 전혀 없다.

distance가 리턴하는 타입을 int로 기술했지만 더 정확하게 표현하면 iterator_traits<Iter>::difference_type으로 해야 옳다. 또 각 반복자의 상수 버전에 대해, 요소의 포인터 버전에 대해서도 일일이 타입 정의를 해야 하며 컴파일러에 따라 이 클래스를 구현하는 방식도 천차만별이라 일반적인 분석을 하기는 어렵다.

39-3 그 외의 반복자

가. 삽입 반복자

보통의 반복자에 *연산자를 적용한 *it식을 대입문의 좌변에 놓으면 반복자가 가리키는 요소의 값이 대입문의 우변값으로 변경된다. 대입을 했으므로 원래의 값이 덮여서 사라진다. 반복자는 항상 덢어쓰기 모드로 동작하고 STL 알고리즘들도 항상 덮어쓰기를 한다.

• 예제 copyoverwrite

#include <iostream> #include <vector> #include <algorithm> using namespace std;     template<typename C> void dump(const char *dest, C c) { cout.width(12); cout << left << dest << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }     void main() { int ari[] = { 1,2,3,4,5 }; vector<int> vi( &ari[0], &ari[5] ); int ari2[] = { 6,7,8,9,10,11,12,13,14,15 };     vector<int>::iterator it; it = find(vi.begin(), vi.end(), 4); copy(&ari2[0], &ari2[10], it);     dump("복사 후", vi); }

반복자 it는 4를 검색한 결과를 대입받았으므로 4의 위치를 가리킬 것이다. 이 상태에서 it위치에 10개의 정수값을 복사했는데 실행해 보면 프로그램이 다운된다. copy함수는 it 반복자 이후가 원본 구간을 저장할 수 있을만한 충분한 공간이 확보되어 있다고 가정하고 동작하는데 크기 5의 벡터에 10개의 값을 집어넣고자 했으므로 벡터의 뒤쪽을 침범하게 되는 것이다.

모든 STL 함수는 동작하는데 필요한 공간이 항상 유효하다고 가정한다. 따라서 컨테이너를 변경하는 함수들은 항상 미리 용량을 확보한 상태에서 호출해야 한다.

일반 반복자가 덮어쓰기 모드로 동작하는데 비해 삽입 반복자(Insert Iterator)는 삽입 모드로 동작하는 반복자이다. *it식을 대입문의 좌변에 놓으면 반복자가 가리키는 위치의 메모리를 먼저 확보한 후 여기에 우변값을 삽입한다.

삽입되는 위치와 내부적으로 훛ㄹ되는 함수에 따라 다음 세 종류의 삽입 반복자가 제공된다.

• inser_iterator<Container> : insert 멤버 함수를 사용하여 중간에 삽입한다. 모든 컨테이너와 함께 사용할 수 있다. 생성자의 인수로 컨테이너와 삽입 위치를 지정하는 반복자를 전달한다.
• front_insert_iterator<Container> : push_front 멤버 함수를 사용하여 선두에 삽입한다. 리스트와 데크 컨테이너에 사용할 수 있으며 벡터에는 사용할 수 없다.
• back_insert_iterator<Container> : push_back 멤버 함수를 사용하여 끝에 추가한다. 모든 컨테이너와 함께 사용할 수 있다.

삽입 반복자에 의해 호출되는 멤버 함수들이 컨테이너의 크기를 자동으로 관리하므로 컨테이너는 필요한 만큼 알아서 늘어난다. *it = value; 식으로 대입만 하면 가리키는 위치에 삽입되고 메모리도 자동으로 관리되므로 개수를 미리 알 수 없는 삽입 동작도 안심하고 수행하 ㄹ수 있으며 컨테이너의 크기를 미리 확장해 놓을 필요도 없다.

이런 동작이 가능한 이유는 삽입 반복자가 자신이 가리키는 컨테이너의 종류를 정확하게 알고 있기 때문이다. 삽입 반복자는 생성할 때부터 템플릿 인수를 통해 대상 컨테이너를 전달받으므로 멤버 함수를 통해 직접적으로 조작할 수 있는 것이다.

• 예제 vectorinsert

#include <iostream> #include <vector> #include <algorithm> using namespace std;     template<typename C> void dump(const char *dest, C c) { cout.width(12); cout << left << dest << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }     void main() { int ari[] = { 1,2,3,4,5 }; vector<int> vi( &ari[0], &ari[5] );     dump("원본", vi); insert_iterator<vector<int>> insit(vi, vi.begin()+2);     *insit = 99; *insit = 100; dump("삽입 후", vi); }

삽입 반복자의 =연산자가 insert멤버 함수를 호출하도록 정의되어 있으므로 *insit에 대한 대입 동작에 의해 우변값이 삽입된다. 이때 만약 메모리가 부족하다면 재할당되며 반복자는 다으므 위치로 옮겨진다. 매 호출마다 메모리가 재할당될 수도 있으므로 이럴 때는 벡터의 용량을 확보해 놓고 삽입 반복자를 사용하는 것이 좋다.

삽입 반복자를 선언하는 문장이 다소 길어 외워서 쓰기에는 불편한 면이 있는데 그래서 삽입 반복자를 생성하여 리턴하는 템플릿 함수들이 정의되어 있다.

insert_iterator<Container> inserter(Container& Cont, Iterator It);

front_insert_iterator<Container> front_inserter(Container& Cont);

back_insert_iterator<Container> back_inserter(Container& Cont);

삽입 반복자를 알고리즘 함수와 함께 사용하면 알고리즘의 대입 동작을 삽입으로 바꿀수 있다. 아록리즘 함수의 본체에서는 *it=value 식으로 대입만 하도록 되어 있지만 반복자의 = 연산자가 삽입으로 재정의되어 있기 때문이다. 그래서 알고리즘의 기본 동작에 변형을 쉽게 가할 수 있다. copyoverwrite 예제를 다음과 같이 수정하면 제대로 동작한다.

insert_iterator<vector<int>> insit(vi.find(vi.begin(), vi.end(), 4));

copy(&ari2[0], &ari2[10], insit);

위의 명령을 아래처럼 사용할 수도 있다.

copy(&ari2[0], &ari2[10], inserter(vi.find(vi.begin(), vi.end(), 4)));

copy는 지정한 구간을 반복자가 지정한 위치에 대입하여 무조건 덮어쓰도록 정의되어 있지만 삽입 반복자에 의해 대입 연산이 재정의되기 때문에 구간을 삽입하는 용도로도 사용할 수 있다.

다음 예제는 배열을 리스트로 복사하되 전방 삽입 반복자를 사용하여 리스트의 앞쪽에 순서대로 삽입하여 역순으로 복사한다.

• 예제 revcopy

#include <iostream> #include <list> using namespace std;     void main() { int ari[] = {1,2,3,4,5}; list<int> li;     copy(&ari[0], &ari[5], front_inserter(li)); copy(li.begin(), li.end(), ostream_iterator<int>(cout, " ")); cout << endl; }

전방 삽입 반복자는 대입 연산자를 push_front 멤버 함수 호출로 정의하므로 배열 요소가 리스트에 반대 순서로 배치된다.

나. 상수 반복자

안전한 참조를 위해 포인터나 레퍼런스에 상수성을 줄 수 있듯이 반복자도 상수성을 가질 수 있다. 비상수 반복자는 레퍼런스를 리턴하므로 *연산자와 함께 대입식의 좌변에 사용할 수 있지만 상수 반복자는 상수 레퍼런스를 리턴하므로 대입식의 좌변에 놓아 값을 변경할 수 없고 오로지 읽을 수만 있다.

상수 반복자는 const_iterator타입으로 정의되어 있다. 상수 반복자가 가리키는 대상이 상수이지 반복자 그 자체가 상수인 것은 아니므로 전후로 이동하여 다른 요소를 가리키는 것은 가능하다.

컨테이너의 begin, end멤버 함수는 상수, 비상수 버전으로 중복 정의되어 있고 컨테이너가 상수일 때는 상수 반복자를 리턴한다.

상수 컨테이너를 인수로 받는 함수가 존재할 수 있으며 전달받은 컨테이너가 이 함수 내에서는 임시적으로 상수성을 가지게 된다. 상수 컨테이너를 액세스할 때는 상수 반복자만 사용할 수 있다.

• 예제 constiterator

#include <iostream> #include <vector> #include <algorithm> using namespace std;     int vectorsum(const vector<int> &cvt) { vector<int>::const_iterator cit; int sum = 0;     for( cit = cvt.begin() ; cit != cvt.end() ; cit++ ) { sum+= *cit; }     // *cit = 1234 ; // 에러 : 상수 반복자가 가리키는 곳에 대입 return sum; }     void main() { int ari[] = {80, 98, 75, 60, 100}; vector<int> vi(&ari[0], &ari[5]);     int sum; sum = vectorsum(vi); printf("총 합 = %d\n", sum); }

요소들의 합계를 구하기 위해서는 벡터의 요소들을 순서대로 읽기만 하며 쓰는 동작은 전혀 필요없으므로 대상 벡터를 상수 레퍼런스로 전달받았다. 이 컨테이너의 요소를 순회하기 위해서는 상수 반복자만 사용할 수 있다.

루프 내부에서 *cit로 벡터의 요소를 순서대로 읽어 sum에 누적하는데 읽는 것은 얼마든지 가능하다. 루프의 증감문에서는 cit++로 반복자를 다음 위치로 이동시키는데 반복자 자체는 상수가 아니므로 다른 위치로 이동할 수 있다. 그러나 *cit에 어떤 값을 대입하면 에러로 처리되는데 cit가 리턴하는 레퍼런스가 상수이기 때문이다.

상수 컨테이너에 대해서는 상수 함수만 호출할 수 있다. insert, erase멤버처럼 컨테이너에 요소를 삽입, 삭제하는 함수는 컨테이너를 변경시키므로 상수 컨테이너로는 호출할 수 없다.

나. 역방향 반복자

역방향 반복자는 순회 방향이 거꾸로 되어 있는 반복자이다. 양방향 반복자나 임의 접근 반복자에 어댑터를 적용하여 구현되며 ++, --연산이 반대 방향으로 정의되어 있다. 각 컨테이너는 다음 두 개의 역방향 반복자 타입을 제공하므로 이 타입의 반복자를 선언하기만 하면된다.

reverse_iterator

const_reverse_iterator

컨테이너로부터 역방향 반복자를 얻을 때는 rbegin, rend 멤버함수를 사용한다. 역방향 반복자로 컨테이너를 순회하면 끝에서부터 앞쪽으로 순회할 수 있다.

• 예제 revit

#include <iostream> #include <vector> using namespace std;     void main() { int ari[] = {1,2,3,4,5}; vector<int> vi(&ari[0], &ari[5]); vector<int>::reverse_iterator rit;     for( rit = vi.rbegin() ; rit != vi.rend() ; rit++ ) { printf("%d\n", *rit); } }

역방향 반복자를 알고리즘으로 전달하면 ++연산의 의미가 바뀌므로 알고리즘의 순회 방향을 변경할 수 있다.

• 예제 revfind

#include <iostream> #include <vector> #include <algorithm> using namespace std;     void main() { int ari[] = {6,2,9,2,7}; vector<int> vi( &ari[0], &ari[5] );     puts(find(vi.begin(), vi.end(),2) == vi.end() ? "없다." : "있다"); puts(find(vi.rbegin(), vi.rend(), 2) == vi.rend() ? "없다" : "있다"); }

이 경우 둘 다 2의 값을 가지지만 위치에 따라 요소의 의미가 달라질 수도 있다. 어떤 요소가 끝에서 어디쯤에 있는지를 검색하고 싶을 때 역방향 반복자를 사용한다.

역방향 반복자에는 원래의 순방향 반복자를 리턴하는 base멤버 함수가 정의되어 있다. 삽입, 삭제 함수들은 역방향 반복자를 받아들이지 않기 때문에 역방향 검색한 위치에 대고 어떤 작업을 하고 싶을 때는 순방향 반복자로 바꾸어야 한다. 또한 역방향 검색 후에 다시 순방향으로 검색하고 싶을 때 base로 언제든지 순방향 반복자를 구할 수 있다. base로 구한 순방향 반복자는 역방향 반복자보다 항상 하나 큰 값을 가진다.

이렇게 되어 있는 이유는 순방향 반복자가 역방향 반복자보다 한 칸 더 오른쪽에 있으며 이렇게 해야 rbegin의 base가 end가 되기 때문이다.

• 예제 revbase

#include <iostream> #include <vector> #include <algorithm> using namespace std;     void main() { const char* str = "C++ standard template libray"; vector<char> vc(&str[0], &str[strlen(str)]);     vector<char>::reverse_iterator rit; vector<char>::iterator bit, it; rit = find(vc.rbegin(), vc.rend(), 't'); bit = rit.base(); it = find(bit, vc.end(), 'a');     if ( it != vc.end() ) { printf("검색 결과 = %c\n", *it); } }