5 분 소요

모던 C++

개요

이터레이터(반복자)는 컨테이너에서 지금 가리키는 요소나 다음 요소를 찾아가는 방법을 제공합니다.

반개방구조

이터레이터의 시작(begin())과 끝(end())은 다음 그림과 같이 반개방 구조([begin - end) 로 표기합니다.)를 가집니다.

begin()은 요소의 시작 항목을 가리키고, end()는 마지막 요소의 다음 위치를 가리킵니다.

image

이에 따라, 다음과 같이 컨테이너에 요소가 있는지 없는지 확인할 수 있습니다.

1
2
3
4
5

// 컨테이너가 텅 비었습니다.
container.begin() == container.end();

// 컨테이너에 요소가 있습니다.
container.begin() != container.end();

이터레이터를 이용한 요소 접근

이터레이터는 다음의 연산자를 통해 요소에 접근합니다.

항목 내용
*, -> 이터레이터가 가리키는 요소
++ 다음 요소를 가리키는 이터레이터

++를 이용하여 이터레이터를 사용하는 경우에는 꼭 전위형을 사용해야 합니다. 후위형을 사용하면, 증가 시키기 전의 값을 복제해서 리턴하기 때문에 불필요한 복사 부하가 생깁니다.(증감 연산자와 연산자 오버로딩 참고)

또한, for() 문의 조건식에서 itr < endItr이 아니라 itr != endItr을 사용합니다. 이는 랜덤 접근이 가능한 이터레이터만 <이 가능하기 때문입니다. <을 지원하는 컨테이너라도 향후 다른 컨테이너로 변경할 수도 있기 때문에, 리팩토링시 수정을 최소화하기 위해 습관적으로 < 보다는 != 사용하는게 좋습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

std::vector<int> v(5); // 5개의 요소 생성(클래스면 생성자를 호출함)
EXPECT_TRUE(v[0] == 0 && v[1] == 0 && v[2] == 0 && v[3] == 0 && v[4] == 0);

std::vector<int>::iterator itr = v.begin(); // 요소의 시작
std::vector<int>::iterator endItr = v.end(); // 마지막 요소의 다음
for (int i = 0; itr != endItr; ++itr, ++i) { // 이터레이터는 복사 부하가 없도록 전위 증가 연산 사용
    *itr = i; // 요소에 값 할당
}

itr = v.begin();
for (int i = 0; itr != endItr; ++itr, ++i) { 
    EXPECT_TRUE(*itr == i);
}       

EXPECT_TRUE(v[0] == 0 && v[1] == 1 && v[2] == 2 && v[3] == 3 && v[4] == 4);

// 랜덤 접근이 가능하다면, 포인터 연산이랑 비슷한 형태로 접근      
*(v.begin() + 1) = 10; 
EXPECT_TRUE(v[1] == 10);

(C++11~) 범위 기반 for()가 추가되어 컨테이너 요소의 탐색 처리가 쉬워졌습니다.

이터레이터 카테고리

이터레이터는 그 특성에 따라 5가지 카테고리로 분류됩니다. 컨테이너는 요소 처리 특성에 맞게 이터레이터를 사용합니다.

항목 내용 컨테이너
input 읽기 전용
++, *, ->, =, ==, !=, 복사 생성자		  
output 쓰기 전용
++, *, =, 복사 생성자		  
forward 단방향 탐색
input과 연산자 동일		  
bidirectional 양방향 탐색
forward 에서 --추가		 list
map
random access 랜덤 접근 탐색
bidirectional에서 +, -, +=, -=, <, >, <=, >=, [] 추가		 vector

image

역방향 이터레이터

역방향 이터레이터는 ++시 요소의 끝에서 처음 방향으로 이동하는 이터레이터 입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 순방향
{
    std::vector<int> v(5); 

    std::vector<int>::iterator itr = v.begin(); // 요소의 시작
    std::vector<int>::iterator endItr = v.end(); // 요소의 끝
    for (int i = 0; itr != endItr; ++itr, ++i) { 
        *itr = i; 
    }
    EXPECT_TRUE(v[0] == 0 && v[1] == 1 && v[2] == 2 && v[3] == 3 && v[4] == 4);
}
// 역방향
{
    std::vector<int> v(5); 

    std::vector<int>::reverse_iterator itr = v.rbegin(); // 요소의 끝
    std::vector<int>::reverse_iterator endItr = v.rend(); // 요소의 시작
    for (int i = 0; itr != endItr; ++itr, ++i) { 
        *itr = i; 
    }
    EXPECT_TRUE(v[0] == 4 && v[1] == 3 && v[2] == 2 && v[3] == 1 && v[4] == 0);
}

삽입 이터레이터

삽입 이터레이터는 *first = value;시 컨테이너에 요소를 삽입하는 특수한 이터레이터 입니다.

다음과 같이 Fill() 함수를 구현했다고 합시다.

전달된 Iterator의

  1. ++을 이용하여 다음 요소로 이동하고,
  2. *을 이용하여 실제 요소를 참조하며,
  3. =을 이용하여 실제 요소에 값을 대입합니다.
1
2
3
4
5
6
7
8

// Iterator가 가르키는 곳부터 n개를 value로 채웁니다. 
// Iterator는 ++, *, = 연산자를 구현해야 합니다.
template<typename Iterator>
void Fill(Iterator first, size_t n, const int& value) {
    for (size_t i = n; 0 < n; --n, ++first) {
        *first = value;
    }
}

다음과 같이 사용할 수 있습니다.

1
2

std::vector<int> v(5); // 5개의 요소 생성(클래스면 생성자를 호출함) 
Fill(v.begin(), 5, 7); // v[0] ~ v[4] 에 7 대입.

하지만 다음은 vector가 할당되지 않아 오류가 발생합니다.

1
2

std::vector<int> v; // 빈 벡터
Fill(v.begin(), 5, 7); // (X) 예외 발생. v가 5개 할당되지 않았다면 예외 발생

Fill() 함수에서는 이터레이터를 반복하면서 *first = value; 로 실제 요소에 값을 대입하는데, 벡터에는 요소가 없어 예외가 발생하게 되는거죠.

이런 경우 값을 대입하지 않고, 컨테이너에 push_back() 하도록 = 연산자를 재정의한 것을 삽입 이터레이터라고 합니다. STL에서는 back_insert_iterator를 제공하고 있는데요, 원리를 이해하기 위해 직접 구현해 보겠습니다.

구현 방법은 다음과 같습니다.

  1. #1 : 값 생성자에서는 컨테이너를 전달받습니다.
  2. #2 : 복사 생성자에서는 컨테이너의 참조자를 복사합니다.
  3. #3 : 복사 대입 연산자는 사용하지 않으므로 private로 정의합니다.
  4. #4 : 복사 대입 연산자중 컨테이너 값 타입을 전달하면, push_back()을 하여 추가합니다.
  5. #5 : 무조건 끝에 추가하는 것이므로, ++은 아무 동작 안하게 합니다.
  6. #6 : * 시 자기 자신을 리턴하여 *first = value;시 #4가 호출되게 합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

template<typename ContainerT>
class MyBackInsertIterator {
    ContainerT& m_Container;
public:
    // 값 생성자에서는 Container를 전달받습니다.
    explicit MyBackInsertIterator(ContainerT& container) : // #1
        m_Container(container) {}

    // 복사 생성자에서는 컨테이너 참조자를 복사합니다.
    MyBackInsertIterator(const MyBackInsertIterator& other) : // #2
        m_Container(other.m_Container) {}
private:   
    // 복사 대입 연산자는 사용하지 않습니다.
    MyBackInsertIterator& operator =(const MyBackInsertIterator& other) {return *this;} // #3

public:
    // = 에서 컨테이너 값 타입을 전달하면, push_back()을 하여 추가합니다.
    MyBackInsertIterator& operator =(const typename ContainerT::value_type& value) { // #4
        m_Container.push_back(value);
        return *this;
    }

    // 무조건 끝에 추가하므로 ++는 별다른 동작하지 않습니다.
    MyBackInsertIterator& operator ++() { // #5
        return *this;
    }

    // * 시 자기 자신을 리턴하여 *first = value;시 #4가 호출되게 합니다.
    MyBackInsertIterator& operator *() { //# 6
        return *this;
    }
};

다음과 같이 테스트 합니다.

1
2
3
4

std::vector<int> v; 
Fill(MyBackInsertIterator<std::vector<int>>(v), 5, 7); // 현 컨테이너 뒤 5 개에 7 삽입. MyBackInsertIterator에서 operator = 을 push_back() 으로 구현

EXPECT_TRUE(v[0] == 7 && v[1] == 7 && v[2] == 7 && v[3] == 7 && v[4] == 7);

STL에서는 back_inserter() 유틸리티 함수로 back_insert_iterator를 생성해 주기 때문에 다음과 같이 사용할 수 있습니다.

1
2
3
4

std::vector<int> v; 
Fill(std::back_inserter(v), 5, 7); // 표준 유틸리티 함수 사용

EXPECT_TRUE(v[0] == 7 && v[1] == 7 && v[2] == 7 && v[3] == 7 && v[4] == 7);

이터레이터 어뎁터

역방향 이터레이터나 삽입 이터레이터와 같이 이터레이터의 고유 기능인 *, ->, ++을 재구현하여 다르게 동작하는 이터레이터들입니다. 자세한 사항은 모던 C++ STL의 이터레이터 어뎁터를 참고하시기 바랍니다.

댓글남기기