반복자

반복자는 포인터를 추상화한 클래스다. 그래서 포인터는 할 수 없는 더 많은 동작을 수행할 수 있다.

반복자는 컨테이너 원소를 순회하고 접근하는 일반화된 방법을 제공한다.

반복자의 종류

STL의 컨테이너를 공부하면서 임의 접근 반복자와 양방향 반복자에 대해서는 언급한 적이 있던 것 같다.

사실 반복자는 더 많다.
간단히 위에서부터 아래로 갈 수록 기능들이 점점 더 추가된다고 생각하면 된다.

• 입력 반복자
• 출력 반복자
• 순방향 반복자
• 양방향 반복자
• 임의 접근 반복자

입력 반복자

입력 반복자는 읽기, 이동, 비교 기능만 지원한다.

*iter와 iter->를 사용하여 읽을 수 있으며, ++을 이용한 전방향 이동, ==와 !=을 이용한 비교가 가능하다.

출력 반복자

출력 반복자는 쓰기, 복사 기능만 지원한다.

*iter에 대입을 지원하기 때문에 값을 쓸 수 있으며, iterator(iter)와 같은 복사 생성자를 통해 복사 생성할 수 있다.

순방향 반복자

순방향 반복자는 입력 반복자와 출력 반복자를 합친 인터페이스를 지원한다.
추가적으로 =을 이용한 대입, iterator() 등의 기본 생성자를 지원한다.

양방향 반복자

양방향 반복자는 순방향 반복자 기능에 --을 통한 역방향 이동을 지원한다.

임의 접근 반복자

임의 접근 반복자는 양방향 반복자 기능을 모두 지원한다.
추가적으로 반복자를 임의 접근하는 데 사용되는 +, -, +=, -=, [] 등의 연산을 지원한다.

순차열과 구간

순차열은 순서가 있는 원소들의 집합을 의미한다.
사실 이렇게 의미적으로 접근하는 것보다 인터페이스로 보는게 더 이해하기 쉽다.

begin()은 순차열의 시작 원소를 가리키는 반복자다.
end()은 순차열의 끝을 가리키는 반복자다.

즉, 순차열의 하나의 시작과 끝을 나타내는 반복자 쌍으로 표현된다.

그리고 이 begin()과 end()를 묶은 반복자 쌍을 구간이라고 한다.
하지만 end()는 포함되지 않기 때문에 항상 [begin, end)의 반개구간을 형성한다.

정리하면 순차열은 구간의 속한 원소들의 순서 있는 집합이다.
순차열을 반복자 쌍으로 표현하면 구간이 된다.

반복자와 상수 반복자

STL의 모든 컨테이너는 iterator와 const_iterator를 정의한다.

iterator는 반복자가 가리키는 원소를 읽거나 변경할 수 있다.
const_iterator는 반복자가 가리키는 원소를 읽을 수만 있다.

모든 컨테이너가 iterator와 const_iterator를 정의한다고 해서 모두 같은 반복자인 것은 아니다.

vector와 deque같은 배열 기반 컨테이너에서의 iterator와 const_iterator는 임의 접근 반복자로 정의된다.

vector와 deque을 제외한 노드 기반 컨테이너에서의 iterator와 const_iterator는 양방향 반복자로 정의된다.

포인터와 유사하게 iterator는 const_iterator로 자동 형 변환이 가능하다.

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);
    vec.push_back(50);

    vector<int>::iterator iter = vec.begin();

    // iterator가 const_iterator로 자동 형 변환 된다.
    vector<int>::const_iterator citer = vec.begin();    

    cout << "iterator: ";
    for(; iter != vec.end(); iter++)
        cout << *iter <<' ';
    cout << endl;
    
    cout << "const_iterator: ";
    for(; citer != vec.end(); citer++)
        cout << *citer << endl;
    cout << endl;

    *iter = 100;

    // const_iterator가 가리키는 원소의 값은 변경할 수 없다.
    // *citer = 100;
}

반복자는 const를 통해 가리키는 대상을 고정할 수도 있다.
이 점은 포인터와 매우 유사하게 동작한다.

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);
    vec.push_back(50);

    vector<int>::iterator iter = vec.begin() + 1;
    *iter = 100;    // 가능하다.
    ++iter;         // 가능하다.

    vector<int>::const_iterator citer = vec.begin() + 1;
    *citer = 100;   // 불가능하다. const_iterator는 읽기 전용.
    ++citer;        // 가능하다.

    const vector<int>::iterator iterc = vec.begin() + 1;
    *iterc = 100;   // 가능하다.
    ++iterc;        // 불가능하다. const므로 가리키는 원소는 고정.

    const vector<int>::const_iterator citerc = vec.begin() + 1;
    *citerc = 100;  // 불가능하다. const_iterator는 읽기 전용.
    ++citerc;       // 불가능하다. const므로 가리키는 원소는 고정. 
}

역방향 반복자

모든 STL 컨테이너는 reverse_iterator와 const_reverse_iterator를 지원한다.

reverse_iterator는 반복자가 가리키는 원소를 읽거나 변경할 수 있다.
const_reverse_iterator는 반복자가 가리키는 원소를 읽을 수만 있다.

마찬가지로 배열 기반 컨테이너의 역방향 반복자는 임의 접근 반복자로 구현된다.
노드 기반 컨테이너의 역방향 반복자는 양방향 반복자로 구현된다.

rbegin()은 순차열의 끝을 가리키는 반복자를 반환한다.
rend()는 순차열의 처음 원소를 가리키는 반복자를 반환한다.

포인터와 유사하게 reverse_iterator는 const_reverse_iterator로 자동 형 변환이 가능하다.

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);
    vec.push_back(50);

    cout << "iterator: ";   // 10 20 30 40 50이 출력된다.
    for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++)
        cout << *iter << ' ';
    cout << endl;
    
    cout << "reverse_iterator: ";   // 50 40 30 20 10이 출력된다.
    for(vector<int>::reverse_iterator iter = vec.rbegin(); iter != vec.rend(); iter++)
        cout << *iter << ' ';
    cout << endl;
}

iterator는 현재 위치의 원소를 가리키지만 reverse_iterator는 현재 위치의 원소의 다음 원소를 가리킨다.

정방향 반복자와 역방향 반복자의 순차열을 같게 하기 위함이다.

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);
    vec.push_back(50);

    // reverse_iterator 반복자 어댑터로 변환
    reverse_iterator<vector<int>::iterator> rbiter(vec.begin());
    reverse_iterator<vector<int>::iterator> reiter(vec.end());

    // 50 40 30 20 10이 출력된다.
    for(; rbiter != reiter; rbiter++)
        cout << *rbiter << ' ';
    cout << endl;

    // 50 40 30 20 10이 출력된다.
    for(vector<int>::reverse_iterator iter = vec.rbegin(); iter != vec.rend(); iter++)
        cout << *iter << ' ';
    cout << endl;
}

아래의 코드는 iterator와 reverse_iterator가 가리키는 원소가 다름을 보인다.

#include <iostream>
#include <vector>

int main(void)
{
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    vector<int>::iterator iter = vec.begin() + 1;
    vector<int>::reverse_iterator riter(iter);

    cout << *iter << endl;          // 20이 출력된다.
    cout << *riter << endl;         // 10이 출력된다.
    cout << *riter.base() << endl;  // 20이 출력된다.
}

삽입 반복자

삽입 반복자는 반복자를 이용하여 순차열에 원소를 삽입할 수 있게 변환해주는 반복자 어댑터다.

기본적으로 반복자는 덮어쓰기만 가능하다.
하지만 어댑터를 이용하면 반복자가 다른 기능을 하도록 변환할 수 있다.

inserter(c, iter);
    - c: 삽입할 컨테이너
    - iter: 삽입할 위치의 반복자

back_inserter(c);
    - c: 삽입할 컨테이너

front_inserter(c);
    - c: 삽입할 컨테이너

inserter()는 모든 컨테이너가 지원한다. 하지만 나머지는 아니다.

back_inserter()는 push_back()을 지원하는 vector, deque, list만 가능하다. front_inserter()는 push_front()를 지원하는 deque, list만 가능하다.

먼저 inserter()를 활용하는 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

int main(void)
{
    vector<int> vec1;
    vec1.push_back(10);
    vec1.push_back(20);
    vec1.push_back(30);
    vec1.push_back(40);
    vec1.push_back(50);

    vector<int> vec2;

    // 오류 발생! 덮어쓸 원소가 vec2에 존재하지 않는다.
    copy(vec1.begin(), vec1.end(), vec2.begin());

    // 삽입 반복자 어댑터를 이용하여 가능하다.
    insert_iterator<vector<int>> insert(vec2, vec2.begin());
    copy(vec1.begin(), vec1.end(), insert);

    // 임시 삽입 반복자 어댑터를 사용해도 된다.
    copy(vec1.begin(), vec1.end(), inserter<vector<int>>(vec2, vec2.begin()));

    cout << "vec1: ";   // 10 20 30 40 50이 출력된다.
    for(vector<int>::iterator iter = vec1.begin(); iter != vec1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;   
    
    cout << "vec2: ";   // 10 20 30 40 50이 출력된다.
    for(vector<int>::iterator iter = vec2.begin(); iter != vec2.end(); iter++)
        cout << *iter << ' ';
    cout << endl;    
}

그 다음 back_inserter()와 front_inserter()를 활용한 예시를 보자.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main(void)
{
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);
    vec.push_back(40);
    vec.push_back(50);

    list<int> lt1;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);

    list<int> lt2;
    lt2.push_back(1);
    lt2.push_back(2);
    lt2.push_back(3);

    copy(vec.begin(), vec.end(), back_inserter<list<int>>(lt1));
    copy(vec.begin(), vec.end(), front_inserter<list<int>>(lt2));

    cout << "vec: ";   // 10 20 30 40 50이 출력된다.
    for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++)
        cout << *iter << ' ';
    cout << endl;      
    
    cout << "lt1: ";   // 1 2 3 10 20 30 40 50이 출력된다.
    for(list<int>::iterator iter = lt1.begin(); iter != lt1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;    

    cout << "lt2: ";   // 50 40 30 20 10 1 2 3이 출력된다.
    for(list<int>::iterator iter = lt2.begin(); iter 2= lt1.end(); iter++)
        cout << *iter << ' ';
    cout << endl;    
}

입출력 스트림 반복자

입출력 스트림 반복자는 알고리즘이 스트림에 읽고 쓸 수 있게 하는 반복자 어댑터다.

istream_iterator<T>는 T 형식의 값을 입력 스트림에서부터 읽을 수 있다.
ostream_iterator<T>는 T 형식의 값을 출력 스트림에 쓸 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

int main(void)
{
    vector<int> vec;

    // 입력 스트림에서 정수를 입력받아서 vec에 저장한다.
    copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter<vector<int>>(vec));

    // 정수를 스트림 끝까지 입력받아서 화면에 출력한다.
    cout << "vec: ";
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}

반복자 특성과 보조 함수

반복자 특성은 게임 개발에서 다룰 일이 없다고 생각한다.

반복자 보조 함수를 이용하면 컨테이너에 상관없이 반복자를 안전하게 다룰 수 있다.

advance(it, n)는 반복자를 n만큼 이동시킬 때 사용한다.
양방향 반복자를 지원하는 컨테이너에서 유용하게 사용한다.

distance(it1, it2)는 두 반복자 사이의 거리를 계산할 때 사용한다.
it2의 위치에서 it1의 위치를 뺄셈하여 계산한다.

next(it + n)는 it에서 n만큼 이동시킨 반복자를 반환한다.
이때 원본 반복자는 변경되지 않는다.

정리

• 반복자는 컨테이너와 알고리즘 간의 인터페이스 역할을 한다.
• 역방향 반복자는 현재 원소의 다음 원소를 가리킨다.
• 반복자 어댑터를 통해서 반복자를 알고리즘에 사용할 수 있다.
• 반복자를 조작할 때는 안전하게 보조 함수를 이용한다.