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

Iterator(반복자)

---

• 반복자는 포인터와 비슷하지만, STL container에 대한 공통의 interface를 제공한다.
  • 반복자를 이용한 연산은 어떤 컨테이너에서 정의된 반복자인지에 따라 결정된다.
• 배열과 벡터의 경우 연속된 자료 구조를 사용하기 때문에 지정 위치의 원소에 바로 접근할 수 있다.
  • 이러한 반복자를 임의 접근 반복자(random access iterator)라고 한다.
• std::foward_list의 경우 역방향 이동을 제공하지 않으며, 이전 노드로 이동하려면 처음부터 다시 찾아가야 한다.
  • 증가 연산만 가능하며, 이러한 반복자를 순방향 반복자(foward iterator) 라고 한다.

반복자 타입에 따라 사용할 수 있는 함수

• advance()
  • 반복자와 거리 값을 인자로 받고, 반복자를 거리 값 만큼 증가시킨다.
• next(), prev()
  • 반복자와 거리 값을 인자로 받고, 해당 반복자에서 지정한 거리만큼 떨어진 위치의 반복자를 반환한다
  • 순방향 이동만 가능한 반복자에 대해 prev() 함수를 사용하면 에러가 발생한다.
• 함수의 동작시간은 반복자 타입에 따라 결정됨
  • 임의 접근 반복자에서는 덧셈과 뺄셈이 상수 시간으로 동작하므로, next(), prev()도 상수 시간으로 동작한다
    • O(1)
  • 나머지 타입의 반복자에서는 주어진 거리만큼 순방향 또는 역방향으로 이동해야 하므로, 선형 시간이 소요된다
    • O(n) (n : 순회할 횟수)

example 4: 다양한 반복자에서 이동하기

#include <iostream>
#include <forward_list>
#include <vector>

int main() {
    std::vector<std::string> vec = {
        "Lewis Hamilton", "Lewis Hamilton", "Nico Roseberg",
        "Sebastian Vettel", "Lewis Hamilton", "Sebastian Vettel",
        "Sevastian Vettel", "Sebastian Veteel", "Fernando Alonso"
    };

    // 상수 시간
    auto it = vec.begin();

    std::cout << "가장 최근 우승자: " << *it << std::endl;

    // 상수 시간
    it += 8;

    std::cout << "8년 전 우승자: " << *it << std::endl;

    // 상수 시간
    advance(it, -3);

    std::cout << "그후 3년 뒤 우승자: " << *it << std::endl;

    std::forward_list<std::string> fwd(vec.begin(), vec.end());

    auto it1 = fwd.begin();

    std::cout << "가장 최근 우승자: " << *it1 << std::endl;

    // 선형 시간
    advance(it1, 5);

    std::cout << "5년 전 우승자: " << *it1 << std::endl;

    return 0;
}

example 5: 기본적인 user defined container 만들기

#include <iostream>
#include <algorithm>

struct singly_ll_node
{
    int data;
    singly_ll_node* next;
};

class singly_ll
{
public:
    using node = singly_ll_node;
    using node_ptr = node*;

private:
    node_ptr head;

public:
    void push_front(int val)
    {
        auto new_node = new node {val, NULL};
        if(head != NULL)
            new_node->next = head;
        head = new_node;
    }

    void pop_front()
    {
        auto first = head;
        if(head)
        {
            head = head->next;
            delete first;
        }
    }

    struct singly_ll_iterator
    {
    private:
        node_ptr ptr;

    public:
        singly_ll_iterator(node_ptr p) : ptr(p) {}

        int& operator*() { return ptr->data; }

        node_ptr get() { return ptr; }

        // 선행 증가
        singly_ll_iterator& operator++()
        {
            ptr = ptr->next;

            return *this;
        }

        // 후행 증가
        singly_ll_iterator operator++(int)
        {
            singly_ll_iterator result = *this;
            ++(*this);

            return result;
        }

        friend bool operator==(const singly_ll_iterator& left, const singly_ll_iterator& right)
        {
            return left.ptr == right.ptr;
        }

        friend bool operator!=(const singly_ll_iterator& left, const singly_ll_iterator& right)
        {
            return left.ptr != right.ptr;
        }
    };

        singly_ll_iterator begin() { return singly_ll_iterator(head); }
        singly_ll_iterator end() { return singly_ll_iterator(NULL); }
        singly_ll_iterator begin() const { return singly_ll_iterator(head); }
        singly_ll_iterator end() const { return singly_ll_iterator(NULL); }

        singly_ll() = default;

        singly_ll(const singly_ll& other) : head(NULL)
        {
            if(other.head)
            {
                head = new node{0, NULL};
                auto cur = head;
                auto it = other.begin();

                while(true)
                {
                    cur->data = *it;

                    auto tmp = it;
                    ++tmp;
                    if(tmp == other.end())
                        break;

                    cur->next = new node{0, NULL};
                    cur = cur->next;
                    it = tmp;
                }
            }
        }

        singly_ll(const std::initializer_list<int>& ilist) : head(NULL)
        {
            for(auto it = std::rbegin(ilist); it != std::rend(ilist); it++)
                push_front(*it);
        }
};

int main()
{
    singly_ll sll = { 1, 2, 3 };
    sll.push_front(0);

    std::cout << "첫 번째 리스트 : ";
    for(auto i : sll)
        // 출력 : 0 1 2 3
        std::cout << i << " "; 
    std::cout << std::endl;

    auto sll2 = sll;
    sll2.push_front(-1);

    std::cout << "첫 번째 리스트를 복사한 후, 맨 앞에 -1을 추가 : ";

    for(auto i : sll2)
    // 출력 : -1 0 1 2 3
        std::cout << i << ' ';
    std::cout << std::endl;

    std::cout << "깊은 복사 후 첫 번째 리스트 : ";

    for(auto i : sll)
        // 출력 0 1 2 3
        std::cout << i << ' ';
    std::cout << std::endl;        
}