반복자(iterator) : 포인터를 추상화한 클래스 객체
반복자의 종류
- 입력 반복자(input_iterator)
- 출력 반복자(output_iterator)
- 순방향 반복자(forward_iterator)
- 양방향 반복자(bidirectional_iterator)
- 임의 접근 반복자(random_access_iterator)
삽입 반복자 : 순차열에 원소를 삽입(insert)할 수 있게 반복자를 변환하는 반복자 어댑터
반복자(iterator)
- 반복자가 가지는 기능은 아래의 표와 같다. (출처 : https://cplusplus.com/reference/iterator/)
- 입력, 출력 반복자 < 순방향 반복자 < 양방향 반복자 < 임의 접근 반복자 순으로 각 기능이 누적된다고 생각하면 된다.
반복자의 순차열, 구간
- 순차열(sequence) : 순서 있는 원소의 집합, 시작과 끝을 나타내는 반복자의 쌍으로 표현
- 구간(range) : 시작과 끝을 나타내는 반복자의 쌍으로 표현하는 것
- [begin, end) : 반개 구간이라고 하며, begin은 포함되고, end는 포함되지 않는 구간
X::iteartor && X::const_iterator
- 정방향 반복자 형식
#include <iostream>
using namespace std;
std::iterator : 정방향 반복자의 내장 형식, 반복자가 가리키는 원소 읽기,쓰기 가능
std::const_iterator : 정방향 반복자의 내장 형식, 반복자가 가리키는 원소 읽기,쓰기 가능- 앞서 작성한 컨테이너를 나눈것과 위의 그림과 같이 각 컨테이너에서 사용되는 반복자의 종류는 다르다.
- 양방향 반복자 : list, set, multiset, map, multimap
- 임의 접근 반복자 : vector, deque
- begin() : 컨테이너 순차열의 첫 원소를 가리키는 반복자를 반환
- end() : 컨테이너 순차열의 끝 표시(past-the-end)반복자를 반환
X::reverse_iterator && X::const_reverse_iterator
- 역방향 반복자 형식
#include <iostream>
using namespace std;
std::reverse_iterator : 역방향 반복자의 내장 형식, 반복자가 가리키는 원소 읽기,쓰기 가능
std::const_reverse_iterator : 역방향 반복자의 내장 형식, 반복자가 가리키는 원소 읽기,쓰기 가능- 정방향 반복자 형식과 동일한 기능 및 연산자를 가지고 있음
- 하지만 정방향 반복자와는 다르게, 역방향으로 동작
- 즉, 정방향 반복자의 begin() == 역방향 반복자의 end() 동일
- rbegin() : 컨테이너 순차열의 끝 표시(past-the-end)반복자를 반환
- rend() : 컨테이너 순차열의 첫 원소를 가리키는 반복자를 반환
- 그림에서 나타나듯이 역방향 반복자는 현재의 위치를 반환하지만 값을 확인하면 이전의 값을 반환
- 정방향 반복자로 포현한 순차열과 역방향 반복자로 표현한 순차열이 서로 같도록 하기 위함
삽입 반복자
- 기본적으로 덮어쓰기 모드로 동작
- 덮어쓰기 모드는 원소의 개수가 동일하지만, 삽입모드는 원소의 개수가 증가
inserter() : insert_iterator객체를 생성, 객체는 컨테이너의 insert() 멤버 함수를 호출해 삽입 모드로 동작하게 함
back_inserter() : back_insert_iterator객체를 생성, 객체는 컨테이너의 push_back() 멤버 함수를 호출해 뒤쪽에 추가(삽입)하게 함
front_inserter() : front_insert_iterator객체를 생성, 객체는 컨테이너의 push_front() 멤버 함수를 호출해 앞쪽에 추가(삽입)하게 함- 모든 컨테이너는 insert()함수를 제공하여 모두 inserter()를 사용할 수 있음
- 하지만 컨테이너에 따라서 제공되는 inserter()의 기능이 달라짐
- vector, deque, list가 back_inserter()를 사용가능
- deque, list가 front_inserter()를 사용가능
입/출력 스트림 반복자
- 스트림과 연결된 반복자
- 알고리즘이 스트림에 읽고 쓸 수 있게 하는 반복자 어댑터
istream_iteartor<T> : 입력 스트림과 연결된 반복자로 T형식의 값을 스트림에서 읽을 수 있음
ostream_iterator<T> : 출력 스트림과 연결된 반복자로 T형식의 값을 스트림에 쓸 수 있음
<예시>
copy(v.begin(), v.end(), ostream_iterator<int>(cout) -> cout에 [v.begin(), v.end())값을 출력시켜줌
copy(v.begin(), v.end(), istream_iterator<int>(cin) -> cin으로부터 [v.begin(), v.end())값을 입력받음반복자 특성과 보조 함수
- 반복자는 자신만의 특징을 가지며 이 특징을 저장하는 템플릿 클래스 : 반복자 특성(iterator traits)
advance(p,n) : 반복자를 p += n의 위치로 이동
n = distance(p1, p2) : n = p2 - p1 / n은 difference_type- Iterator Traits의 정의
template<class Iter>
struct Iterator_traits
{
typedef typename Iter::iterator_category iterator_category;
typedef typename Iter::value_type value_type;
typedef typename Iter::difference_type difference_type;
typedef typename Iter::pointer pointer;
typedef typename Iter::reference reference;
}- Iterator Tag의 정의
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag : public input_iterator_tag{};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};