1.1절. Iterator 이란

우리나라 말로 하면 "반복자", "순환자" 정도가 될것이다. 그런데 굳이 번역된 말에 신경쓸필요 없이 C에서 사용되는 포인터 라고 생각하는게 가장 이해하기 쉬울듯하다. 다른말로 pointer 를 객체등에 유연하게 사용할수 있도록 일반화 시킨 버젼 이라고 할수 있다. 포인터와 마찬가지로 iterator 를 증가시키거나 감소 시킴으로써 객체간을 이동할수 있다.

iterator 는 자료형에 대한 정보를 가지고 있으며, 이러한 정보에 어떻게 접근해야 하는지에 대한 정보를 가지고 있다. 포인터가 자료에 접근하기 위해서 주소정보를 가지고 있는것과 비슷한데, iterator 는 객체에 접근하기위한 정보를 가지고 있는 또다른 객체이다.

iterator 는 일반화(generic) 프로그래밍을 하는데 있어서 가장 핵심이 되는 요소중 하나로써, 컨테이너와 알고리즘 사이에서 서로를 연결 시켜주는 인터페이스(가교) 역활을 한다(보통 알고리즘은 iterator 를 아규먼트로 받아들인다). 이렇듯 알고리즘들이 iterator 를 받아 들임으로써 많은 종류의 다른 컨테이너들을 사용할수(적용시킬수) 있게 된다. 예를들어 어떤 컨테이너에 sort 알고리즘을 적용시키기 원한 다면 컨테이너 객체를 넣는대신에, sort 하고 싶은 범위를 iterator 를 통해 지정할수 있음으로(보통은 처음과 끝, 즉 전체가 되겠지만) 좀더 유연하게 프로그래밍 작업이 가능할것이다.

이렇듯 iterator 의 개념 자체는 간단하지만, iterator 에도 여러가지 종류가 있다. Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, Random Access Iterator 등이 있다. 헉 뭐가 이리 종류가 많지? 라고 걱정할수 도 있겠지만, 그리 걱정할 필요는 없다. 그냥 상식적? 으로 생각하면 되기 때문이다. 다음장에서는 이러한 Iterator 의 종류에 대해서 알아보도록 할것이다.

1.2절. Output Iterator

출력 반복자라고 부를수 있으며, 쓰기 전용의 반복자이다. 즉 어떤 컨테이너에 원소를 쓰는건 가능하지만 읽을수는 없는 종류의 iterator 들이다. 이들 이터레이터에는 ++ 연산이 가능하(.

#include <vector>
#include <string>

int main()
{
    vector<string> V;
    vector<string> V2;

    V.push_back("hello");
    V.push_back("Myname is yundream");

    copy(V.begin(), V.end(), ostream_iterator<string>(cout, "
"));
}
				

OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
				

#include <list>
#include <vector>

int main()
{
    list<int> L;
    L.push_front(3);

    front_insert_iterator<list<int> > ml(L);

    *ml++ = 0;
    *ml++ = 1;
    *ml++ = 2;

    copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
}
				

#include <list>
#include <vector>

int main()
{
    list<int> L;
    L.push_front(3);

    back_insert_iterator<list<int> > ml(L);

    *ml++ = 0;
    *ml++ = 1;
    *ml++ = 2;

    copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
}
				

#include <list>

int main()
{
    list<int> L;
    L.push_front(3);
    L.push_front(4);

    insert_iterator<list<int> > ii(L, L.begin());


    *ii++ = 0;
    *ii++ = 1;
    *ii++ = 2;
    copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
}
				

#include <vector>
#include <set>
#include <algorithm>

int main()
{
    int A1[] = {1, 3, 5, 7, 9 ,11};
    int B1[] = {1, 2, 3, 4, 5, 6};

    vector<int> A;
    vector<int> B;
    set<int> Result;

    copy(&A1[0], &A1[6], back_inserter(A));
    copy(&B1[0], &B1[6], back_inserter(B));

    merge(A.begin(), A.end(), B.begin(), B.end(),
        inserter(Result, Result.begin()) );

    copy(Result.begin(), Result.end(), ostream_iterator<int>(cout, " "));

    cout << endl;
}
				

1.3절. Input Iterator

입력반복자라고 불리우며, 읽기전용의 반복자이다. Output Iterator 과 정반대의 Iterator 이다. 마찬가지로 ++ 연산을 통해서 한쪽방향으로 순환이 가능하도록 되어 있다.

#include <vector>
#include <string>

int main()
{
    vector<string> V;

    copy(istream_iterator<string>(cin), istream_iterator<string>(),
        back_inserter(V));

    vector<string>::iterator mi;
    mi = V.begin();

    while(mi != V.end())
    {
        cout << *mi << endl;
        *mi++;
    }
}
				

1.4절. Forward Iterator

순방향 반복자이며, 한쪽방향으로 진행하며 읽기/쓰기가 모두 가능한 형태의 Iterator 이다. 다중 패스 알고리즘을 적용하기 위해서 사용될수 있다. forward Iterator 를 사용하는 대표적인 알고리즘으로 replace 라는 알고리즘이 있다.

  	
template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)
			

#include <vector>
#include <algorithm>

int main()
{
    vector<int> V;
    V.push_back(1);
    V.push_back(1);
    V.push_back(2);
    V.push_back(3);
    V.push_back(1);
    V.push_back(4);

    replace(V.begin(), V.end(), 1, 5);

    for (int i = 0; i < V.size(); i++)
        cout << V[i] << endl;
}
			

1.5절. Bidirectional Iterator

지금까지의 Iterator 는 한방향으로만 순환이 가능했다. 즉 Iterator 에 대한 ++ 연산만 가능했다 바면 Bidirectional 이란 이름에서 알수 있듯이 이 Iterator 는 양방향 모두로의 순환이 가능하다. 기본적인 특징은 Forward Iterator 과 같다.

양방향 반복자를 필요로 하는 가장 대표적인 알고리즘으로 reverse 알고리즘이 있다.

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
			

#include <vector>
#include <algorithm>

int main()
{
    vector<int> V;
    V.push_back(1);
    V.push_back(2);
    V.push_back(3);
    V.push_back(4);

    reverse(V.begin(), V.end());

    for (int i = 0; i < V.size(); i++)
        cout << V[i] << endl;
}
			

1.6절. Random Access Iterator

이것은 Bidirectional Iterator 의 특징인 양방향순환의 특징외에도 랜덤하게 원소에 접근할수 있는 특징을 제공한다. 다른 Iterator 들이 컨테이너를 순회하기 위해서 각원소에 차례대로 접근했던것과는 다르다.

예를들어 어떤 컨테이너에 대해서 binary search 를 수행한다고 가정해 보자, binary serach 의 특성상 Iterator 는 컨테이너의 임의 지점에 접근이 가능해야 search 가 효율적으로 이루어질수 있을것이다.

#include <vector>
#include <algorithm>

int main()
{
    vector<int> V;
    V.push_back(1);
    V.push_back(2);
    V.push_back(3);
    V.push_back(5);
    V.push_back(7);
    V.push_back(10);
    V.push_back(4);

    cout << binary_search(V.begin(), V.end(), 10) << endl;
}
			

binary_search 는 다음과 같이 정의되어 있다.

bool binary_search(ForwardIterator first, ForwardIterator last,
                   const LessThanComparable& value);