[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