Blog

C++ 예제로 배우는 소프트웨어 설계 기법 (11) — 반복자(Iterator)

10편의 컨테이너들은 원소를 담는 방식이 저마다 다르다. 연결 리스트는 노드 포인터를 따라가고 배열은 인덱스를 늘려 가므로, 내부 구조를 그대로 공개하면 컨테이너를 바꿀 때마다 순회 코드도 고쳐야 한다. 반복자(Iterator) 패턴은 내부 구조는 감추고 "다음 원소로 가는 방법"만 공개한다. 이 글에서는 가상 함수 기반 GoF 반복자와 STL 스타일 반복자를 직접 만들어 비교하고, C++20 반복자 concept·ranges 연동과 반복자 무효화(invalidation)까지 g++ 13.3으로 확인한다.

이 시리즈의 다른 글

내부 구조가 드러난 순회

#include <cstdio>

template <typename T>
struct Node { T data; Node* next; };

template <typename T>
struct SList {
    Node<T>* head = nullptr;                      // 내부 구조가 공개되어 있다
    void push_front(const T& v) { head = new Node<T>{v, head}; }
};

int main()
{
    SList<int> s;
    for (int i = 1; i <= 4; ++i) s.push_front(i * 10);
    for (Node<int>* p = s.head; p; p = p->next)   // 사용자가 노드 구조를 알아야 순회 가능
        std::printf(" %d", p->data);
    std::printf("\n");
    // 배열 기반 컨테이너로 바꾸면 이 루프를 모두 고쳐야 한다
}
$ g++ -std=c++20 -Wall -o ex exposed.cpp
$ ./ex
 40 30 20 10

사용자 코드가 Node와 next를 직접 다루므로 컨테이너 구현을 바꾸면 순회 코드가 모두 깨진다.

GoF 반복자: 인터페이스로 감추기

#include <cstdio>
#include <memory>
#include <vector>

template <typename T>
struct IIterator {                                // 순회 방법만 공개
    virtual ~IIterator() = default;
    virtual bool has_next() const = 0;
    virtual T& next() = 0;
};

template <typename T>
struct IContainer {
    virtual ~IContainer() = default;
    virtual std::unique_ptr<IIterator<T>> iterator() = 0;
};

template <typename T>
class SList : public IContainer<T> {
    struct Node { T data; Node* next; };
    Node* head_ = nullptr;
    struct It : IIterator<T> {
        Node* cur;
        explicit It(Node* n) : cur(n) {}
        bool has_next() const override { return cur; }
        T& next() override { T& v = cur->data; cur = cur->next; return v; }
    };
public:
    void push_front(const T& v) { head_ = new Node{v, head_}; }
    std::unique_ptr<IIterator<T>> iterator() override { return std::make_unique<It>(head_); }
};

template <typename T>
class Array : public IContainer<T> {
    std::vector<T> v_;
    struct It : IIterator<T> {
        std::vector<T>& v; std::size_t i = 0;
        explicit It(std::vector<T>& v) : v(v) {}
        bool has_next() const override { return i < v.size(); }
        T& next() override { return v[i++]; }
    };
public:
    void push_back(const T& x) { v_.push_back(x); }
    std::unique_ptr<IIterator<T>> iterator() override { return std::make_unique<It>(v_); }
};

void print_all(IContainer<int>& c)                // 컨테이너 종류를 모른다
{
    auto it = c.iterator();
    while (it->has_next()) std::printf(" %d", it->next());
    std::printf("\n");
}

int main()
{
    SList<int> s;
    Array<int> a;
    for (int i = 1; i <= 4; ++i) { s.push_front(i * 10); a.push_back(i); }
    print_all(s);
    print_all(a);
}
$ g++ -std=c++20 -Wall -o gi gof_iter.cpp
$ ./gi
 40 30 20 10
 1 2 3 4

print_all은 IContainer와 IIterator만 알기 때문에 리스트든 배열이든 같은 코드로 순회한다. 반복자를 힙에 만들고 원소마다 가상 함수를 두 번 부른다.

STL 스타일 반복자

#pragma once
#include <cstddef>
#include <iterator>

template <typename T>
class SList {
    struct Node { T data; Node* next; };
    Node* head_ = nullptr;
public:
    class iterator {                              // 포인터처럼 동작하는 반복자
        Node* cur_ = nullptr;
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using reference = T&;

        iterator() = default;
        explicit iterator(Node* n) : cur_(n) {}
        T& operator*() const { return cur_->data; }
        T* operator->() const { return &cur_->data; }
        iterator& operator++() { cur_ = cur_->next; return *this; }
        iterator operator++(int) { iterator t = *this; ++*this; return t; }
        bool operator==(const iterator&) const = default;
    };
    ~SList() { while (head_) { Node* n = head_->next; delete head_; head_ = n; } }
    void push_front(const T& v) { head_ = new Node{v, head_}; }
    iterator begin() { return iterator(head_); }
    iterator end() { return iterator(); }
};
#include <algorithm>
#include <iterator>
#include <cstdio>
#include <numeric>
#include <vector>
#include "slist.h"

template <typename C>
void print_all(C& c)                              // 가상 함수 없이 어떤 컨테이너든
{
    for (auto& x : c) std::printf(" %d", x);      // range-for는 begin()/end()만 요구
    std::printf("\n");
}

int main()
{
    SList<int> s;
    for (int i = 1; i <= 5; ++i) s.push_front(i * 10);
    std::vector<int> v{3, 1, 2};
    print_all(s);
    print_all(v);

    // 표준 알고리즘도 그대로 쓴다
    auto it = std::find(s.begin(), s.end(), 30);
    if (it != s.end()) std::printf("  find 30: found, next=%d\n", *std::next(it));
    std::printf("  sum=%d\n", std::accumulate(s.begin(), s.end(), 0));
    std::printf("  count_if >25: %td\n", std::count_if(s.begin(), s.end(), [](int x) { return x > 25; }));
}
$ g++ -std=c++20 -Wall -o si stl_iter.cpp
$ ./si
 50 40 30 20 10
 3 1 2
  find 30: found, next=20
  sum=150
  count_if >25: 3

*, ++, ==만 정의하면 포인터와 같은 모양이 되어 range-for와 std::find·std::accumulate 같은 표준 알고리즘이 그대로 동작한다. 공통 기반 클래스 대신 템플릿으로 컨테이너 종류를 숨겼다.

C++20 concept과 ranges

#include <algorithm>
#include <cstdio>
#include <iterator>
#include <ranges>
#include "slist.h"

static_assert(std::forward_iterator<SList<int>::iterator>);   // C++20 반복자 요구 조건 검사
static_assert(std::ranges::forward_range<SList<int>>);

int main()
{
    SList<int> s;
    for (int i = 1; i <= 8; ++i) s.push_front(i);
    auto evens_squared = s | std::views::filter([](int x) { return x % 2 == 0; })
                           | std::views::transform([](int x) { return x * x; });
    for (int x : evens_squared) std::printf(" %d", x);
    std::printf("\n  max=%d\n", std::ranges::max(s));
}
$ g++ -std=c++20 -Wall -o rg ranges.cpp
$ ./rg
 64 36 16 4
  max=8

반복자 별칭(value_type, difference_type)과 기본 생성자, 후위 ++를 갖췄으므로 std::forward_iterator를 만족한다. 그래서 직접 만든 리스트에 views::filter, ranges::max를 바로 쓸 수 있다.

순회 비용 비교

#include <chrono>
#include <cstdio>
#include <memory>
#include <vector>

template <typename T> struct IIterator { virtual ~IIterator() = default; virtual bool has_next() const = 0; virtual T& next() = 0; };
template <typename T> struct VecIt : IIterator<T> {
    std::vector<T>& v; std::size_t i = 0;
    explicit VecIt(std::vector<T>& v) : v(v) {}
    bool has_next() const override { return i < v.size(); }
    T& next() override { return v[i++]; }
};

__attribute__((noipa)) std::unique_ptr<IIterator<int>> make_it(std::vector<int>& v) { return std::make_unique<VecIt<int>>(v); }

__attribute__((noipa)) long sum_virtual(std::vector<int>& v)
{
    long s = 0;
    for (auto it = make_it(v); it->has_next(); ) s += it->next();
    return s;
}
__attribute__((noipa)) long sum_stl(std::vector<int>& v)
{
    long s = 0;
    for (int x : v) s += x;
    return s;
}

template <typename F> void bench(const char* n, F f)
{
    auto t = std::chrono::steady_clock::now();
    long r = f();
    std::printf("  %-8s %6.1f ms (sum=%ld)\n", n, std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t).count(), r);
}

int main()
{
    std::vector<int> v(50'000'000, 1);
    bench("virtual", [&] { return sum_virtual(v); });
    bench("stl", [&] { return sum_stl(v); });
}
$ g++ -std=c++20 -O2 -o bn bench.cpp
$ ./bn
  virtual    59.4 ms (sum=50000000)
  stl        13.8 ms (sum=50000000)
$ ./bn
  virtual    55.0 ms (sum=50000000)
  stl        12.7 ms (sum=50000000)

원소 5천만 개 합계에서 가상 함수 반복자는 약 4배 느렸다. STL 반복자는 인라인되어 포인터 증가와 덧셈만 남지만, 가상 함수 반복자는 원소마다 간접 호출이 남는다.

반복자 무효화

#include <cstdio>
#include <vector>

int main()
{
    std::vector<int> v{1, 2, 3};
    for (auto it = v.begin(); it != v.end(); ++it)
        if (*it == 2) v.push_back(20);           // 재할당되면 it가 옛 버퍼를 가리킨다
    std::printf("size=%zu\n", v.size());
}
$ g++ -std=c++20 -g -fsanitize=address -o iv invalidate.cpp
$ ./iv 2>&1 | grep -E "ERROR|#[0-9] .*invalidate.cpp" | head -2 | sed -E "s#/tmp/[^ ]*/##; s# at pc .*##; s#0x[0-9a-f]+ in ##"
==4914==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000018
    #0 main invalidate.cpp:8

push_back으로 버퍼가 재할당되면 기존 반복자는 해제된 메모리를 가리킨다. 반복자는 컨테이너 내부를 가리키는 포인터와 같으므로, 컨테이너를 바꾸는 연산 뒤에 계속 써도 되는지 확인해야 한다.

방식다형성비용표준 알고리즘
————
내부 구조 노출없음최소불가
GoF 반복자 (has_next/next)실행 시간 (가상 함수)힙 할당 + 원소마다 간접 호출불가
STL 반복자 (*, ++, ==)컴파일 시간 (템플릿)인라인, 포인터 수준가능

주의사항

상황문제대응
———
순회 중 push_back·insert·erase반복자 무효화, use-after-freeerase의 반환값 사용, 인덱스 순회, 또는 std::erase_if
반복자 별칭·기본 생성자 누락std::forward_iterator 불만족, ranges 사용 불가static_assert로 concept 검사
const 컨테이너 순회begin() const가 없으면 컴파일 에러const_iterator 제공
end() 반복자 역참조미정의 동작비교 후 역참조
함수 인자 안에서 반복자 비교와 증가를 함께 사용인자 평가 순서 미지정별도 문장으로 분리

마무리

  • 반복자는 컨테이너의 내부 구조를 감추고 순회 방법만 공개한다.
  • 실행 중 다형성이 필요하면 GoF 반복자, 성능과 표준 알고리즘 연동이 필요하면 STL 반복자를 쓴다.
  • C++20 반복자 concept을 만족시키면 직접 만든 컨테이너에도 ranges를 바로 쓸 수 있다.

참고

Tags: , , , , , , , , , , ,

답글 남기기