반복자

std::vector는 인덱스로 원소에 접근하지만, std::list나 std::set에는 인덱스가 없습니다. 컨테이너마다 순회하는 방법이 다르다면, 정렬이나 검색 같은 알고리즘을 컨테이너마다 따로 만들어야 합니다. 반복자(iterator)는 어떤 컨테이너든 같은 방식으로 원소를 가리키고 다음 원소로 넘어가게 해, 알고리즘과 컨테이너를 이어 줍니다.

이 글은 반복자의 기본 사용법, 반복자의 종류와 능력, 원소를 바꾸지 못하게 하는 const 반복자, 그리고 컨테이너를 바꿀 때 반복자가 무효가 되는 규칙을 다룹니다. 반복자는 포인터와 배열에서 본 포인터를 일반화한 것이어서, 간접 참조와 증가 같은 사용법이 포인터와 비슷합니다.

반복자의 기본 사용법

컨테이너의 begin()은 첫 원소를, end()는 마지막 원소의 바로 다음 위치를 가리키는 반복자를 돌려줍니다. *it로 가리키는 원소에 접근하고 ++it로 다음 원소로 넘어가며, it != end()인 동안 순회합니다.

#include <iostream>
#include <list>
#include <string>
#include <vector>

int main() {
    std::vector<int> numbers{10, 20, 30, 40, 50};
    auto it = numbers.begin();
    std::cout << *it << ' ';
    ++it;
    std::cout << *it << ' ';
    it = numbers.begin() + 3;
    std::cout << *it << '\n';

    for (auto pos = numbers.begin(); pos != numbers.end(); ++pos) {
        std::cout << *pos << ' ';
    }
    std::cout << '\n';

    std::list<std::string> fruits{"Apple", "Banana", "Cherry"};
    auto fit = fruits.begin();
    std::cout << *fit << ' ';
    ++fit;
    std::cout << *fit << ' ';
    --fit;
    std::cout << *fit << '\n';
}

10 20 40
10 20 30 40 50
Apple Banana Apple

std::vector의 반복자는 numbers.begin() + 3처럼 한 번에 여러 칸을 건너뛸 수 있고, std::list의 반복자는 ++와 --로 한 칸씩만 움직입니다. 반복자의 정확한 타입은 std::vector<int>::iterator처럼 길기 때문에 보통 auto로 받습니다. for 반복문에서 본 범위 기반 for도 안에서는 begin()과 end()를 써서 이렇게 순회합니다.

[begin(), end())는 시작은 포함하고 끝은 포함하지 않는 반열린 범위입니다. end()는 원소가 아니므로 간접 참조할 수 없고, 빈 컨테이너에서는 begin()과 end()가 같아서 begin()도 간접 참조할 수 없습니다. 또 서로 다른 컨테이너의 begin()과 end()를 짝지은 범위는 올바른 범위가 아닙니다.

반복자의 종류

반복자는 지원하는 연산에 따라 몇 가지 종류로 나뉘며, 아래 그림처럼 위 단계로 갈수록 할 수 있는 일이 늘어납니다.

쓰기 전용으로 한 번만 앞으로 가는 출력 반복자(output iterator)는 이 단계와 따로 있는 종류이며, std::ostream_iterator가 그 예입니다. 알고리즘은 필요한 종류를 정해 두므로, std::find는 입력 반복자로 충분하지만 std::sort는 임의 접근 반복자가 필요해 std::list에는 쓸 수 없습니다. 그래서 std::list는 정렬을 멤버 함수 sort()로 따로 제공합니다.

반복자의 종류에 맞춰 움직이는 도우미 함수도 있습니다. <iterator>의 std::next(it, n)과 std::prev(it, n)은 이동한 새 반복자를 돌려주고, std::distance(first, last)는 두 반복자 사이의 원소 수를 셉니다. 다만 std::prev는 뒤로 움직여야 하므로 양방향 반복자 이상에서만 쓸 수 있습니다. 임의 접근 반복자에서는 이들이 상수 시간이지만, 그 밖의 반복자에서는 한 칸씩 움직이므로 원소 수에 비례하는 시간이 듭니다.

const 반복자와 역방향 반복자

원소를 읽기만 할 때는 cbegin()과 cend()가 돌려주는 const_iterator를 씁니다. 이 반복자는 움직일 수는 있지만, 가리키는 원소를 바꿀 수는 없습니다.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> data{1, 2, 3, 4, 5};

    for (auto it = data.cbegin(); it != data.cend(); ++it) {
        std::cout << *it << ' ';
        // *it = 10; // 컴파일 오류: const_iterator로는 원소를 바꿀 수 없음
    }
    std::cout << '\n';

    for (auto it = data.rbegin(); it != data.rend(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';
}

1 2 3 4 5
5 4 3 2 1

const_iterator의 const는 const 포인터와 포인터 상수의 const int*처럼 가리키는 원소를 막는 것입니다. 반대로 const std::vector<int>::iterator는 반복자 객체 자체를 고정한 것이어서 원소는 바꿀 수 있지만 반복자를 움직일 수 없습니다. rbegin()과 rend()는 마지막 원소부터 거꾸로 순회하는 역방향 반복자(reverse iterator)를 돌려주며, 이때도 ++가 한 칸 앞, 즉 이전 원소로 이동합니다.

반복자 무효화

컨테이너에 원소를 넣거나 지우면, 그 전에 얻어 둔 반복자가 더 이상 올바른 위치를 가리키지 않을 수 있습니다. 이것을 반복자 무효화(iterator invalidation)라고 하며, 무효가 된 반복자를 쓰는 것은 정의되지 않은 동작입니다. 어느 반복자가 무효가 되는지는 컨테이너와 연산마다 다릅니다.

위 그림처럼 std::vector에 원소를 넣을 때 공간이 모자라 더 큰 공간으로 옮기는 재할당이 일어나면, 기존 원소를 가리키는 반복자, 참조, 포인터와 end()가 모두 무효가 됩니다. 재할당이 없으면 넣은 위치와 그 뒤만 무효가 되고, 앞의 원소는 그대로 유효합니다. erase는 지운 위치와 그 뒤를 무효로 만듭니다.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{10, 20, 30};
    values.reserve(8);
    auto first = values.begin();
    values.push_back(40);
    std::cout << *first << ' ' << values.size() << '\n';

    auto next = values.erase(values.begin() + 1);
    if (next != values.end()) {
        std::cout << *next << '\n';
    }

    for (int value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

10 4
30
10 30 40

reserve(8)은 원소 8개를 담을 공간을 미리 마련할 뿐 원소 수를 바꾸지 않으며, 이 뒤로는 원소가 8개를 넘기 전까지 재할당이 일어나지 않습니다. 그래서 push_back(40) 뒤에도 first는 유효해 10을 가리킵니다. erase는 20을 지우고, 지운 원소의 다음 위치를 가리키는 새 반복자를 돌려주므로 next는 30을 가리킵니다. 마지막 원소를 지우면 돌려받은 반복자가 end()이므로, 간접 참조하기 전에 확인해야 합니다.

순회하면서 원소를 지울 때는 erase가 돌려준 반복자로 이어 가야 합니다. 다음 함수는 짝수를 모두 지웁니다.

#include <vector>

void removeEven(std::vector<int>& v) {
    for (auto it = v.begin(); it != v.end();) {
        if (*it % 2 == 0) {
            it = v.erase(it);
        } else {
            ++it;
        }
    }
}

지운 경우에는 erase가 돌려준 다음 위치로 가고, 지우지 않은 경우에만 ++it로 넘어갑니다. C++20에서는 같은 일을 std::erase_if(v, [](int x) { return x % 2 == 0; }); 한 줄로 할 수 있습니다. 범위 기반 for도 안에서 반복자와 end()를 들고 있으므로, 그 안에서 원소를 넣거나 지우면 안 됩니다.

더 깊이: 무효가 된 반복자를 실행 중에 잡아내는 빌드

무효가 된 반복자를 쓰는 것은 정의되지 않은 동작이어서, 보통의 빌드에서는 우연히 옛 값을 읽고 그대로 지나가 버리기도 합니다. 그래서 표준 라이브러리 구현들은 개발 중에 이런 실수를 잡는 디버그용 빌드를 제공합니다. GCC의 libstdc++는 -D_GLIBCXX_DEBUG로 컴파일하면 디버그 모드가 켜지며, 이 모드의 반복자는 자기가 어느 컨테이너를 가리키는지 알고 있어서 범위 끝을 넘어 움직이거나 이미 사라진 컨테이너의 반복자를 간접 참조하면 문제를 표준 오류에 출력하고 프로그램을 멈춥니다. 알고리즘의 전제도 검사해서, 같은 비교 기준으로 정렬되어 있어야 하는 입력 범위가 그렇지 않으면 알려 줍니다.

이 모드는 std::vector 같은 표준 클래스 템플릿의 크기와 동작을 바꾼다는 점에 주의해야 합니다. libstdc++ 문서에 따르면 디버그 모드로 컴파일한 코드와 그렇지 않은 코드는, 두 번역 단위 사이에 컨테이너를 주고받지 않을 때만 함께 링크할 수 있습니다. MSVC에서는 _ITERATOR_DEBUG_LEVEL 매크로가 같은 역할을 하며, 디버그 빌드에서는 기본값 2로 반복자 디버깅이 켜지고 릴리스 빌드에서는 기본값 0으로 꺼집니다.

반복자 어댑터

반복자의 동작을 바꾸는 반복자 어댑터(iterator adapter)도 있습니다. 앞에서 본 역방향 반복자가 그 하나이고, std::back_inserter(v)가 만드는 삽입 반복자는 값을 대입할 때마다 v.push_back을 불러 원소를 추가합니다. 알고리즘이 결과를 쓸 위치로 삽입 반복자를 넘기면, 미리 공간을 만들지 않아도 결과가 컨테이너에 추가됩니다. 이 쓰임은 다음 글의 알고리즘에서 봅니다.

정리

• 반복자는 컨테이너의 원소를 가리키는 객체로, *it로 접근하고 ++it로 넘어가며 [begin(), end()) 범위를 순회합니다.
• end()는 원소가 아니므로 간접 참조할 수 없고, 빈 컨테이너에서는 begin()도 간접 참조할 수 없습니다.
• 반복자는 입력, 순방향, 양방향, 임의 접근, 연속의 순서로 능력이 늘며, 알고리즘은 필요한 종류를 요구합니다.
• const_iterator는 원소를 바꾸지 못하게 하고, 역방향 반복자는 마지막 원소부터 거꾸로 순회합니다.
• 컨테이너를 바꾸면 반복자가 무효가 될 수 있으며, 그 범위는 컨테이너와 연산마다 다르므로 바꾼 뒤에는 필요한 반복자를 다시 얻습니다.
• 순회하며 지울 때는 erase가 돌려준 반복자로 이어 가거나, C++20의 std::erase_if를 씁니다.

연습 문제

1. 값 바꾸기와 마지막 원소 지우기

invalidation.cpp의 처음 값을 {4, 5, 6}으로, 추가하는 값을 7로 바꾸면 세 줄은 무엇을 출력하나요? 마지막 원소를 erase해 돌려받은 반복자를 간접 참조해도 되나요?

2. 잘못된 삭제 루프

다음 코드로 짝수를 지우면 어떤 문제가 생기나요? v는 std::vector<int>라고 하고, erase를 부른 바로 뒤에 루프가 it로 무엇을 하는지를 따라가 보세요.

for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it);
    }
}

3. 리스트의 반복자

std::list<std::string> names{"Banana", "Cherry"};에서 auto it = names.begin();으로 Banana를 가리킨 뒤 names.push_front("Apple");을 하면, *it는 무엇인가요? 같은 일을 std::vector로 하면 어떤가요?

다음 글 알고리즘에서는 반복자 범위에 정렬, 검색, 변환 같은 연산을 적용하는 표준 알고리즘과, 결과를 쓸 공간을 준비하는 방법을 다룹니다.