[C++] Iterator에 대해서

반복자 iterator의 개념

반복자는 포인터와 상당히 비슷하다. 컨테이너에 저장되어 있는 원소들을 참조할 때 사용한다. 포인터와 비슷한 객체이다.
반복자는 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공한다.
반복자는 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 한다.
알고리즘마다 다른 방식으로 컨테이너를 순회할 수 있기 때문에 반복자에도 여러 종류가 있다.

An iterator is an object that can "iterate" (navigate) over elements.
- The C++ Standard Library

반복자는 컨테이너 내부의 원소(객체)를 가리키고 접근할 수 있어야 한다.
반복자는 다음 원소로 이동하고 컨테이너의 모든 원소를 순회할 수 있어야 한다.

---

반복자의 선언

반복자는 일반적으로 다음과 같이 선언한다.

containter:: iterator

컨테이너를 순회하기 위해서 공통적으로 begin()과 end() 함수를 가진다.
여기서 중요한 것은 begin()과 end()의 범위이다.
순차열의 시작은 begin() 끝은 end() 이다. end()는 실제 원소의 끝이 아닌 끝을 표시하는 원소이다.

다시말해, 컨테이너의 범위는 [ begin(), end )로 쓸 수 있다. 반 개방 범위로 본다.
시작은 포함하고, 끝은 포함하지 않는다.
배열 인덱스와 비슷하다. past-the-end 라고 부른다.
이러한 방식에는 두 가지 장점이 있다.

1. 원소를 순회하는 반복문을 간단히 할 수 있다. end()에 다다르지 않으면 계속해서 반복문이 동작한다.
2. 비어있는 범위에 대해 다른 코딩을 할 필요가 없다. 빈 컨테이너일 경우 begin()과 end()는 동일하다.

   bool empty(const STL_Container& container) 
   { 
   	return container.begin() == container.end(); 
   }​

1번의 이유로 반복문은 다음과 같이 작성할 수 있다.

for(iter = v.begin(); iter != v.end(); ++iter)

!= 연산을 사용하면 된다. 이 연산은 모든 컨테이너에서 사용할 수 있다.
random access 반복자인 경우 비교 연산 <, > 등을 할 수 있다.

 

반복문에서 반복자를 증가시킬 때 후위(postfix)보다는 전위연산자를 사용한다.
후위 연산자를 사용하면 반복자의 이전 값을 반환하기 때문에 임시로 객체가 생겨 성능이 늦어진다.
(클래스에서 증가연산자 overloading과 관련이 있다.)

구체적인 예는 아래와 같다.
vector의 반복자는 아래와 같이 선언한다.

vector<int>::iterator iter;

v.begin() : 컨테이너의 시작원소를 가리키는 반복자를 반환한다.
v.end() : 컨테이너의 끝 표시 반복자를 반환한다
++iter : 반복자를 다음 원소를 가리키도록 이동한다
*iter: iter가 가리키는 원소(객체)를 반환한다.
iter[3] : iter+3번째 원소(객체)를 반환한다.
iter += 2 : 현재 iter 위치에서 2개 뒤의 원소(객체)로 접근한다.

---

반복자의 종류

• 입력 반복자(input iterator) : 현 위치의 원소를 한 번만 읽을 수 있는 반복자 (istream)
• 출력 반복자(output iterator) : 현 위치의 원소를 한 번만 쓸 수 있는 반복자 (ostream)
• 순방향 반복자(forward iterator) : 입력, 출력 반복자 기능에 순방향으로 이동(++)이 가능한 재할당될 수 있는 반복자
• 양방향 반복자(bidirectional iterator) : 순방향 반복자 기능에 역방향으로 이동(--)이 가능한 반복자, !=, ==, ++, --연산 가능하다. (list, set, multiset, map, multimap)
• 임의 접근 반복자(random access iteraotr) : 양방향 반복자 기능에 +, -, ++, --, +=, -=, [], <, >, <=, >=, ==, != 연산이 가능한 반복자(vector, deque)

모든 컨테이너는 양방향 반복자 이상을 제공한다.
배열 기반 컨테이너인 vector와 deque는 임의 접근 반복자를 제공한다.

---

반복자 예제

#include <iostream>
#include <vector>

using namespace std;

int main()
{

    vector<int> v; // vector

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    vector<int>::iterator iter = v.begin(); // iterator

    cout << iter[3] << endl; // random access

    iter += 2;
    cout << *iter << endl; //

    // loop
    for(iter = v.begin(); iter != v.end(); ++iter) {
        cout << *iter << endl;
    }

    return 0;
}