[ Anything ] - Iterator - 1

 C++에서 자주 사용하는 Iterator입니다. 이 Iterator는 우리가 사용하거나 만든 알고리즘을 STL[Standard Template Library]와 이어주는 일종의 다리의 역할을 하며 C++STL의 주축을 이루는 요소 중 하나입니다. 이 Iterator는 Container의 특정한 메모리 주소를 가리킬 수 있으며 종류에 따라서 Read/Write을 수행할 수 있습니다. 예를 들어서 다음과 같은 Class을 임의로 만들었다고 가정해봅시다.

figure 1a

물론 불완전하긴 하지만 STL의 Algorithm의 여러 함수가 요구하는 Iterator들이 구현이 되어 있기 때문에 Vertex에 필요한 operator을 구현하기만 하다면 정렬이나 제거, 복사 등 유용한 기능들을 활용할 수 있습니다. 그렇기 때문에 Iterator가 STL로 가는 연결고리 역할을 한다고 볼 수 있습니다.

단순하게 For loop나 While을 사용해도 상관은 없습니다. 실제로 코딩 테스트에서 STL을 위해 Iterator을 사용할 필요가 전혀 없기도 합니다. 오히려 Iterator을 사용하면 쓸데없이 문제가 복잡해지는 경향이 있기도 합니다. 가령 std::for_each의 경우 container 내의 자료에 대해 적당한 작업을 하려면 람다 식을 도입해야 하는데 이중으로 자료를 처리하려면 두 개의 람다식을 사용해야 하며 Static variable의 사용까지 제한을 받습니다. 그럼에도 불구하고 C++을 사랑하는 사람들이 Iterator을 사용하는 이유는 다음과 같습니다.

1. STL Container의 각 원소에 접근하고 특정한 작업을 수행할 수 있습니다.

2. Container의 내부 구조와 상관 없이 Iterator에 대한 기능만 구현이 되어 있다면 어떤 Container이든 STL의 알고리즘들을 사용할 수 있습니다.

3. Iterator algorithm은 Container의 타입에 종속적이지 않습니다.

4. Iterator는 STL Container class의 Generic한 접근법을 그대로 차용합니다.

사실 가장 핵심은 마지막 4번입니다. 약속된 몇 가지의 Iterator가 구현이 되어 있으면 매번 새롭게 등장하는 Container들에 대해 iterator을 숙지해야 할 필요가 전혀 없습니다. 어쩌면 생산성의 향상과 관련이 있을지도 모르겠습니다.

Pointers or Iterators?

언뜻 보기에 둘은 큰 차이가 없는 것 같습니다. 하지만 Pointer는 메모리의 주소값을 저장하는 일종의 변수이며 무엇이든 저장된 데이터의 타입과 같은 데이터 타입을 갖습니다. 한편 Iterator는 STL Container의 메모리 주소만을 가리키도록 설계가 되어 있습니다. Pointer가 함수의 주소를 가리킬 수 있는 반면 Iterator는 그런 목적으로 쓸 수 없습니다. 간단히 정리하면 STL Container에 종속되어 있다고 할 수 있습니다.

Five major classes in the iterator

배우기 전에는 Iterator을 무분별하게 사용하고 종종 치명적인 에러와 마주했습니다. 그 이유는 iterator에 대한 깊은 이해가 없이 사용했기 때문입니다. MSDN이나 CPPREFERENCE을 참조하면 Iterator에도 몇 가지 커다란 갈래가 있다는 사실을 알 수 있습니다.

figure 1b (from. https://www.geeksforgeeks.org/input-iterators-in-cpp/)

Input Iterator

input iterator는 제한된 상황에서만 사용할 수 있습니다. std::find의 경우를 예로 정리해보도록 합니다.

figure 2a

input iterator는 기본적으로 Read operation밖에 할 수 없습니다. 즉, asterisk(*)을 사용한 Dereferencing을 사용은 할 수 있지만 이를 통해 해당 주소의 값에 접근하여 수정하는 것은 원칙적으로 Illegal이란 뜻입니다. 이 원리는 input iterator는 dereference을 진행하면 rvalue을 반환하기 때문입니다.

게다가 input iterator는 오직 값을 증가만 시킬 수 있으며 감소를 시킬 수 없습니다. 그래서 input itertator는 다섯 가지 클래스 중 가장 빈약하다는 뜻에서 weak iterator라고도 합니다. 그래서 원칙대로라면 다음과 같은 코드는 컴파일을 할 수 없어야 합니다.

figure 2b

하지만 vector와 같은 Container는 input iterator보다 강력한 iterator을 반환하기 때문에 Read, Write 모두 수행할 수 있습니다. 조금 더 기술적인 설명은 vector의 Iterator는 random access iterator을 반환하기 때문이라고 할 수 있습니다. 만약 위의 코드에 사용된 iterator가 vector의 iterator가 아니라 istream의 iterator였더라면 오류가 생겼을 것입니다. 참고로 STL의 대표적인 Container중에서 Random access iterator을 제공하는 Container는 Vector와 Dequeue뿐입니다.

figure 2b-1

위의 코드는 잘 동작할 것입니다. 하지만 다음과 같이 input iterator에 해당하는 istream_iterator을 --시키는 행위는 분명 컴파일 자체가 불가능 할 것입니다.

figure 2b-2

가능한 다른 operation은 ++iter와 iter++을 통해 다음 iterator로 Advance(One-way iterator)할 수 있다는 것입니다. 따라서 input iterator을 Argument로 받는다면 해당 알고리즘은 single path algorithm일 가능성이 높습니다.

또, ==[equality operator], !=[inequality operator] 등의 operator을 사용하여 값을 비교할 수도 있습니다. input iterator의 이러한 성질 때문에 std::copy 함수의 경우엔 argument로 결코 input iterator을 받을 수 없습니다. Dereference는 되지만 값을 바꿀 수 없다면 복사를 하여 다른 Container을 만들 수 없기 때문입니다.

figure 2c

복사를 할 원본은 손상이 되어서도 안 되고 Read로 충분하기 때문에 input iterator을 사용하지만 새롭게 값을 채워 넣을 container는 output iterator을 사용하는 것을 볼 수 있습니다. 이렇듯, input iterator는 read only iterator의 성질을 갖기 때문에 가장 사용빈도가 낮습니다. 주의할 점은 Read only이기는 하지만 iterator간의 값의 Swap은 가능하다는 사실입니다.

figure 2d-1

위와 같이 분명 input iterator에 값을 Write하는 행위는 illegal이지만 std::swap을 통해 값을 교환하는 것은 됩니다.

figure 2d-2

figure 2d-3

Output Iterator

Input iterator와 마찬가지로 제한된 상황에서만 사용하는 iterator입니다. 직감적으로 input iterator가 read only였으니 output iterator는 write only일 것 같습니다. 좀 이상하긴 한데 원칙적으로 정해진 바에 따르면 그렇다고 합니다. 직관적으로 말이 안 되기는 하는데 값에 접근은 할 수 없지만 할당은 할 수 있습니다. 그래서 둘은 서로 상호보완적이라고 할 수 있습니다.

input iterator와 마찬가지로 ++iter, iter++을 사용하는 one-way iterator이며 Asterisk(*) operator로 Dereference할 수 있습니다. One-way iterator이기 때문에 자연스럽게 Single-pass algorithm에만 사용할 수 있습니다. 하지만 equlity/unequality operation은 수행할 수 없습니다. 왜냐하면 원칙적으로 output iterator는 value에 접근할 권한이 없기 때문입니다. 대신에 Dereference 한 공간에 어떤 자료를 할당할 수 있습니다. input iterator는 dereference시 rvalue을 반환했지만 output iterator는 값의 수정을 허용하기 때문에 기본적으로 lvalue을 반환합니다.

Input/Output Iterator and std::move()

figure 3a

std::move는 input/output iterator들의 성질을 설명할 수 있는 대표적 함수라고 할 수 있습니다. std::move는 이름처럼 자명한 기능을 수행합니다. 특정 범위의 무언가를 다른 범위에 이동시켜주는 역할을 합니다. 이동을 위해서는 원본에 대한 Read 을 수행하기 때문에 input iterator면 충분하지만 새로운 Container에 값을 할당해주기 위해서는 값에 Access의 문제가 아닌 Assign의 문제이기 때문에 Output iterator의 도움이 절실해집니다. 즉, std::move는 input/output iterator들의 환상의 콜라보레이션이라고 할 수 있겠습니다.

figure 3b

반환값이 output iterator일 수밖에 없습니다.