[ Anything ] - Iterator - 2

 Iterator은 크게 Input, Output, Forward, Random Access, Bidirectional iterator로 갈래가 나누어 집니다. 이전엔 input/output에 대해 공부를 했습니다. 나머지도 살펴보도록 합니다.

Forward Iterator

 

figure 1a

대표적으로 사용하는 Algorithm library의 함수 중 하나입니다. 온통 Forward iterator 타입의 오브젝트들로 가득합니다. 이전에 보았던 iterator들의 hierarchy관계도를 보면 알 수 있지만 Forward iterator는 input/output iterator의 조합과 같습니다. input iterator의 access와 output iterator의 assign을 모두 지원한다는 뜻이기도 합니다.

주목할 만한 특징은 Forward iterator는 거의 모든 STL Container가 사용한다는 점입니다. 왜냐하면 5개의 iterator 중에서 가장 간단하고 쉽게 Container을 loop 할 수 있기 때문입니다. 또한, input/output  iterator가 각각 rvalue, lvalue로 Dereference되기 때문에 Forward Iterator는 둘 다 사용할 수 있습니다.

이전에 보았던 두 개의 Iterators와 마찬가지로 Forward iterator는 post-increment(iter++)와 pre-increment(++iter)을 모두 사용하여 advance할 수 있습니다. equality, unequality 역시 input/output iterator와 같기 때문에 다른 비교 연산자는 사용할 수 없다는 점까지 같습니다.

 물론 forward iterator엔 단점 역시 존재합니다. 가장 체감할 수 있는 단점은 Offset dereference operator[]을 사용할 수 없다는 점입니다. 또, 단방향[unidirectional] iterator이기 때문에 감소시켜 Container을 탐색할 수는 없습니다. 그리고 위에서 설명했던 것처럼 equality, unequality operators을 제외하고는 이 Forward iterator에 대해서 implement하는 것은 원칙적으로 illegal입니다.

위에서 search을 예로 들었으나 실질적으로 체감할 수 있는 예는 아마도 std::replace일 것입니다.

figure 1b

생각을 해보았습니다. forward iterator는 input/output iterator의 조합입니다. 그리고 replace는 어떤 container의 범위를 스캔하고 어떤 조건에 부합하면 해당 값을 새로운 값으로 변환하는 기능을 수행합니다. container을 스캔할 때는 input iterator로 사용하는 것이 적합합니다. dereference을 하여 값만을 비교하면 되기 때문입니다. 반면에 조건에 부합하여 값을 변경해야 하는 경우엔 output iterator의 assign 성질을 사용해야 할 것입니다. 또한, 탐색을 하는 와중에 backward을 향해 역주행 할 이유가 없습니다. 따라서 std::replace는 input/output iterator의 성질을 모두 활용하는 Forward iterator을 채택하는 것이 적합합니다.

figure 1c

그런데 std::reverse_copy을 한 번 생각해봅니다. 이 함수는 다음과 같은 설명이 붙어 있습니다.

figure 1d

이 함수는 함수 이름이 설명하는 것처럼 어떤 Container의 원소들을 역순으로 다른 container에 복사하는 기능을 수행합니다. 즉, 값을 복사하는 과정에서는 iterator을 forward가 아닌 backward을 향해서 advance한다는 뜻입니다. 이는 Forward iterator의 정의에 정면으로 배치됩니다. 그래서 등장하는 iterator가 바로 Bidirectional iterator입니다.

Bidirectional iterator

이름이 설명을 끝냅니다. 기존 세 가지의 iterators와 다르게 이 iterator는 container의 begin, end의 방향으로 모두 Advance할 수 있습니다. 이 iterator는 std::next_permutation에서도 사용됩니다.

figure 2a

Bidirectional iterator는 Forward iterator와 유사하지만 begin 방향으로 Advance할 수 있다는 점이 다릅니다. Map, List, Multimap, Set, Multiset 등이 Bidirectional iterator을 지원한다는 점을 유념하는 것이 좋습니다. 즉, 우리가 만약 별다른 정의 없이 위의 예시의 iterator을 만든다면 그것은 자동적으로 Bidirectional Iterator가 됩니다. 마치 vector의 iterator가 Random access iterator가 되는 것처럼 말입니다.

중요한 특징들은 Input/Output Iterator에서부터 이어져옵니다. 한계점 역시 거의 같습니다. 이전 Iterator들의 장점과 단점에 단지 Advance방향이 한결 자유로워졌다는 점만 추가됩니다.

Random Access Iterator

 가장 접할 일이 많은 iterator입니다. STL Container 중 대표적인 vector의 iterator가 이 범주에 속하기 때문입니다. <algorithm> library에 있는  std::sort와 같은 함수의 argument에 넘어가는 iterator입니다.

figure 3a

Random access iterator는 Container 내의 임의의 원소에 접근하여 여타 iterator들이 수행할 수 있는 모든 것들을 할 수 있습니다. 따라서 C++17을 제외한 이전의 기준으로 본다면 가장 완전한 형태의 iterator라고 할 수 있습니다. bidiectional을 비롯한 iterator들이 increment나 decrement만 수행할 수 있었던 것과는 다르게 random access iterator는 다음과 같은 operator을 사용할 수도 있습니다.

figure 1b-1

figure 1b-2

istream_iterator는 원칙적으로 input iterator이기 때문에 pre/post increment나 eauqlity/inequality operator을 제외하곤 사용할 수 없으며 implement 시도 역시 Illegal입니다. 하지만 vector의 iterator는 random access iterator이기 때문에 사용할 수 있습니다. 다음과 같은 코드에서 출력이 될 것 같은 값은 '2'입니다.

figure 1c-1

figure 1c-2

뿐만 아니라 <=, >= 등등 다양한 대소 비교 연산자 역시 허용되는 특징을 갖고 있으며 일명 offset dereference operator 라고 불리는 []을 사용하여 iterator가 가리키는 주소의 값에 접근하는 것도 허용됩니다.