[C++][STL] 반복자(Iterator)

반복자(Iterator)란?

STL 구성 요소

• STL의 구성 요소(반복자, 컨테이너, 알고리즘) 중 하나.
  • STL은 Standard Template Library의 약자로, C++에서 템플릿을 이용해 정리해 둔 표준 라이브러리를 말한다.
• 반복자는 컨테이너(ex. vector, list)의 요소들을 순회하기 위해 사용하는 “래퍼 클래스”로, 포인터를 핵심 멤버로 가지면서 다양한 편의 기능과 안전장치를 추가한 클래스이다.
• 반복자는 기존 포인터와 동일한 방식으로 사용할 수 있는데, 이는 반복자 클래스 내부에 역참조(*)나 증감 연산자(it++, ++it) 등을 연산자 오버로딩 해두었기 때문이다.

 

왜 C++은 반복자를 만들었을까?

 

주요 목적. 컨테이너 순회의 일반화

• 가장 큰 목적은 "컨테이너의 내부 구조를 몰라도 같은 방식으로 순회하기 위해서"이다. 기존 포인터 방식은 메모리가 연속적일 때만 산술 연산(ptr++와 같이)을 통해 요소 이동이 가능하다는 한계점이 있다. 그래서 vector와 같이 메모리가 연속적인 컨테이너는 포인터만 있어도 순회가 가능하지만, list와 같이 메모리가 비연속적인 컨테이너는 포인터만으로는 순회가 불가능하여 next(), prev()와 같은 요소 이동 함수를 따로 정의해둬야 한다.
• list와 같이 메모리가 비연속적인 STL 컨테이너들은 map, set 등 여러 개 존재한다. 그럼에도 만약 C++ 이 반복자를 만들지 않고 기존 포인터 방식만 고수했다면 지금까지도 C++ 개발자들은 STL 컨테이너를 순회할 때마다 1) 메모리가 비연속적인지, 2) 비연속적이라면 요소 이동 함수 이름은 무엇인지 외웠어야 했을 것이다.
• 다행히 반복자가 등장하게 되면서, 컨테이너 내부 구조를 몰라도 순회할 땐 반복자만 사용하면 되는 편리한 상황이 되었다. 이에 대한 예제는 아래와 같다.

template <typename T>
void print_elements(T& container) {
    // vector와 list의 멤버 함수로 begin(), end()가 정의되어 있으며,
    // 각 함수는 반복자(iterator)를 반환.
    for (auto it = container.begin(); it != container.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> v = {1, 2, 3};
    std::list<int> l = {10, 20, 30};

    // 동일한 함수를 사용하여 서로 다른 구조의 컨테이너를 출력
    print_elements(v); // Vector 순회
    print_elements(l); // List 순회 (포인터였다면 불가능한 방식)

    return 0;
}

 

그 외 목적들

• 유지보수의 편의성: 반복자가 컨테이너 종류의 상관없이 순회 방식을 일반화함으로써 유지보수도 편리해졌다. 만약 성능 문제로 컨테이너를 vector에서 list로 바꿔야 하는 상황이 발생했다면? 포인터 방식을 사용했다면 순회 로직을 갈아엎어야 됐지만, 반복자 방식을 사용했다면 코드는 거의 수정할 필요가 없다.
• 안정성: 포인터는 메모리 주소에 직접 접근할 수 있는 아주 위험한 녀석이기 때문에 안전장치를 마련해 두는 것이 좋다. 반복자는 컨테이너 범위 내에서만 움직일 수 있도록 제어함으로써 이러한 안전장치의 역할을 하게 된다.
• 알고리즘의 재사용성: 알고리즘 함수를 만들 때도 컨테이너의 반복자를 인자로 전달받는 방식을 이용하면 모든 컨테이너가 알고리즘을 사용할 수 있는, 즉 알고리즘 재사용성이 높아진다. 대표적으로 STL algorithm의 알고리즘들(std::sort나 std::find 같은)이 있다. 예시는 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm> // 알고리즘 헤더

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};

    // v.begin()부터 v.end()까지의 범위에서 30을 찾음
    auto it = std::find(v.begin(), v.end(), 30);

    if (it != v.end()) {
        std::cout << "값 발견: " << *it << std::endl;
    } else {
        std::cout << "값을 찾지 못했습니다." << std::endl;
    }

    return 0;
}

 

 

반복자는 각 컨테이너 클래스 내부에 정의되어 있다.

• 반복자가 컨테이너 종류 상관없이 같은 방식으로 순회할 수 있도록 해준다고 하지만, 그렇다고 같은 반복자 클래스를 여러 컨테이너가 공유하는 것은 아니다. 각 컨테이너의 반복자는 서로 다른 클래스이며, 각 반복자는 컨테이너 클래스 내부에 정의되어 있다. 아래 예제를 보면 각 컨테이너의 반복자는 서로 다른 타입임을 알 수 있다.

std::vector<int> v = {1, 2, 3};
std::list<int> l = {1, 2, 3};

auto vit = v.begin(); // 타입: std::vector<int>::iterator
auto lit = l.begin(); // 타입: std::list<int>::iterator

// if (vit == lit) { ... } // 컴파일 에러! 서로 다른 타입은 비교할 수 없음
// vit = lit;             // 컴파일 에러! 대입할 수 없음

 

왜 반복자를 클래스 내부에 정의했을까?

• 캡슐화와 종속성을 부여하기 위해서다. 각 컨테이너가 반복자 클래스를 공유하지 않고, 오로지 자신만 사용한다면 굳이 외부에서 독립적으로 정의해 둘 필요가 있을까? 그럴 필요 없다. 오히려 접근 가능하도록 냅두면 잘못된 사용만 늘어날 뿐이다. 그래서 반복자 클래스는 각 컨테이너 내부에 정의해 둔다. 아래 예제와 같이 말이다.

template <typename T>
class vector {
    T* _first; // 데이터의 시작 지점 (주소)
    T* _last;  // 마지막 데이터 다음 지점 (주소)
    T* _end;   // 할당된 메모리의 끝 지점 (주소)
    
public:
    // 컨테이너 내부에 반복자 클래스가 정의됨 (중첩 클래스)
    class vector_iterator {
        T* ptr;
    public:
        T& operator*() { return *ptr; }
        vector_iterator& operator++() { ++ptr; return *this; }
        // ... 생략 ...
    };

    // std::vector<int>::iterator와 같은 외부 접근시 편리성을 위한 별칭 추가
    using iterator = vector_iterator<T>;

    iterator begin() { return iterator(_first); }
    iterator end() { return iterator(_end); }
};

• 위 예제 코드를 보면 알겠지만 컨테이너 내부에 iterator 타입 멤버 변수는 따로 두지 않는다. 대신 데이터의 주요 지점을 포인터 타입의 멤버 변수로 두고, begin(), end() 등 iterator 관련 함수를 호출할 때마다 포인터 변수를 감싼(wrap) 새로운 iterator 객체를 생성하고 반환한다.
  • 매번 반복자 객체가 생성된다고 하면 "무거운 작업이 아닐까?" 걱정이 될 수 있다. 하지만 성능 걱정을 안 해도 되는 게 1) 반복자 객체의 크기가 포인터와 별 차이 없고, 2) 최신 컴파일러의 경우 인라인(inline) 확장과 반환값 최적화(RVO)를 수행하기 때문에 매번 객체를 생성함에도 불구하고 비용이 굉장히 적다.

 

---

반복자 종류

 

iterator

• 기본 반복자 타입. 
• begin(), end() 함수가 iterator를 반환한다.
  • begin()는 첫 번째 원소를 가리키는 반복자를, end()는 마지막 원소 뒤를 가리키는 반복자를 반환한다.
  • begin(), end() 계열의 함수들은 반복자를 지원하는 각 컨테이너에 정의되어 있다.

vector<int> v1 = {1, 2, 3, 4, 5};

vector<int>::iterator it = v1.begin();
for(; it != v1.rend(); it++){
    cout << *it << ' ';
}
cout << '\n';

 

실행 결과

1 2 3 4 5

 

const _iterator

• const 포인터와 같은 역할을 한다. const_iterator가 가리키고 있는 원소의 값을 수정할 수 없다.
• cbegin(), cend()가 const_iterator를 반환한다.
  
  • 각각 begin()과 end()가 반환하는 반복자와 같은 곳을 가리킨다.

vector<int> v1 = {1, 2, 3, 4, 5};

vector<int>::const_iterator c_it = v1.cbegin();
// *c_itr = 10; // 식이 수정할 수 있는 lvalue여야 합니다.

 

reverse_iterator

• 거꾸로 이동하는 반복자.
• rbegin(), rend()가 reverse_iterator를 반환한다.
  • rbegin()는 마지막 원소를 가리키는 반복자를, rend()는 첫 번째 원소 앞을 가리키는 반복자를 반환한다.

vector<int> v1 = {1, 2, 3, 4, 5};

vector<int>::reverse_iterator r_it = v1.rbegin();
for(; r_it != v1.rend(); r_it++){
    cout << *r_it << ' ';
}
cout << '\n';

 

실행 결과

5 4 3 2 1

 

const_reverse_iterator

• const 속성을 가진 reverse_iterator 반복자.
• crbrgin(), crend()가 const_reverse_iterator를 반환한다.
  • 각각 rbegin()과 rend()가 반환하는 반복자와 같은 곳을 가리킨다.

vector<int> v1 = {1, 2, 3, 4, 5};

vector<int>::const_reverse_iterator cr_it = v1.crbegin();
for(; cr_it != v1.rend(); cr_it++){
    cout << *cr_it << ' ';
    // *cr_it = 10; // 식이 수정할 수 있는 lvalue여야 합니다.
}
cout << '\n';

 

실행결과

5 4 3 2 1

 

[C++11] 범위 기반 for문(range based for loop)

• C++11부터 범위 기반(range-based) for문이 생겼다.
• 범위 기반 for문은 컨테이너 원소를 for문으로 순차적으로 접근하려 할 때 보다 간단하게 표현할 수 있는 방식이다.

vector<int> v1 = {1, 2, 3, 4, 5};

// "기본적인" 범위 기반 for문(값을 복사하므로 원본은 수정 X)
for(int elem : v1){
    cout << elem << ' ';
}

// "레퍼런스를 사용한" 범위 기반 for문(자주 보이는 패턴)
for(const int& elem : v1){
    cout << elem << ' ';
}

// "auto 타입을 사용한" 범위 기반 for문(개인적으로 별로 안좋아하는 방식)
for(const auto& elem : v1){
    cout << elem << ' ';
}

 

---

커스텀 반복자 만들어보기 예제

#include <iostream>
#include <vector>
#include <initializer_list>

using namespace std;

class MyContainer {
private:
    std::vector<int> data;

public:
    MyContainer(std::initializer_list<int> init) : data(init) {}

public:
    // 반복자 정의(중첩 클래스)
    class Iterator {
    public:
        // STL 표준 관례에 따른 타입 정의 (알고리즘 연동 시 필요)
        using iterator_category = std::random_access_iterator_tag;
        using value_type = int;
        using pointer = int*;
        using reference = int&;

        Iterator(int* p) : ptr(p) {}

        /* 연산자 오버로딩 */
        int& operator*() const { return *ptr; }
        int* operator->() { return ptr; }
        
        Iterator& operator++() { ++ptr; return *this; }
        Iterator operator++(int) { Iterator temp = *this; ++ptr; return temp;} 
  
        // v.begin() + 6 과 같은 연산을 위한 산술 연산자 추가 (Random Access)
        Iterator operator+(int n) const { return Iterator(ptr + n); }
        Iterator operator-(int n) const { return Iterator(ptr - n); }

        bool operator==(const Iterator& other) const { return ptr == other.ptr; }
        bool operator!=(const Iterator& other) const { return ptr != other.ptr; }

    private:
        int* ptr;
    };

public:
    // 반복자 관련 함수
    Iterator begin() { return Iterator(data.data()); }
    Iterator end() { return Iterator(data.data() + data.size()); }

    void push_back(int val) {
        data.push_back(val);
    }
};

int main() {
    MyContainer container = {1, 2, 3, 4, 5};

    // 반복자 for 루프
    for (auto it = container.begin(); it != container.end(); ++it)
        cout << *it << " ";
    cout << '\n';

    // 범위 기반 for 루프
    for(auto it : container)
        cout << it << " ";
    cout << '\n';

    return 0;
}

 

실행결과

1 2 3 4 5
1 2 3 4 5

---

참고자료

https://modoocode.com/223