이터레이터

이터레이터가 필요한 이유 - 이터레이터를 이해하는 것이 STL을 이해하는 열쇠이다. 템플릿이 알고리즘을 저장할 데이터형과 무관하게 만드는 것처럼, 이터레이터는 알고리즘을 사용할 컨테이너형과 무관하게 만든다. 이터레이터는 STL의 일반화 접근에 필수 구성요소 이다.

find 함수를 구현하기 위해 이터레이터가 가져야 하는 특성

이터레이터가 참조하는 값에 접근하기 위해 내용 참조를 할 수 있어야 한다. 즉, p가 이터레이터라면 *p가 정의되어야 한다.
한 이터레이터를 다른 이터레이터에 대입할 수 있어야 한다. 즉, p와 q가 이터레이터라면 p = q 라는 표현이 정의되어야 한다.
한 이터레이터가 다른 이터레이터에 대입할 수 있어야 한다. 즉, p와 q가 이터레이터라면 p = q 라는 표현이 정의되어야 한다.
한 이터레이터가 다른 이터레이터와 같은 것인지 비교할 수 있어야 한다. 즉, p와 q가 이터레이터라면 p == q 와 p != q라는 표현이 정의되어야 한다.

//배열일 경우

typedef double * iterator;

iterator find_ar(iterator begin, iterator end, const double & val)

{

iterator ar;

for(ar = begin; ar != end; ar++)

if(*ar == val)

return ar;

return end; // val을 찾지 못했다는 것을 나타낸다.

}

//링크드리스트 일경우

struct Node

{

double item;

Node * p_next;

};

class iterator

{

Node * pt;

public:

iterator() : pt(0){}

iterator (Node * pn) : pt(pn) {}

double operator*() { return pt->item;}

iterator & operator++() //++it를 위해

{

pt = pt->p_next;

return *this;

}

iterator operator++(int)

{

iterator tmp = *this; //it++ 를 위해

pt = pt->p_next;

return tmp;

}

//...operator==(), operator!=() 등

};

iterator find_ll(iterator head, const double & val)

{

iterator start;

for(start = head; start != 0; ++start)

if(*start == val)

return start;

return 0;

}

이터레이터 종류 - STL은 다섯 가지 이터레이터를 정의하고, 알고지름을 필요한 이터레이터의 종류로 서술한다. 다섯가지 이터레이터는 입력 이터레이터, 출력 이터레이터, 전방 이터레이터, 전후방 이터레이터, 임의 접근 이터레이터이다.

입력 이터레이터

"입력"이라는 용어는 프로그램의 관점에서 사용되는 말이다. 즉 키보드에서 프로그램으로 들어가는 정보를 입력이라고 생각하듯이, 컴테이너에서 프로그램으로 들어가는 정보를 입력이라고 생각한다. 따라서 입력 이터레이터는, 컴테이너로부터 값을 읽기 위해 프로그램이 사용할 수 있다. 특히, 입력 이터레이터의 내용 참조는 프로그램이 컴테이너로부터 하나의 값을 읽는 것을 허용하지만, 프로그램이 그 갓ㅂ을 변경하는 것을 허용할 필요는 없다. 따라서 입력 이터레이터를 필요로 하는 알고리즘들은, 컴테이너에 저자오딘 값을 변경하지 않는 알고리즘들이다.
입력 이터레이터는 컨테이너에 들어 있는 모든 값에 접근할 수 있도록 허용해야 한다. ++ 연산자의 접두어 버전과 접미어 버전을 두 다 지원하면 그렇게 된다. 입력 이터레이터를 컨테이너에 있는 첫 번째 원소를 지시하도록 설정하고, past-the-end에 도달할 때까지 증가시키면 그 컴테이터에 있는 모든 원소가 한 번씩 지시된다. 입력 이터레이터를 사용하여 다시 한 번 그 컨테이너를 훑을 때 동일한 순서로 값들을 훑고 지나간다는 보장은 없다. 또한 입력 이터레이터가 이미 증가된 후에 증가되기 전 값을 여전히 내용 참조할 수 있다는 보장은 없다. 입력 이터레이터에 기초를 둔 알고리즘은 일회성 알고리즘이다. 즉, 이전의 패스에서 얻은 이터레이터 값이나, 같은 패스라도 앞에서 얻은 이터레이터 값에 의존하지 않는다. 입력 이터레이터는 일방향 이터레이터이다. 즉, 증가시킬 수는 있지만 되돌릴 수는 없다.

출력 이터레이터

STL 사용헤서 "출력" 이라는 용어는 플그램에서 컨테이너로 정보를 보내기 위해 이터레이터가 사용된다는 것을 의미한다.(그래서 프로그램의 출력은 컴테이너의 입력이다.) 출력 이터레이터는 입력 이터레이터와 비슷하다. 다만 출력 이터레이터는 내용 참조를 통해 프로그램이 컨테이너에 있는 값을 읽는 것이 아니라 변경하는 것을 허용한다. 읽지 못하지만 쓸 수 있다는 것이 이상하게 여겨지겠지만, 이 특성은 화면 출력에도 적용된다. 즉, cout은 디스플레이로 보내지는 문자들의 스트림을 변경할 수 있지만, 화면에 표시된 것들을 읽지 못한다. STL은 매우 일반적이어서 컨테이너들이 출력 장치를 나타낼 수도 있다. 그러므로 컨테이너들을 가지고 같은 상황을 만들 수 있다. 또한 알고리즘이 컨테이너의 내용을 읽지 않고 변경한다면, 그 내용을 읽을 수 있는 이터레이터는 있을 필요가 없다.
요약하면, 입력 이터레이터는 일회성 읽기 전용 알고리즘에 사용할 수 있고, 출력 이터레이터는 일회성 쓰기 전용 알고리즘에 사용할 수 있다.

전방 이터레이터

입력 이터레이터나 출력 이터레이터와 마찬가지로, 전방 이터레이터도 컨테이너 속을 훑고 지나가기 위해 ++ 연산자만 사용한다. 그래서 전방 이터레이터는 컨테이너 속을 한 번에 한 원소씩 전방으로만 진행할 수 있다. 입력 이터레이터나 출력 이터레이터와는 달리, 전방 이터레이터는 그것을 사용할 때마다 연속된 값들을 반드시 같은 순서로 훑고 지나간다. 또한 전방 이터레이터가 증가된 후에도 그 이전의 이터레이터 값을 내용 참조하여 항상 같은 값을 얻을 수 있다. 이 특성 때문에 다중 패스 알고리즘이 가능해진다.
데이터를 읽을 때와 변경할 때 전방 이터레이터를 사용할 수 있다. 데이터를 읽기만 할 때에도 전방 이터레이터를 사용할 수 있다.

전후방 이터레이터

컨테이너 속을 전방과 후방으로 모두 훑고 지나갈 필요가 있는 알고지름이 있다고 가정하자. 예를들어, 뒤집기(reverse)함수를 첫 번째 원소와 마지막 원소를 맞바꾸고, 첫 번째 원소를 지시하는 포인터는 증가시키고 마지막 원소를 지시하는 포인터는 감소시키면서 이 과정을 반복한다. 전후방 이터레이터는 전방 이터레이터가 가지고 있는 모든 기능에 (접두어 버전과 접미어 버전의) 두 감소 연산자에 대한 기능을 추가한다.

임의 접근 이터레이터

표준 소팅이나 이진 탐색과 같은 알고리즘은, 컨테이너에 들어 있는 임의 원소로 직접 점프할 수 있는 기능을 가지고 있어야 한다. 이것을 임의접근 이라 한다. 이때 임의 접근 이터레이터가 필요하다. 임의 접근 이터레이터는 전후방 이터레이터가 가지고 있는 모든 기능에, 임의 접근을 지원하는 (포인터 덧셈과 같은) 연산과, 원소들의 순서를 매기는 데 사용할 관계 연산자들을 추가한다.

copy(), ostream_iterator, istream_iterator

copy()

하나의 컨테이너에서 다른 컨테이너로 데이터를 복사하는 copy() 라는 알고리즘이 있다.
int casts[10] = {4, 2, 3, 7, 6, 8, 5, 6, 9, 1};
vector<int> dice(10);
copy(casts, casts + 10, dice.begin()); //배열을 벡터에 복사한다.
copy() 함수는 목적지 컨테이너에 있는 기존의 데이터 위에 쓴다. 그리고 목적지 컨테이너는 복사되는 원소들을 저장할 수 있을 만큼 충분히 커야 한다. 그러므로 빈 벡터에는 copy() 함수를 사용하여 데이터를 복사할 수 없다. 이것을 할 수 있는 비법 있긴 있다. 뒤에 나옴

ostream_iterator

#include <iterator>
...
ostream_iterator<int, char> out_iter(cout, " ");
out_iter 이터레이터는 cout을 사용하여 정보를 출력할 수 있게 해주는 인터페이스가 된다. 첫 번째 템플릿 전달인자는 출력 스트림으로 보내는 데이터형을 나타낸다. 두 번째 템플릿 전달인자는 출력 스트림이 사용하는 문자형을 나타낸다.
첫 번째 생성자 전달인자는 사용할 출력 스트림을 나타낸다. 파일 출력에 사용되는 스트림이 첫 번째 생성자 전달인자가 될 수도 있다. 두 번째 문자열 전달인자는 출력 스트림에 보내진 각 항목 뒤에 표시되는 분리자이다.
*out_iter++ = 15; // cout<<15<<" "; 처럼 동작한다.
copy(dice.begin(), dice.end(), out_iter); // 벡터를 출력 스트림에 복사
copy(dice.begin(), dice.end(), ostream_iterator<int, char>(cout, " ")); //익명 이터레이터
copy(istream_iterator<int, char>(cin), istream_iterator<int, char>(), dice.begin();

ostream_iterator와 마찬가지로, istream_iterator도 구 개의 템플릿 전달인자를 사용한다. 첫 번째 템플릿 전달인자는 읽을 데이터형을 나타낸다. 두 번째 템플릿 전달인자는 입력 스트림에 사용되는 char 데이터형을 타나낸다. 생성자 전달인자로 사용하는 것은 cin이 관리하는 입력 스트림을 사용한다는 뜻이다. 생성자 전달인자를 생략하는 것은, 입력 실패를 나타낸다. 그래서 위 코드는 파일 끝, 데이터형 불일치 또는 다른 어떤 입력 실패가 일어날 때까지 입력 스트림으로부터 읽는다는 뜻이다.

기타 유용한 이터레이터들

reverse_iterator

vector 클래스는 past-the-end를 지시하는 reverse_iterator를 리턴하는 rbegin() 이라는 멤버함수와, 첫 번째 원소를 지시하는 reverse_iterator를 리턴하는 rend() 멤버 함수를 가지고 있다. reverse_iterator를 증가시키면 실제로는 감소되기 때문에 다음과 같은 명령문을 사용하면 컨테이너의 내용을 뒤집어 풀력할 수 있다. 그리고 reverse_iterator는 선언할 필요조차 없다.
copy(dice.rbegin(), dice.rend(), out_iter); //후진으로 출력
역방향 포인터의 사용은 특별한 보상을 요구한다. rp가 dice.rbegin() 으로 초기화되는 역방향 포인터라고 가정하자. 그렇다면 *rp는 무엇이 되는가? rbegin()은 past-the-end를 리턴하기 때문에 그 주소의 내용을 참조하려 시도하면 안된다. 마찬가지로 rend()가 실제로 첫 번째 원소의 위치라면 범위의 끝이 복사 범위에 포함되지 않기 때문에 copy()는 한걸음 일찍 복사를 멈춘다.
역방향 포인터들은 먼저 감소기킨 후에 내용 참조를 함으로써 이 두 가지 문제를 해결한다. 즉, *rp는 *rp의 현재 값 바로 앞에 있는 이터레이터 값을 내용 참조한다. 즉, rp가 여섯 번째 위치를 지시한다면, *rp는 다섯 번째 위치의 값이 된다.

//copyit.cpp -- copy()와 이터레이터를 사용한다.

#include <iostream>

#include <iterator>

#include <vector>

int main()

{

using namespace std;

int casts[10] = {6, 7, 3, 4, 7, 8, 9, 4, 3, 8};

vector<int> dice(10);

//배열에서 벡터로 복사한다.

copy(casts, casts + 10, dice.begin());

cout<<"주사위를 던저라!\n";

//ostream 이터레이터를 생서한다.

ostream_iterator<int,char> out_iter(cout," ");

//벡터에서 출력 스트림으로 복사한다.

copy(dice.begin(), dice.end(), out_iter);

cout<<endl;

cout<<" 역방향 이터레이터의 암시적 사용: \n";

copy(dice.rbegin(), dice.rend(), out_iter);

cout<<endl;

cout<<" 역방향 이터레이터의 명시적 사용: \n";

vector<int>::reverse_iterator ri;

for(ri = dice.rbegin(); ri != dice.rend(); ++ri)

cout<<*ri<<' ';

cout<<endl;

cin.get();

return 0;

}

insert_iterator, back_insert_iterator, front_insert_iterator

copy(casts, casts + 10, dice.begin());
함수는 dice가 그 값들을 저장할 수 있는 충분한 공간을 가지고 있다고 가정한다. 즉, copy()는 목적지로 보내지는 정보의 크기에 맞게 목적지의 크기를 자동으로 조정하지 않는다.
세 개의 삽입 이터레이터가 복사 과정을 삽입 과정으로 변환함으로써 이 문제를 해결한다. 삽입은 기존 데이터 위에 쓰지 않고 새 원소들을 추가하여, 자동 메모리 할당을 사용하여 새 정보에 꼭 맞는 공산을 확보한다. back_insert_iterator 는 컨테이너의 말미에 원소들으라 삽입한다. 그리고 front_insert_iterator는 컨테이너의 선두에 원소를 삽입한다. insert_iterator 는 insert_iterator 생성자에 전달인자로 지정된 위치 앞에 원소들을 삽입한다. 이 세 가지는 모두 출력 컨테이너 개념의 모델들이다.
back_insert_iterator<vector<int>> back_iter(dice);
insert_iterator<vector<int>> insert_iter(dice, dice.begin()); //삽입될 위치를 지정하는 생성자 전달인자가 하나 추가된다.

//inserts.cpp -- copy() 와 삽입 이터레이터들을 사용한다.

#include <iostream>

#include <string>

#include <iterator>

#include <vector>

int main()

{

using namespace std;

string s1[4] = {"fine", "fish", "fashion", "fate"};

string s2[2] = {"busy", "bats"};

string s3[2] = {"sillay", "singers"};

vector<string> words(4);

copy(s1,s1 + 4, words.begin());

ostream_iterator<string, char> out(cout," ");

copy(words.begin(), words.end(), out);

cout<<endl;

//익명의 back_insert_iterator 객체를 생서한다.

copy(s2,s2+2, back_insert_iterator<vector<string>>(words));

copy(words.begin(), words.end(), out);

cout<<endl;

//익명의 insert_iterator 객체를 생서한다.

copy(s3,s3+2, insert_iterator<vector<string>>(words,words.begin()));

copy(words.begin(), words.end(), out);

cout<<endl;

cin.get();

return 0;

}

//list.cpp -- list를 사용한다.

#include <iostream>

#include<list>

#include <iterator>

int main()

{

using namespace std;

list<int> one(5,2);

int stuff[5] = {1, 2, 4, 8, 6};

list<int> two;

two.insert(two.begin(), stuff, stuff + 5);

int more[6] = {6, 4, 2, 4, 6, 5};

list<int> three(two);

three.insert(three.end(), more, more+6);

cout<<"리스트 one: ";

ostream_iterator<int, char> out(cout, " ");

copy(one.begin(), one.end(), out);

cout<<endl<<"리스트 two: ";

copy(two.begin(), two.end(), out);

cout<<endl<<"리스트 three: ";