icon안동민 개발노트

반복자

반복자의 개념

 반복자(Iterator)는 STL의 핵심 개념 중 하나로, 컨테이너의 요소에 접근하고 순회하는 일반화된 방법을 제공합니다. 포인터와 유사하게 동작하지만, 더 추상화되어 있어 다양한 컨테이너에 대해 일관된 인터페이스를 제공합니다.

 반복자의 주요 특징

  1. 컨테이너와 알고리즘을 연결하는 다리 역할
  2. 포인터와 유사한 동작 (*, ->, ++, -- 등의 연산자 지원)
  3. 컨테이너의 종류에 관계없이 일관된 사용법 제공

반복자의 종류

 STL은 다섯 가지 주요 반복자 카테고리를 정의합니다.

  1. 입력 반복자 (Input Iterator) : 읽기 전용, 순방향 이동만 가능
  2. 출력 반복자 (Output Iterator) : 쓰기 전용, 순방향 이동만 가능
  3. 순방향 반복자 (Forward Iterator) : 읽기/쓰기 가능, 순방향 이동
  4. 양방향 반복자 (Bidirectional Iterator) : 읽기/쓰기 가능, 양방향 이동
  5. 임의 접근 반복자 (Random Access Iterator) : 읽기/쓰기 가능, 임의 접근

 각 카테고리는 이전 카테고리의 기능을 포함하며 추가적인 기능을 제공합니다.

반복자 연산

 주요 반복자 연산을 살펴보겠습니다.

*it        // 반복자가 가리키는 요소에 접근
it->member // 반복자가 가리키는 요소의 멤버에 접근
++it       // 다음 요소로 이동 (전위 증가)
it++       // 다음 요소로 이동 (후위 증가)
--it       // 이전 요소로 이동 (양방향, 임의 접근 반복자)
it--       // 이전 요소로 이동 (양방향, 임의 접근 반복자)
it1 == it2 // 두 반복자가 같은 위치를 가리키는지 비교
it1 != it2 // 두 반복자가 다른 위치를 가리키는지 비교
it += n    // n만큼 전진 (임의 접근 반복자)
it -= n    // n만큼 후진 (임의 접근 반복자)
it1 - it2  // 두 반복자 사이의 거리 (임의 접근 반복자)

컨테이너와 반복자

 대부분의 STL 컨테이너는 다음과 같은 반복자 관련 멤버 함수를 제공합니다.

container.begin()  // 첫 번째 요소를 가리키는 반복자 반환
container.end()    // 마지막 요소의 다음을 가리키는 반복자 반환
container.rbegin() // 역방향 반복자의 시작 (마지막 요소)
container.rend()   // 역방향 반복자의 끝 (첫 번째 요소의 이전)
container.cbegin() // 상수 반복자의 시작
container.cend()   // 상수 반복자의 끝

반복자를 사용한 컨테이너 순회

 다양한 방법으로 컨테이너를 순회해보겠습니다.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
 
    // 1. 기본적인 for 루프를 사용한 순회
    std::cout << "Using basic for loop:" << std::endl;
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
 
    // 2. 범위 기반 for 루프를 사용한 순회
    std::cout << "Using range-based for loop:" << std::endl;
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
 
    // 3. 역방향 순회
    std::cout << "Reverse iteration:" << std::endl;
    for (std::vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;
 
    // 4. 상수 반복자를 사용한 순회
    std::cout << "Using const_iterator:" << std::endl;
    for (std::vector<int>::const_iterator cit = vec.cbegin(); cit != vec.cend(); ++cit) {
        std::cout << *cit << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

반복자와 알고리즘

 STL 알고리즘은 반복자를 사용하여 컨테이너의 요소에 접근합니다. 이를 통해 알고리즘이 특정 컨테이너에 종속되지 않고 일반화될 수 있습니다.

 예제 : std::find와 std::sort 알고리즘 사용

#include <iostream>
#include <vector>
#include <algorithm>
 
int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
 
    // std::find를 사용하여 요소 찾기
    auto it = std::find(vec.begin(), vec.end(), 5);
    if (it != vec.end()) {
        std::cout << "Found 5 at position: " << std::distance(vec.begin(), it) << std::endl;
    }
 
    // std::sort를 사용하여 벡터 정렬
    std::sort(vec.begin(), vec.end());
    
    std::cout << "Sorted vector: ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

반복자의 무효화

 컨테이너의 내용이 변경될 때 기존 반복자가 무효화될 수 있습니다. 이는 특히 동적 할당을 사용하는 컨테이너(예 : vector)에서 주의해야 합니다.

예제
// 예제
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> vec = {1, 2, 3};
    auto it = vec.begin();
    
    std::cout << "Before push_back: " << *it << std::endl;
    
    vec.push_back(4);  // 재할당 발생 가능
    // std::cout << "After push_back: " << *it << std::endl;  // 위험: it가 무효화되었을 수 있음
    
    it = vec.begin();  // 반복자 재설정
    std::cout << "After reset: " << *it << std::endl;
 
    return 0;
}

사용자 정의 반복자

 사용자 정의 컨테이너를 만들 때, 해당 컨테이너에 대한 반복자를 직접 구현할 수 있습니다. 다음은 간단한 링크드 리스트와 그에 대한 반복자의 예입니다.

#include <iostream>
 
template <typename T>
class LinkedList {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& d) : data(d), next(nullptr) {}
    };
 
    Node* head;
 
public:
    class Iterator {
    private:
        Node* current;
 
    public:
        Iterator(Node* node) : current(node) {}
        T& operator*() { return current->data; }
        Iterator& operator++() { current = current->next; return *this; }
        bool operator!=(const Iterator& other) { return current != other.current; }
    };
 
    LinkedList() : head(nullptr) {}
 
    void insert(const T& value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }
 
    Iterator begin() { return Iterator(head); }
    Iterator end() { return Iterator(nullptr); }
};
 
int main() {
    LinkedList<int> list;
    list.insert(3);
    list.insert(2);
    list.insert(1);
 
    for (auto it = list.begin(); it != list.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

연습 문제

  1. vector<int>를 생성하고, 반복자를 사용하여 모든 짝수 요소를 제거하는 프로그램을 작성하세요.
  2. list<string>을 만들고, 사용자로부터 입력받은 문자열을 알파벳 순서에 맞게 삽입하는 프로그램을 작성하세요. 반복자를 사용하여 적절한 삽입 위치를 찾으세요.
  3. map<string, int>을 사용하여 단어의 빈도수를 세는 프로그램을 작성하세요. 반복자를 사용하여 모든 단어와 그 빈도수를 출력하세요..

참고 자료

컨테이너 개요알고리즘