커스텀 이터레이터 구현

왜 커스텀 이터레이터를 구현하나?

• 커스텀 컨테이너를 STL처럼 쓰기 위해 필요합니다.
• 목표는 다음 3가지입니다.
  1) for (auto& x : container) 지원
  2) find, copy, for_each 같은 알고리즘과 연동
  3) 내부 구조(배열, 연결 리스트)를 감춘 채 공통 사용법 제공

---

이터레이터가 최소로 제공해야 할 연산

학습용 최소 세트(Forward 수준 기준):

연산	의미
*it	현재 요소 접근
++it	다음 요소로 이동
it1 == it2, it1 != it2	위치 비교

추가로 자주 구현:

• it++ (후위 증가)
• it->member (operator->)
• 양방향 컨테이너라면 --it

이터레이터 내부 구조

[ Vector Iterator ]              [ List Iterator ]
  ptr ──────────►                  node ──────────►
  ┌────┬────┬────┬────┐            [10]↔[20]↔[30]
  │ 10 │ 20 │ 30 │ 40 │               ▲
  └────┴────┴────┴────┘            *it → node->data
  ++it → ptr++                    ++it → node = node->next

---

벡터 스타일 이터레이터 (포인터 기반)

template <typename T>
class VectorIterator {
public:
    explicit VectorIterator(T* p = nullptr) : ptr(p) {}

    T& operator*() const { return *ptr; }
    T* operator->() const { return ptr; }

    VectorIterator& operator++() { ++ptr; return *this; }      // 전위 ++
    VectorIterator operator++(int) {                           // 후위 ++
        VectorIterator temp(*this);
        ++(*this);
        return temp;
    }

    bool operator==(const VectorIterator& rhs) const { return ptr == rhs.ptr; }
    bool operator!=(const VectorIterator& rhs) const { return !(*this == rhs); }

private:
    T* ptr;
};

핵심 포인트:

• 내부가 연속 메모리면 ++는 포인터 증가(ptr++)로 직관적입니다.
• end()는 마지막 다음 주소를 가리켜야 합니다.
• 빈 컨테이너에서도 begin() == end()가 되도록 설계해야 합니다.

---

리스트 스타일 이터레이터 (노드 기반)

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

template <typename T>
class ListIterator {
public:
    explicit ListIterator(Node<T>* n = nullptr) : node(n) {}

    T& operator*() const { return node->data; }
    T* operator->() const { return &node->data; }

    ListIterator& operator++() { node = node->next; return *this; }
    ListIterator& operator--() { node = node->prev; return *this; } // 양방향

    bool operator==(const ListIterator& rhs) const { return node == rhs.node; }
    bool operator!=(const ListIterator& rhs) const { return !(*this == rhs); }

private:
    Node<T>* node;
};

핵심 포인트:

• 리스트는 연속 메모리가 아니므로 it + 1 같은 랜덤 접근 연산을 지원하지 않습니다.
• 보통 더미(tail sentinel) 노드를 두고 end()가 그 노드를 가리키게 설계합니다.

---

컨테이너의 begin() / end() 구현 포인트

벡터 스타일 컨테이너 예시:

iterator begin() { return iterator(buffer); }
iterator end()   { return iterator(buffer + sz); }

리스트(더미 노드) 스타일 컨테이너 예시:

iterator begin() { return iterator(head->next); }
iterator end()   { return iterator(tail); }

체크 포인트:

• 빈 컨테이너에서 begin() == end()가 성립하는가?
• end()를 역참조하지 않도록 API 사용 규칙이 명확한가?
• const 컨테이너에 대해 const_iterator begin() const를 제공했는가?

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
operator!=만 급하게 구현하고 operator== 생략	비교 로직 중복/불일치 위험
end()를 마지막 요소로 착각	마지막 원소 누락 또는 UB
리스트 이터레이터에 it + n 기대	컨테이너 특성과 불일치
수정 가능한 이터레이터만 제공	const 컨테이너 순회 불편/오류

체크 질문 (스스로 답해보기)

• 벡터 이터레이터와 리스트 이터레이터의 ++ 동작이 본질적으로 왜 다른가?
• begin() == end()가 되는 "빈 컨테이너" 상태를 직접 구성해 설명할 수 있는가?
• 커스텀 컨테이너에서 range-for가 동작하려면 어떤 멤버가 필요한가?

---