Skip to content

18. STL 반복자(STL Iterator)

1. 키워드

  • STL 반복자(STL Iterator)
  • STL(Standard Template Library)
  • 반복자(Iterator), 컨테이너(Container), 알고리즘(Algorithm)
  • 입력 반복자(Input Iterator)
  • 출력 반복자(Output Iterator)
  • 순방향 반복자(Forward Iterator)
  • 양방향 반복자(Bidirectional Iterator)
  • 임의 접근 반복자(Random Access Iterator)
  • iterator 헤더 파일
  • 스트림 반복자(Stream Iterator)
  • 삽입 반복자(Insert Iterator)
  • 역방향 반복자(Reverse Iterator)
  • 상수 반복자(Constant Iterator)


2. 반복자

1) STL

  • C++이 가지는 프로그래밍 언어로서의 특징 중 하나로 일반화 프로그래밍을 들 수 있다.
  • 이러한 일반화 프로그래밍은 데이터를 중시하는 OOP와는 달리 프로그램의 알고리즘에 그 중점을 둔다.
  • C++ 표준 템플릿 라이브러리인 STL도 이러한 일반화 프로그래밍 패러다임의 한 축을 담당하고 있다.
  • STL은 알고리즘을 일반화한 표현을 제공하며, 데이터의 추상화와 코드를 재활용할 수 있게 한다.


2) STL의 구성 요소

  • C++ 표준 템플릿 라이브러리인 STL은 다음과 같은 구성 요소로 이루어진 템플릿을 제공한다.


1] 반복자

2] 컨테이너

3] 알고리즘


3) 컨테이너

  • STL에서 컨테이너는 같은 타입의 여러 객체를 저장하는 일종의 집합이라 할 수 있다.
  • 컨테이너는 클래스 템플릿으로, 컨테이너 변수를 선언할 때 컨테이너에 포함할 요소의 타입을 명시할 수 있다.


4) 반복자

  • 반복자란 STL 컨테이너에 저장된 요소를 반복적으로 순회하여, 각각의 요소에 대한 접근을 제공하는 객체이다.
  • 즉, 컨테이너의 구조나 요소의 타입과는 상관없이 컨테이너에 저장된 데이터를 순회하는 과정을 일반화한 표현이다.
  • 템플릿이 타입과 상관없이 알고리즘을 표현할 수 있게 해준다면, 반복자는 컨테이너와 상관없이 알고리즘을 표현할 수 있게 해주는 것이다.
  • 반복자가 가져야 할 요구 사항과 정의되어야 할 연산자는 다음과 같다.


1] 가리키는 요소의 값에 접근할 수 있어야 하기 때문에 *(참조 연산자)가 정의되어야 한다.

2] 반복자 사이의 대입 연산, 비교 연산이 가능해야 하기 때문에 =(대입 연산자) 및 관계 연산자가 정의되어야 한다.

3] 가리키는 요소의 주변 요소로 이동할 수 있어야 하기 때문에 ++(증가 연산자)가 정의되어야 한다.


  • 위와 같은 요구 사항을 모두 갖춰야만 STL 알고리즘에서 반복자로 사용될 수 있다.
  • 참고로 반복자는 포인터를 일반화한 것으로, 포인터는 반복자가 가져야 할 모든 요구 사항을 만족한다.


3. 반복자의 종류

1) 반복자의 종류

  • STL은 제공하는 기능에 따라 반복자를 다음과 같이 다섯 가지로 분류하고 있다.


1] 입력 반복자

2] 출력 반복자

3] 순방향 반복자

4] 양방향 반복자

5] 임의 접근 반복자


(1) 입력 반복자

  • 입력 반복자는 가장 단순한 형태의 반복자로, 컨테이너로부터 값을 읽는 데 사용된다.
  • 입력 반복자를 사용하면 컨테이너로부터 값을 읽을 수는 있지만, 프로그램이 그 값을 변경할 수는 없다.
  • 따라서 이 반복자는 읽기 전용 알고리즘에서 사용할 수 있다.


  • 입력 반복자는 ++를 사용하여 순방향으로만 이동할 수 있다.
  • 또한, *를 사용하여 반복해서 요소를 참조할 수 있다.


  • 다음의 코드는 순차 검색을 통해 컨테이너에 포함된 특정 값을 찾아내는 Find() 함수의 원형을 보여준다.


template <class InputIterator, class T>
InputIterator Find(InputIterator first, InputIterator last, const T &value);


(2) 출력 반복자

  • 출력 반복자는 입력 반복자와는 반대로 컨테이너의 값을 변경하는 데 사용된다.
  • 출력 반복자를 사용하면 컨테이너의 값을 변경할 수는 있지만, 프로그램에서 값을 읽을 수는 없다.
  • 따라서 이 반복자는 쓰기 전용 알고리즘에 사용할 수 있다.


  • 출력 반복자는 ++를 사용하여 순방향으로만 이동할 수 있다.
  • 또한, *를 사용하여 단 한 번만 요소에 값을 쓸 수 있다.


  • 다음의 코드는 한 컨테이너에서 다른 컨테이너로 값을 복사하는 Copy() 함수의 원형을 보여준다.


template<class InputIterator, class OutputIterator>
OutputIterator Copy(InputIterator first, InputIterator last, OutputIterator result);


  • 참고로 입력 반복자와 출력 반복자는 입출력 스트림에만 적용된다.


(3) 순방향 반복자

  • 순방향 반복자는 입출력이 모두 가능한 반복자이다.
  • 따라서 이 반복자는 다중 패스 알고리즘에 사용할 수 있다.


  • 순방향 반복자는 ++를 사용하여 순방향으로만 이동할 수 있다.
  • 또한, *를 사용하여 몇 번이고 반복해서 같은 요소를 참조하거나, 그 값을 변경할 수 있다.
  • 즉, 순방향 반복자는 입력 반복자와 출력 반복자의 기능을 모두 포함하고 있다.


  • 다음의 코드는 특정 값을 찾아 다른 값으로 변경하는 Replace() 함수의 원형을 보여준다.


template<class ForwardIterator, class T>
void Replace(ForwardIterator first, ForwardIterator last, const T &target, const T &replacement);


(4) 양방향 반복자

  • 양방향 반복자는 입출력이 모두 가능한 반복자이다.


  • 양방향 반복자는 ++를 사용하면 순방향으로, --를 사용하면 역방향으로도 이동할 수 있다.
  • 또한, *를 사용하여 몇 번이고 반복해서 같은 요소를 참조하거나, 그 값을 변경할 수 있다.
  • 즉, 양방향 반복자는 순방향 반복자의 기능을 모두 포함하고 있다.


  • 다음의 코드는 특정 컨테이너의 모든 값을 거꾸로 새로운 컨테이너에 옮기는 Reverse() 함수의 원형을 보여준다.


template<class BidirectionalIterator, class OutputIterator>
OutputIterator Reverse(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);


(5) 임의 접근 반복자

  • 임의 접근 반복자는 최상위 레벨의 반복자로서 가장 많은 기능을 제공한다.


  • 임의 접근 반복자는 양방향 반복자의 모든 기능을 포함하고 있으며, [](첨자 연산자)를 통해 임의의 요소에 접근할 수 있다.
  • 또한, 증감 연산자를 통해 양방향으로 이동할 수 있으며, 요소의 순서를 결정하기 위해 관계 연산자를 사용할 수 있다.
  • 즉, 임의 접근 반복자는 양방향 반복자의 모든 기능과 함께 기존의 일반 포인터가 하는 거의 모든 일을 할 수 있다.


  • 다음의 코드는 특정 컨테이너의 모든 값을 정렬시키는 Sort() 함수의 원형을 보여준다.


template<class RandomAccessIterator>
void Sort(RandomAccessIterator first, RandomAccessIterator last);


2) 반복자 계층

  • STL의 반복자는 계층적으로 분류된다.
  • 예를 들어, 순방향 반복자는 입력 반복자와 출력 반복자의 모든 기능을 포함하고 거기에 자신만의 기능을 추가한다.
  • 이렇게 다양한 반복자를 사용하는 이유는 알고리즘의 적용 조건을 제한하기 위해서이다.
  • 즉, 양방향 반복자는 임의 접근 반복자에 기초하는 알고리즘은 사용할 수 없지만, 자신보다 하위 계층의 반복자에 기초하는 알고리즘은 사용할 수 있는 것이다.


  • 다음 표는 STL 주요 반복자의 기능을 계층 순으로 정리한 것이다.


반복자의 기능 입력 출력 순방향 양방향 임의 접근
접근(->) O X O O O
읽기(*) O X O O O
쓰기(*) X O O O O
증가 연산자(++) O O O O O
감소 연산자(--) X X X O O
첨자 연산자([]) X X X X O
산술 연산자(+, -) X X X X O
산술 대입 연산자(+=, -=) X X X X O
관계 연산자(<, <=, >, >=) X X X X O


4. 기타 반복자

1) iterator 헤더 파일

  • STL은 iterator 헤더 파일을 통해 미리 정의된 몇 가지 반복자를 제공한다.
  • 이 헤더 파일은 미리 정의된 반복자뿐만 아니라 스트림 반복자, 반복자의 원형 그리고 여러 지원 템플릿을 포함하고 있다.


2) 스트림 반복자

  • 스트림 반복자는 반복자 연산을 통해 알고리즘이 입출력 스트림에 보다 쉽게 접근할 수 있게 해준다.
  • 이때 STL은 입력과 출력 스트림을 각각 입력과 출력 반복자로 변환하는 방식으로 제공한다.
  • 입력 스트림 반복자는 istream_iterator, 출력 스트림 반복자는 ostream_iterator 클래스 템플릿에서 제공한다.


  • istream_iterator 클래스 템플릿은 다음과 같이 정의된다.


template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
class istream_iterator : public iterator<input_iterator_tag, T, Distance, const T *, const T &> { ... }


  • ostream_iterator 클래스 템플릿은 다음과 같이 정의된다.


template <class T, class charT = char, class traits = char_traits<charT> >
class ostream_iterator : public iterator<output_iterator_tag, void, void, void, void> { ... }


  • istream_iterator와 ostream_iterator 클래스 템플릿은 첫 번째를 제외한 인수에 모두 디폴트 인수를 명시하고 있다.
  • 따라서 사용자는 입출력하고자 하는 데이터의 타입만을 인수로 전달하여 간편하게 사용할 수 있다.


  • 다음의 코드는 copy() 함수를 사용하여 vector 객체의 첫 요소부터 마지막 요소까지를 모두 출력하는 것이다.


#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main(void) {
    vector<int> vc = {1, 2, 3, 4, 5};
    copy(vc.begin(), vc.end(), ostream_iterator<int>(cout));
    cout << endl;
    copy(vc.begin(), vc.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

// 12345
// 1 2 3 4 5


  • 위의 코드에서는 C++ 표준 출력 객체인 cout 객체를 ostream_iterator 클래스 템플릿의 인수로 전달하여 모니터에 대한 출력을 수행한다.


3) 삽입 반복자

  • 알고리즘에서 출력 반복자를 사용하면 반복자가 가리키는 요소의 값을 덮어쓰게 된다.
  • 하지만 삽입 반복자는 값을 덮어쓰지 않고, 그 요소의 위치에 새로운 값을 삽입할 수 있게 해준다.
  • 즉, 삽입 반복자는 반복자의 복사 연산을 삽입 연산으로 변환해 주는 역할을 한다.
  • STL에서 제공하는 삽입 반복자는 다음과 같다.


1] insert_iterator

2] back_insert_iterator

3] front_insert_iterator


삽입 반복자 설명 사용 멤버 함수 사용가능 컨테이너
insert_iterator 해당 컨테이너의 특정 위치에 삽입함 insert() 모든 컨테이너
back_insert_iterator 해당 컨테이너의 뒤쪽에 삽입함 push_back() 시퀀스 컨테이너
(vector, list, deque)
front_insert_iterator 해당 컨테이너의 앞쪽에 삽입함 push_front() list, deque


  • 다음의 코드는 push_back() 함수와 push_front() 함수의 삽입 반복자를 사용하여 리스트에 요소를 삽입하는 것이다.


#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main(void) {
    list<int> ls = {10};
    ls.push_back(20);   // back_insert_iterator를 사용함
    ls.push_front(30);  // front_insert_iterator를 사용함
    copy(ls.begin(), ls.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

// 30 10 20


4) 역방향 반복자

  • 역방향 반복자는 순방향 반복자와는 반대 방향으로 동작하는 반복자이다.
  • 즉, 역방향 반복자의 ++는 순방향 반복자의 역방향으로 이동하게 된다.
  • rbegin()과 rend() 멤버 함수를 사용하면 자동으로 reverse_iterator를 반환한다.


  • 다음의 코드는 rbegin()과 rend() 함수의 역방향 반복자를 사용하여 리스트의 요소를 역순으로 출력하는 것이다.


#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main(void) {
    list<int> ls = {10, 20, 30};
    copy(ls.rbegin(), ls.rend(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

// 30 20 10


5) 상수 반복자

  • 앞서 살펴본 것처럼 반복자를 동작 방식으로 분류하는 것 외에도 반복자가 가리키는 값의 변경이 가능한가로 분류할 수도 있다.
  • 이때 반복자가 가리키는 값의 변경이 불가능한 반복자를 상수 반복자라고 한다.
  • 단, 상수 반복자란 가리키는 요소를 상수화시킨 것이지 반복자 그 자체를 상수화시킨 것은 아니다.
  • 따라서 양방향 상수 반복자라면 앞뒤로 이동하며 다른 요소를 가리키는 것이 가능하다.
  • 이러한 상수 반복자의 타입은 const_iterator 타입으로 정의된다.


  • 다음의 코드는 반복자를 사용하여 list의 첫 번째 요소의 값을 변경하는 것이다.


#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main(void) {
    list<int> ls = {10, 20, 30};
    list<int>::iterator iter;
    list<int>::const_iterator citer;

    iter = ls.begin();
    *iter = 100;
    citer = ls.end();
    // *citer = 300; // 상수 반복자이므로 값의 변경은 불가능함

    for (citer = ls.begin(); citer != ls.end(); citer++) {
        cout << *citer << " ";
    }
    cout << endl;

    return 0;
}

// 100 20 30


  • 위의 코드에서 상수 반복자로 선언된 citer는 가리키는 값의 변경이 불가능하며, 값을 읽는 작업에만 사용할 수 있다.

References