37-2-나.반복자

C언어의 가장 핵심적인 문법이 무엇이냐는 질문을 받는다면 누구나 주저없이 포인터를 선택할 것이다. 다소 난해하고 문제점도 많기는 하지만 C언어를 강력한 언어로 만드는 일등 공신이기 때문이다. 같은 방식으로 STL의 가장 핵심 요소가 무엇이냐고 묻는다면 반복자라고 대답할 수 있다. 반복자는 포인터와 하는 역할이나 사용 방법이 비슷하되 훨씬 더 일반화되어 있어 임의의 컨테이너와 함께 사용할 수 있다. STL의 일반성은 반복자를 통해 확보된다.

반복자의 정의를 내리기 전에 컨테이너를 순회하는 방법을 먼저 연구해 보자. 컨테이너는 복수 개의 자료를 저장하는 집합소이므로 컨테이너에 대해 출력, 검색, 정렬, 대체 등의 연산을 하려면 먼저 각 요소를 순서대로 액세스하는 순회가 필요하다. 컨테이너에서 한 요소를 검색하려면 찾는 요소가 어디쯤 있는지 알기 위해 순서대로 읽으면서 비교해야 하며 정렬이나 병합 등은 더 복잡한 순회를 해야 한다.

컨테이너에 가해질 수 있는 여러 가지 연산 중 가장 기초적이고 간단한 출력 연산을 구현한다고 해 보자. 배열의 각 요소를 출력하려면 일단 요소들을 모두 방문하면서 그 값을 읽어야 한다. 요소들을 순서대로 방문하는 것이 곧 순회이다. 크기 num의 배열을 출력하는 코드는 다음과 같이 작성할 수 있다.

void Print(int *ar,int num)

{

int i;

for (i=0;i<num;i++) {

printf("%d\n",ar[i]);

}

}

배열은 임의 접근이 가능하므로 0부터 배열의 크기 직전까지 첨자를 증가시키면서 [ ] 연산자로 첨자 위치의 요소를 출력하면 된다. for 문이 배열 전체를 훑으면서 각 요소를 순회하는 과정에서 printf로 요소값을 출력했다. 배열과 for문을 안다면 아주 쉽게 이해되는 코드이다. 연결 리스트의 경우도 순회를 해야 노드들을 출력할 수 있는데 순회 방법이 배열과 상당히 다르다.

void Print(Node *head)

{

Node *Now;

for (Now=head->next;Now!=tail;Now=Now->next) {

printf("%d\n",Now->value);

}

}

첨자 연산이 지원되는 배열은 첨자를 증가시키면 되지만 연결 리스트는 노드들이 메모리의 여기 저기에 링크로 연결되어 있으므로 링크를 쫓아 다녀야 모든 노드를 순회할 수 있다. 노드를 가리키는 포인터 Now를 선언하고 최초 head에서 시작하여 다음 노드를 검색하기를 tail에 이를 때까지 반복하면서 Now가 가리키는 노드의 값을 출력하였다.

배열과 연결 리스트는 논리적으로 유사한 컨테이너임에도 물리적인 자료 구조가 틀리므로 순회하는 방법이 아주 다르다. 그렇다면 다른 컨테이너의 경우는 어떨까? 아마 내부 구조가 다르기 때문에 컨테이너별로 순회를 하는 방법이 제각각일 것이다. 순회 방법이 이처럼 틀려지면 똑같은 작업을 하는 함수라도 하나로 통합할 수가 없다. 위 예의 Print 함수도 for루프 안쪽의 코드, 즉 순회 중에 할 작업은 동일한데 순회 방법이 틀려 두 Print 함수가 각각 필요하다.

지원하는 컨테이너의 종류가 C개이고 구현하고 싶은 알고리즘이 A개일 때 모든 컨테이너에 대해 알고리즘 함수를 일일이 만들어야 하므로 결국 C*A개의 함수를 각각 따로 만들어야 한다. 순회 방법이 다를 뿐이지 알고리즘 구현 코드는 유사하므로 아마 이 함수들의 코드는 대부분 중복될 것이다. 어떻게 하든 순회 방법을 일반화시켜 내부 구조에 상관없이 동일한 방법으로 순회할 수 있다면 알고리즘의 일반성이 확보되어 모든 컨테이너에 쓸 수 있는 범용 알고리즘을 만들 수 있을 것이다.

순회 방법을 일반화하기 위해 STL에서 사용하는 개념이 바로 반복자이다. 어떤 경우에는 포인터가 되기도 하고 어떤 경우에는 첨자가 되기도 하며 또 어떤 경우에는 다소 복잡한 객체가 요구되기도 한다. 반복자는 다음과 같은 기능을 가지는데 종류에 따라서는 일부 기능이 제외되기도 한다.

① 컨테이너의 요소 하나를 가리키는 기본적인 역할을 한다.

② 가리키는 지점의 요소를 읽고 쓸 수 있다. 내용을 읽는 * 연산자가 정의된다.

③ 증감에 의해 주변 요소로 이동할 수 있다. ++, -- 등의 연산자가 정의된다.

④ 반복자끼리 대입, 비교 가능해야 한다. 대입, 비교 연산자가 정의된다.

포인터는 위 4가지 기능을 모두 가지므로 그 자체로 완벽한 반복자이며 따라서 모든 STL 알고리즘에 포인터를 사용할 수 있다. 컨테이너별로 요소를 가리키는 방법은 각기 다르지만 반복자라는 개념을 사용하면 위의 요구 사항을 만족하는 객체를 정의할 수 있다. 아무튼 반복자를 사용하면 C의 포인터가 하는 동작을 일반화할 수 있으며 그래서 반복자를 포인터의 일반화라고 한다. 반복자는 포인터를 그대로 흉내내므로 임의의 컨테이너에 저장된 모든 요소를 순서대로 가리킬 수 있다.

모든 컨테이너는 시작점과 끝다음점을 조사하는 begin, end 멤버 함수를 제공한다. 끝 다음점이란 범위의 경계를 넘어선 지점을 의미하는데 begin에서 시작하여 이 지점 직전까지 순회하면 모든 요소를 차례대로 방문할 수 있다. 끝다음점의 개념과 효용성에 대해서는 다음 장에서 좀 더 상세하게 다루기로 한다.

반복자와 컨테이너의 begin, end 함수를 사용하면 모든 컨테이너를 동일한 방법으로 순회할 수 있다. 앞에서 만들었던 배열 출력 예제를 반복자를 사용하여 다시 작성해 보면 다음과 같아진다. C의 정적 배열은 동일 타입의 변수 집합이므로 그 자체로 이미 컨테이너라고 할 수 있다.

예 제 : iterarray

#include <iostream>

using namespace std;

void main()

{

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

int *it;

for (it=&ari[0];it!=&ari[5];it++) {

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

}

}

정수형 배열을 가리키는 포인터 it를 선언하고 배열 첫 번째 요소의 번지에서 시작하여 끝다음점 요소 직전까지 순회하면서 *it를 출력하면 배열 요소 전체가 출력된다. 여기서 사용된 it 포인터는 배열의 한 요소를 가리키며 증가하고 비교되며 *연산자로 요소를 읽기도 하므로 반복자의 요구 조건을 모두 만족한다. 다음은 벡터에 대해 반복자를 적용해 보자.

예 제 : itervector

#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>::iterator it;

for (it=vi.begin();it!=vi.end();it++) {

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

}

}

정수형 벡터에 1~5까지의 정수값을 채워 넣었다. 벡터는 다른 컨테이너의 요소들로 자신을 초기화하는 생성자를 제공하는데 이 생성자의 문법은 다음에 배우기로 하자. 정수형 벡터 vi에는 다섯 개의 정수가 삽입되며 크기는 5이다. 벡터의 한 요소를 가리키는 반복자는 다음과 같이 선언한다.

vector<T>::iterator it;

vector<T>가 클래스 이름이고 이 클래스안에 iterator라는 타입이 typedef로 정의되어 있으므로 이 타입으로 변수를 하나 선언하면 벡터의 한 요소를 가리키는 반복자가 된다. for 루프에서는 반복자를 begin으로 초기화하고 end 직전까지 반복자를 증가시키며 벡터의 매 요소를 순회하였다. 다음은 연결 리스트의 경우를 보자. 위 예제의 vector를 list로 바꾸고 (꼭 필요하지는 않지만)객체의 이름을 vi에서 li로 바꾸기만 하면 된다.

예 제 : iterlist

#include <iostream>

#include <list>

using namespace std;

void main()

{

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

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

list<int>::iterator it;

for (it=li.begin();it!=li.end();it++) {

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

}

}

보다시피 벡터와 순회 방법이 완전히 동일하다. begin ~ end 사이를 반복자가 순회하여 *it 표현식으로 순회중의 요소를 액세스할 수 있는 것이다. 벡터나 리스트 외의 다른 컨테이너들도 순회하는 방법은 동일하다. 각 컨테이너의 내부 구조는 상당히 다르지만 반복자를 사용하면 똑같은 방법으로 순회할 수 있다.

반복자는 컨테이너를 순회하는 방법과 컨테이너의 한 요소를 참조하는 방법을 획일화함으로써 알고리즘들이 컨테이너의 내부 구조에 대해 독립성을 가지도록 한다. 순회 방법이 일정하다면 하나의 함수로 임의의 컨테이너를 지원하는 알고리즘을 구현할 수 있다. 이게 과연 가능한지 앞서 예를 든 Print 함수를 일반적인 알고리즘으로 구현해 보자.

예 제 : itergeneric

#include <iostream>

#include <vector>

#include <list>

using namespace std;

template<typename IT>

void Print(IT s, IT e)

{

IT it;

for (it=s;it!=e;it++) {

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

}

}

void main()

{

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

vector<int> vi(&ari[0],&ari[5]);

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

Print(&ari[0],&ari[5]);

Print(vi.begin(),vi.end());

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

}

Print는 반복자 타입을 인수로 받아들이는 함수 템플릿으로 정의되어 있어 임의의 반복자 타입으로 구체화될 수 있다. Print의 본체는 IT 타입의 지역변수 it를 선언하고 인수로 전달된 범위 s~e사이를 순회하며 *it로 반복자가 가리키는 값을 읽어 출력했다. main에서는 정적 배열, 벡터, 리스트 세 컨테이너에 대해 Print 함수를 호출하여 컨테이너 전체를 출력한다. 실행해 보면 1~5까지의 숫자가 세 번 출력될 것이다.

컨테이너를 출력하는 Print 정도의 간단한 함수 따위는 직접 만들어 쓰나 일반화시키나 별 감흥이 없겠지만 이보다 훨씬 더 복잡한 동작을 하는 정렬, 병합 등의 알고리즘을 딱 하나만 만들어 놓고 두루 두루 쓸 수 있다면 멋지다는 생각이 들 것이다. 이 예제를 보면 STL이 강조하는 일반화란 무엇인지 어렴풋이 감이 올 것이다.

반복자는 컨테이너를 다루는 기본적인 방법이다. 컨테이너에 요소를 삽입, 삭제할 때 또는 검색한 결과를 리턴할 때 반복자가 필요하다. STL의 모든 함수들은 컨테이너내의 위치를 칭할 때 반복자를 사용하며 검색 결과를 보고할 때도 반복자를 사용한다. 반복자는 임의의 컨테이너와 알고리즘이 서로를 몰라도 같이 동작할 수 있도록 이어주는 매개체 역할을 한다.

여기서는 반복자의 개념만 직감적으로 이해하기로 한다. 반복자라는 용어의 정확한 의미와 끝다음점의 개념, 왜 반복자끼리 비교할 때 != 연산으로 비교를 하는지 등에 대해서는 다음 장에서 좀 더 상세하게 다루기로 하자.