Iterator
반복자는 컨테이너의 한 지점을 가리키는 객체이다.
Un itérateur est un objet qui
indique vers un point du conteneur.
컨테이너의 종류와 내부 구조에 상관없이 한 요소를 가리키는 목적으로 반복자라는 동일한 장치를 일관된 방법으로 사용할수있다.
Quels que soient le type et la structure
interne du conteneur, le même
dispositif appelé itérateur peut être utilisé
de manière cohérente dans le but de pointer
vers un élément.반복자의 종류
1. Input iterator
기본적인 기능만 제공하는 반복자이다.
- 한 위치를 가르킴
- 반복자가 가르키는 위치의 요소를 * 연산자로 읽을수있다.
- 요소를 변경하는것은 불가능하다.
- 끝낼시점을 결정하기위한 != 연산자.
a = *it; // 가능
*it = a; // 불가능
2. output iterator
- *연산자를 이용하여, 요소의 내용을 변경할수있다. (출력은 입력과 달리 무조건적이다)
- 전진할수있다. (++)
*it = a; // 가능
a = *it; // 필요하지않음
반복자 구간끼리 복사하는 copy알고리즘에 입력, 출력 반복자가 동시에 나타난다.
outPutIterator copy(
InPutIterator first,
InPutIterator last,
outPutIterator ret)
{
while (first != last)
*ret++ = *first++;
return (ret);
}3. foward iterator
- 읽기, 쓰기 모두 가능.
- 순방향으로 이동가능. ( it++, ++it )
- 같은 위치를 여러번 읽고 쓸수 있다. (search 함수)
void replace(FwdIt first,
FwdIt last,
Type const &old,
type const &new);
/*
컨테이너의 old값을 찾아서, new값으로 바꾼다.
그러므로, 읽기, 쓰기가 모두 필요하다.
또한, 대체 동작을 여러번 반복할 필요는 없으므로,
구간의 처음부터 끝까지 한번만 순회하면된다.
그러므로, 순방향 반복자가 필요하다.
*/4. bidirctional Iterator
- 읽기, 쓰기 모두가능.
- 양방향으로 이동가능. (++, --)
- 순방향반복자의 기능을 포함한다.
void reverse(BiIt first, BiIt lase);
/*
구간 내의 모든 요소들을 반대로 배치해야하므로, 양쪽 끝에서
동시에 순회를 하여, 값을 교환해야한다.
그러므로, 반복자가 증가, 감소 모두를 포함해야한다.
*/
5. random access iterator
- 양방향 반복자의 기능을 포함한다.
- 반복자에 임의 정수를 더하는 +n 연산을
제공한다. (컨테이너의 요소들이 선형적으로 배치되어있기때문)- 복합 대입 연산자를 지원한다.
반복자의 속성
알고리즘 함수들은 임의의 컨테이너에 대해 동작하므로,
반복자만 인수로 전달받을뿐 컨테이너에 대해서는 알지못한다.
반복자의 특성에는 반복자의 레벨(위의 5가지 구분)이
가장 중요하고, 그외 반복자가 가리키는 타입,
반복자의 거리를 표현하는 타입등 반복자와
관련된 타입정보들이 포함된다.이러한 반복자의 특징을 표현하기위해,
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_category와 value_type만 살펴보자!
- iterator_category:
// 모두 멤버를 가지지않고 타입만 정의하는 빈 클래스.
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 {};
- value_type :
템플릿 인수로 전달된다.
vector<int> myVector;
/*
여기서 int는 템플릿인수이며, 일반적으로 T로 표현된다.
또한 value_type은 T이다.
*/- 예)
class vector_iterator {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
// ...
}
class list_iterator {
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
// ...
}
vector<int>::iterator vit;
list<int>::iterator lit;
iterator_traits<vit>::iterator_category;
// 임의 접근이다.
iterator_traits<lit>::iterator_category;
// 양방향이다.
iterator_traits<vit>::value_type;
// 정수를 가리킨다.
-
예2)
int distance(Iter first, Iter last) { if (반복자가 입력용이면) { /* ++로 접근 */ } else { /* 임의 인덱스로 접근 */ }
etudiant_42