[C++] 반복자 (Iterator)

 

 

 

C++ 반복자(Iterator)

 

C++ 라이브러리는 반복자를 제공하는데 이것을 사용하면 라이브러리의 방식대로 자료구조를 액세스 할 수 있다.

따라서 라이브러리가 효과적으로 동작한다는 것을 보장 할 수 있다는 장점이 있다.

 

즉, 포인터와 상당히 비슷하며, 컨테이너에 저장되어 있는 원소들을 참조할 때 사용한다.

 

추상적으로 말하자면, 반복자란 컨테이너에 저장되어 있는 모든 원소들을 전체적으로 훑어 나갈 때 사용하는, 일종의 포인터와 비슷한 객체라고 할 수 있다. 알고리즘 마다 각기 다른 방식으로 컨테이너를 훑어가기 때문에, 반복자에도 여러가지 종류가 있게 된다. 

 

 

 

반복자의 성질

 

- 컨테이너와 컨테이너 안의 있는 요소를 구별

- 요소의 값 확인

- 컨테이너 안에 있는 요소들 간에 이동할 수 있는 연산 제공

- 컨테이너가 효과적으로 처리할 수 있는 방식으로 가용한 연산들을 한정

 

 

 

반복자 구간(range)

 

구간이란 컨테이너에 담긴 값들의 시퀀스를 나타낸다. 구간은 반복자 한 쌍으로 나타내며, 이 반복자들이 각각 시퀀스의 시작과 끝을 가리킨다. 반복자는 특정 값을 지정하는데 사용될 수 있으며, 연속적인 메모리 영역을 두 개의 포인터로 나타내듯이 한 쌍의 반복자는 값들의 구간을 설정하는데 사용될 수 있다. 

 

그러나 반복자의 경우 설정되는 범위 내의 값들이 반드시 물리적으로 연속적이어야 할 필요가 없다 .단, 이 두개의 반복자가 같은 컨테이너로부터 생성된 것이어야 하며, 두번째 반복자는 첫번째 반복자 이후에 와야한다. 그리고 첫번째 반복자에서 두번째 반복자까지 차례로 컨테이너 내부의 원소들을 처리하게 되므로 논리적인 연속성을 지닐 수 있다. 

 

또한 반복자 2개를 사용하여 컨테이너의 특정 구간에 속한 원소들을 나타내고자 한다면, 두번째 반복자가 첫번째 반복자에 도달가능 해야한다. 

 

그리고, 포인터는 널(NULL) 값을 가질 수 있는데 이는 아무것도 가리키지 않는다는 의미이다. 반복자 또한 어떤 값도 가리키지 않는 반복자를 참조하는 것은 에러를 발생시킨다. 

 

 

 

* end() 함수는 끝이 아니다

 

컨테이너를 다룰 때 자주 쓰이는 end()라는 멤버함수는 컨테이너의 맨 마지막 원소를 가리키는게 아니다. end()가 가리키고 있는 것은 맨 마지막 원소의 바로 다음번 원소이다. 따라서 이러한 반복자를 past-the-end 반복자라고 부른다. (종점을 지나쳐버린 곳을 가리키는 반복자) 

 

end() 멤버 함수를 통해 얻어지는 반복자는 결과적으로 아무 의미가 없는 것을 가리키고 있는 것이며, 이 반복자가 가리키는 것을 참조하면 예상치 못한 오류가 발생하게 된다. 

 

또한 아무 원소도 없는 컨테이너의 begin()과 end()는 같다. 

 

 

 

반복자의 종류

 

 

- 입력 반복자(input iterator) :  읽기만 가능, 순방향 이동, 현 위치의 원소를 한 번만 읽을 수 있는 반복자

 

- 출력 반복자(output iterator) : 쓰기만 가능, 순방향 이동, 현 위치의 원소를 한 번만 쓸 수 있는 반복자 

 

- 순방향 반복자(forward iterator) : 읽기/쓰기 모두 가능, 순방향 이동(++)이 가능한 재할당될 수 있는 반복자

 

- 양방향 반복자(bidirectional iterator) : 읽기/쓰기 모두 가능, 순/역 방향 이동(--)이 가능한 반복자 

 

- 임의 접근 반복자(random access iterator) :  읽기/쓰기 모두 가능, 임의 접근, 

                                                      양방향 반복자 기능에 +, -, += , -=, [] 연산이 가능

 

 

 

모든 컨테이너는 양방향 반복자 이상을 제공한다.

 

배열 기반 컨테이너인 vector와 deque는 임의 접근 반복자를 제공한다.

 

 

반복자 종류	사용 방식	읽기	접근	쓰기	증감	비교
입력 반복자 (input iterator)	istream_iterator	=*p	->		++	== !=
출력 반복자 (output iterator)	ostream_iterator inserter front_inserter back_inserter			*p=	++
순방향 반복자 (forward iterator)		=*p	->	*p=	++	== !=
양방향 반복자 (bidirectional iterator)	list set 과 multiset map 과 multimap	=*p	->	*p=	++ --	== !=
임의접근 반복자 (random access iterator)	일반 포인터 vector deque	=*p	-> []	*p=	++ -- + - += -=	== != < > <= >=

 

 

추가적인 자료 : http://mayple.tistory.com/

 

 

 

 

 

 

반복자 개념을 포인터로 적용한 예제

 

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

 

#include <iostream>  using namespace std;  void main() {       int ari[]=;       int *it;       for (it=&ari[0];it!=&ari[5];it++) {              printf("%d\n",*it);       } } 

 

 

 

 

벡터를 이용한 반복자

 

 

정수형 벡터에 1부터 5까지 정수 값을 채워넣었다. 벡터의 한 요소를 가리키는 반복자는 다음과 같이 선언한다.

 

vector<T>::iterator it;

 

vector<T>가 클래스 이름이고 이 클래스 안에 iterator라는 타입이 typedef로 정의되어 있으므로 이 타입으로 변수를 하나 선언하면 벡터의 한 요소를 가리키는 반복자가 된다. for 루프에서는 반복자를 begin으로 초기화 하고 end 직전까지 반복자를 증가시키며 벡터의 매 요소를 순회하였다. 

 

#include <iostream>  #include <vector>  using namespace std;  void main() {       int ari[]=;       vector<int> vi(&ari[0],&ari[5]);       vector<int>::iterator it;       for (it=vi.begin();it!=vi.end();it++) {            printf("%d\n",*it);       } } 

 

 

 

 

 

 

 

리스트를 이용한 반복자

 

 

이는 위 예제의 vector를 list로 바꾸었다. 벡터와 순회하는 방법이 완전 동일하다. begin ~ end 사이를 반복자가 순회하여 *it 표현식으로 순회중의 요소를 액세스 할 수 있다. 

#include <iostream>  #include <list>  using namespace std;  void main() {       int ari[]=;       list<int> li(&ari[0],&ari[5]);             list<int>::iterator it;       for (it=li.begin();it!=li.end();it++) {            printf("%d\n",*it);       } } 

 

 

 

 

벡터와 리스트의 차이

 

 

반복자가 가리키는 요소를 삭제 할 경우 그 반복자는 무효화 된다. 

 

vector에 대해 erase를 호출하면 방금 삭제된 요소 다음에 있는 요소들을 가리키는 모든 반복자는 무효화 된다.

 

또한 push_back을 사용하여 vector에 요소를 추가해도 해당 vector를 가리키고 있던 모든 반복자는 무효화 된다. 

 

vector에 한 요소를 삭제하면 그 다음 요소들이 이동되고, 한 요소를 추가하면 새로운 요소를 위한 공간을 확보하기 위해 전체 vector가 재할당되기 때문이다.

 

하지만 list에서는 erase나 push_back이 다른 요소들에 대한 반복자를 무효화 시키지 않고 실제로 삭제된 요소를 가리키는 반복자만 무효화 된다. 왜냐하면 그 요소는 더 이상 존재하지 않기 때문이다. 

 

 

 

 

 

 

 

참고자료 1 : http://egloos.zum.com/printf/v/1824410

 

참고자료 2 : http://hyeonstorage.tistory.com/318

 

참고자료 3 : http://mayple.tistory.com

 

참고자료 4 : http://egloos.zum.com/lsrsp/v/13053