초보자를 위한 c++ STL 반복자(iterator) 정리

1)반복자란 무엇인가

앞서 array, vector, forward_list를 설명할 때 반복자(iterator)를 사용한 것을 기억하실 것입니다.

초보자를 위한 c++ STL array 정리

 

초보자를 위한 c++ STL vector 정리

 

초보자를 위한 C++ STL forward_list 정리

반복자는 포인터와 비슷하지만, STL 컨테이너에 대해 공통의 인터페이스를 제공하여 반복자를 이용한
연산을 하기 위해서는 어떤 컨테이너에서 정의된 반복자인지에 따라 정의됩니다. 또한 반복자는
벡터와 배열 같은 연속된 자료 구조에서 특정 위치의 원소에 곧바로 접근할 수 있기 때문에 유연하게
사용이 가능합니다. 이러한 반복자를 임의 접근 반복자(random access iterator)라고 합니다.
그러나 forward_list의 경우 기본적으로 역방향 이동을 제공하지 않기 때문에, 바로 이전 노드를
이동하기 위해서도 맨 처음 노드부터 시작해서 찾아야 합니다. 따라서 증가 연산만 가능하며,
이러한 반복자를 순방향 반복자(forward_iterator)라고 합니다.

 

2)반복자 타입에 따라 사용할 수 있는 함수

advance()	인자값으로 들어온 iterator를 원하는 위치로 옮길 수 있는 함수
next()	기준 iterator에서 원하는 거리(n차)의 iterator를 반환하는 함수
prev()	기준 iterator에서 원하는 거리(-n차) 거리의 iterator를 반환하는 함수

int main() {
	vector<int> vec{ 1,2,3,4,5 };

	vector<int>::iterator it = next(vec.begin(), 2); //+2차이의 거리의 값으로 반환
	vector<int>::iterator it2 = prev(vec.end(), 2); //-2차이의 거리의 값으로 반환

	vector<int>::iterator it3 = vec.begin();
	it3 += 2; //상수 시간
	advance(it3, 2); //+2차이의 거리의 값으로 변경

	cout << "next():" << *it << endl;
	cout << "prev():" << *it2 << endl;
	cout << "advance():" << *it3 << endl;

	advance(it3, -2); //-2차이의 거리의 값 으로 변경
	cout << "advance(-2):" << *it3 << endl;
}

next():3
prev():4
advance():5
advance(-2):3

vector같은 연속된 자료 구조에서는 상수 시간으로 값을 접근하며 iterator에 원하는 값을 +하여
이동시킬 수 있습니다. 또한 advance 함수를 사용할때는 앞으로도 이동(순방향)시킬 수도 있고
뒤로도 이동(역방향)시킬 수 있습니다.

int main() {
	forward_list<int> fwl{ 1,2,3,4,5 };

	forward_list<int>::iterator it = next(fwl.begin(), 2); //+2차이의 거리의 값으로 반환
	//forward_list<int>::iterator it2 = prev(fwl.end(), 2); //에러발생

	forward_list<int>::iterator it3 = fwl.begin();
	//it3 += 2; 에러 발생
	advance(it3, 2); //+2차이의 거리의 값으로 변경(선형 시간)

	cout << "next():" << *it << endl;
	cout << "prev():" << "Error" << endl;
	cout << "advance():" << *it3 << endl;

	//advance(it3, -2); //에러 발생
	cout << "advance(-2):" << "Error" << endl;
}

next():3
prev():Error
advance():3
advance(-2):Error

다만 forward_list는 순뱡향으로 연속적인 순회를 통해서만 특정 원소를 접근할 수 있기 때문에
it3 += 2; 같은 식에서도 에러가 나며 -n차이의 거리의 값을 반환하는 prev(-2)나 advance(iterator,-2)
같은 역방향으로 순회하는 함수에서도 에러가 발생하기 때문에 무조건 순방향으로 연속적으로 접근
할 수 있는 함수를 사용해야 합니다.

---

위 블로그의 내용은 코딩 테스트를 위한 자료 구조와 알고리즘 with c++를 참고하여 작성하였습니다.

https://product.kyobobook.co.kr/detail/S000001834528

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ | 존 캐리 - 교보문고