반복자(Iterator)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

임의 접근 반복자(Randon Access Iterator)

• 특정 위치의 원소에 바로 접근할 수 있는 반복자
• vector, array 등에서 사용된다.

 

순방향 반복자(Forward Iterator)

• 한 쪽 방향으로만 진행하고 증가 연산만 가능한 반복자
• forward_list에서 사용된다.

 

양방향 반복자(Bidirectional Iterator)

• 양쪽 방향으로 진행 가능하고 증감 연산을 지원하는 반복자
• 대부분의 STL 컨테이너에서 지원한다.

 

반복자의 성능

vector, array에서 next(), prev()는 O(1)에 수행된다.

forward_list, list에서 next(), prev()는 선형 시간이 소요된다.

 

std::iterator

• 앞에서 뒤 방향으로 진행한다.

std::reverse_iterator

• 뒤에서 앞 방향으로 진행한다.

 

#include <iostream>
#include <vector>
#include <forward_list>

using namespace std;

void main()
{
    vector<string> vec = {"Lewis Hamilton", "Lewis Hamilton", "Nico Roseberg",
                            "Sebastian Vettel", "Lewis Hamilton", "Sebastian Vettel",
                            "Sebastian Vettel", "Sebastian Vettel", "Fernando Alonso"};
    
    vector<string>::iterator it = vec.begin();
    cout << "가장 최근 우승자: " << *it << endl;

    // O(1) 소요
    it += 8;
    cout << "8년전 우승자: " << *it << endl;

    // O(1) 소요
    advance(it, -3);
    cout << "그후 3년 뒤 우승자: " << *it << endl;

    // O(1) 소요
    cout << "그 2년 전 우승자: " << *next(it, 2) << endl;

    forward_list<string> fwd(vec.begin(), vec.end());

    forward_list<string>::iterator jt = fwd.begin();
    cout << "가장 최근 우승자: " << *jt << endl;

    // 선형 시간 소요
    advance(jt, 5);
    cout << "5년전 우승자: " << *jt << endl;

    // forward_list는 순방향으로만 이동할 수 있으므로 에러 발생
    //advance(jt, -2);
}

 

출력

가장 최근 우승자: Lewis Hamilton
8년전 우승자: Fernando Alonso
그후 3년 뒤 우승자: Sebastian Vettel
그 2년 전 우승자: Sebastian Vettel
가장 최근 우승자: Lewis Hamilton
5년전 우승자: Sebastian Vettel