STL - 이터레이터(iterator)

★ 일반화 프로그래밍

→ STL은 일반화 프로그래밍의 한가지 예이다.

→ 객체지향 프로그래밍이 프로그램의 데이터적인 측면을 중시하는 데에 비해 일반화 프로그래밍은 데이터 타입에 대해 무관하며 알고리즘을 중시한다.
이것은 즉 일반화 프로그래밍이라는 것이 어떠한 데이터 타입에서도 무난하게 돌아가야 한다는 것을 의미한다.


★ 이터레이터에 대해

→ STL을 이해하기 위해서는 이터레이터의 이해가 반드시 필요하다. 배열, 리스트, 큐 등 다양한 종류의 컨테이너에 대해서 같은 연산으로 동일한 동작을 할 수 있도록 하는 것이 이터레이터이다.
예를 들어 ++연산을 예로 들어본다면 둘다 다음 요소를 가리키게 한다는 기능적인 측면에서는 같지만, 배열에서는 다음 주소 공간을 가리키게 하는데에 비해 리스트는 서로의 원소들이 (메모리 주소상으로는) 떨어져있고 Link로 연결되어 있으므로 다음 노드를 가리키게 하는 데에는 실제적으로 배열과 다소 틀리다. 당연히 같은 기능을 하는 함수임에도 불구하고 알고리즘은 판이하게 차이가 날 수밖에 없다.
하지만 이터레이터는 이런 다양한 구조의 컨테이너에 대해 동일 연산으로 동일한 기능을 할 수 있게 해주는 역활을 한다.


★ 이터레이터의 종류

→ 이터레이터도 쓰는 알고리즘에 따라서 그 종류가 달라질 수 있다.
예를 들어 어떤 컨테이너 내부를 전부 훑으면서 그 값들을 출력하는 알고리즘이 있다고 하자. 이터레이터는 여기서 데이터를 읽으면서 ++ 연산자를 통해 둘러볼 수 있을 것이다. 이 때 데이터 읽기 접근은 가능하나 쓰기(원소의 변경)은 금지시켜야 한다. 이와 같은 접근 제어에 관련된 이터레이터의 종류는 5가지가 된다.

1. 입력 이터레이터

→ 여기서 입력이라는 개념은 컨테이너→프로그램 으로 데이터 이동이 가능하다는 것을 의미한다. 즉, 컨테이너의 내용을 읽는 것이 가능하다는 뜻이다. 그러나 프로그램에서 컨테이너로의 데이터 쓰기는 금지되어 있다.
또한 입력 이터레이터는 컨테이너의 모든 원소들의 값을 읽을 수 있도록 하기 위해 ++ 연산자를 지원한다. 그러나 역순 이동인 -- 연산자는 지원하지 않는다. 이것은 입력 이터레이터가 순방향으로 이동하며 값을 읽기만 가능하나는 것을 의미한다.

→ 그리고 입력 이터레이터는 ++ 연산자를 통해 원소의 처음부터 해서 모든 원소들을 둘러 본 후 다시 처음부터 둘러 본다고 한다면 둘러보는 원소의 순서가 전 때와 같을 것이라는 보장이 없다. 즉, 순서대로 읽는 것이 거의 불가능 하며, 이 때문에 출력 이터레이터와 같이 입력 이터레이터는 일회성으로 쓰일 수밖에 없다.

2. 출력 이터레이터

→ 입력 이터레이터와는 틀리게 프로그램→컨테이너 로의 데이터 이동이 가능하다. 즉, 컨테이너에서 값을 쓸 수만 있고, 읽을 수는 없다는 것이다.
출력 이터레이터는 입력의 경우와 마찬가지로 ++ 연산자를 통한 순방향 이동은 가능하지만 -- 연산을 통한 역방향 이동은 금지되어 있다.

→ 또한 출력 이터레이터도 입력 이터레이터의 경우와 마찬가지로 원소를 또 다시 둘러 본다 할때, 둘러보는 원소의 순서가 이전과 동일할 것이라는 보장성이 없다. 결국 이것도 일회성으로 쓰일 수밖에 없다는 것이 된다.

3. 전방 이터레이터

→ 입력과 출력이 둘 다 가능한 이터레이터이며 이것 또한 ++ 연산자를 통해 순방향 이동만 가능하며 역방향 이동연산(--)이 불가능하다. 하지만 전방 이터레이터는 다시 컨테이너의 원소들을 둘러본다 할지라도 이전과 같은 순서로 순회가 가능하게 되었다.

4. 전후방 이터레이터

→ 전방 이터레이터에서 -- 연산자를 통해 역방향 이동도 가능한 것이 추가되었다. 물론 읽고 쓰기 둘다 가능하고 원소들을 다시 둘러본다 할지라도 그 순서가 변하지 않는다.

5. 임의접근 이터레이터

→ 순방향, 역방향 이동 뿐만 아니라 + 나 - 등의 연산자를 통한 직접적 점프가 가능하다. 임의접근 이터레이터는 [], +=, -= 같은 연산자 사용도 가능하고, >, < 같은 비교 연산도 가능하게 해준다.
허나 이런 연산들은 이터레이터가 컨테이너 첫 원소부터 past-the-end (컨테이너 마지막 원소 바로 다음 부분)까지의 범위에서만 유효하다.


→ 위와 같은 이터레이터들은 계층이 있으며 그 순서는

(입력 - 출력) < 전방 < 전후방 < 임의 접근 의 계층이다. (입력-출력 계층의 요구사항이 가장 적다.)

→ 이렇게 다양한 종류의 이터레이터들로 나눈 이유는 요구사항이 적은 이터레이터로 알고리즘을 만듬으로써 다양한 종류의 컨테이너들이 사용할 수 있도록 하는 목적을 가지고 있다. ( 아마도 컨테이너에 따라서는 위의 이터레이터 중 쓰지 못하는 것도 있는 모양이다. )
list 같은 경우의 이터레이터는 전후방 이터레이터를 가질 수 있는데, 이것은 입출력, 전방, 전후방 이터레이터를 쓰는 알고리즘을 사용할 수 있지만 요구사항이 전후방 이터레이터보다 더 높은 임의 접근 이터레이터를 쓰는 알고리즘을 사용할 수가 없다는 뜻이 된다.


★ 포인터도 이터레이터다.

→ 이터레이터는 포인터의 일반화 버전이고, 포인터는 이터레이터의 모든 조건을 충족시킨다. 이 말은 즉, 이터레이터를 쓰는 STL알고리즘에 포인터를 넣을 수도 있다는 것이 된다.
예를 들어 이런 것도 가능하다.

const int SIZE = 100;
double Receipts[SIZE];

... // Receipts에 값을 넣음..

// sort() 의 인수는 [인수1, 인수2) 범위의 이터레이터임.
sort( Receipts, Receipts + SIZE );
// Receipts는 위 배열의 가장 첫번째 주소이며, Receipts + SIZE 는 위 배열의 past-the-end 부분이다.
// past-the-end : 마지막 원소 바로 다음 지점

→ 이렇게 배열도 past-the-end 마커를 제공할 수 있다면 (반드시 past-the-end 마커 지점을 알아야만 하는 것은 아님) STL 알고리즘에 포인터를 적용시키는 것이 가능하다.