001_반복자 (iterator)

반복자 (Iterator)

STL 에서 반복자 (Iterator)란 STL 컨테이너에 저장된 요소를 반복적으로 순회하여, 각각의 요소에 대한 접근을 제공하는 객체로 포인터와 매우 비슷하다. 즉, 컨테이너의 구조나 요소의 타입과는 상관없이 컨테이너에 저장된 데이터를 순회하는 과정을 일반화한 표현이다. 템플릿이 타입과 상관없이 알고리즘을 표현할 수 있게 해준다면, 반복자는 컨테이너와 상관없이 알고리즘을 표현할 수 있게 해준다.

반복자가 가져야할 요구 사항과 정의되어야 할 연산자는 다음과 같다.

가리키는 요소의 값에 접근할 수 있어야 한다. 따라서 참조 연산자 * 가 정의되어야 한다.
반복자 사이의 대입 연산, 비교 연산이 가능해야 한다. 따라서 대입, 관계 연산자가 정의되어야 한다.
기리키는 요소의 주변 요소로 이동할 수 있어야 한다. 따라서 증가 연산자 ++ 가 정의되어야 한다.

반복자의 종류

5종류의 반복자가 있다.

입력 반복자 (Input Iterator) 읽기만 가능, 순방향 이동, 현 위치의 원소를 한 번만 읽을 수 있음
출력 반복자 (Output Iterator) 쓰기만 가능, 순방향 이동, 현 위치의 원소를 한 번만 쓸 수 있음
순방향 반복자 (Forward Iterator) 읽기/쓰기 모두 가능, 순방향 이동 ++ 이 가능한 재할당 될 수 있는 반복자
양방향 반복자 (Bidirectional Iterator) 읽기/쓰기 모두 가능, 순방향 이동 ++, 역방향 이동 -- 이 가능
임의 접근 반복자 (Random Access Iterator) 읽기/쓰기 모두 가능, 임의 접근, 양방향 반복자 기능에 +, -, +=, -=, [] 연산이 가능

모든 컨테이너는 양방향 반복자 이상을 제공하며, 배열 기반 컨테이너인 std::vector, std::deque 는 임의 접근 반복자를 제공한다.

반복자 종류	사용 방식	읽기	접근	쓰기	증감	비교
입력 반복자	`istream_iterator`	`=*p`	`->`		`++`	`==` `!=`
출력 반복자	`ostream_iterator` `inserter` `front_inserter` `back_inserter`			`=*p`	`++`
순방향 반복자		`=*p`	`->`	`=*p`	`++`	`==` `!=`
양방향 반복자	`std::list` `std::set`, `std::multiset` `std::map`, `std::multimap`	`=*p`	`->`	`=*p`	`++` `--`	`==` `!=`
임의접근 반복자	일반 포인터 `std::vector` `std::deque`	`=*p`	`->` `[]`	`=*p`	`++` `--`
`+` `-` `+=` `-=`	`==` `!=
< >`
`<=` `>=`