[Coding Test] Coding Tips 3 : Iterator

삼성B형을 위한 코딩 팁 시리즈

Python 개발자의 PRO 취득을 위한 C++ 공부 여정

• [Coding Test] Coding Tips 1 : ABS(x) macro used in DFS
• [Coding Test] Coding Tips 2 : Priority Queue, Bit Operator
• [Coding Test] Coding Tips 3 : Iterator
• [Coding Test] Coding Tips 4 : algorithm library
• [Coding Test] Coding Tips 5 : 잡-Skill
• [Coding Test] Coding Tips 6 : vector, deque, list
• [Coding Test] Coding Tips 7 : hash

Iterator

Iterator 동작이 어떻게 이뤄지는지 알면 여러모로 편리하게 사용할 수 있다. list, set, map 등의 iterator 를 보관하고 있으면 O(1) 시간에 접근은 물론 O(1) 시간 복잡도로 삽입, 삭제가 가능하다.

operation

• distance(v.begin(), it) : 두 iterator 사이 거리 반환
• advance(it, 3) : Iterator를 다음 3번째 Iterator 로 이동
• new_it = next(it, 3) : new_it 에 it 다음 3번째 iterator 저장
• new_it = prev(it, 3) : new_it 에 it 이전 3번째 iterator 저장

random access iterator : O(1)

advance(it, 3) → it += 3 next(it, 3) → it + 3 (반환필요)

otherwise : O(n)

reverse_iterator

• 반대 방향으로 진행하기 위한 iterator adaptor
• rbegin(), rend() 는 reverse_iterator_type 반환하기 때문에 begin() 과 다름
• reverse iterator : ++ 연산으로 역방향 진행

Traverse

정방향 순회

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

vector<int> v;

int main(void) {

	for (auto it = v.begin(); it != v.end(); ++it) {
		/* process */
	}

	return 0;
}

역방향 순회

v.end() 로 부터 시작할 때에는 --it 를 내부에 넣는게 중요! 또한, reverse iterator 를 사용하면 임시 객체를 생성하는 작업이 수행되기 때문에 성능 이슈가 생길 수 있음.

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

vector<int> v;

int main(void) {

	/* iterator  */
	for (auto it = v.end(); it != v.begin();) {
		--it;
		/* process */
	}

	/* reverse_iterator */
	for (auto it = v.rbegin(); it != v.rend(); it++) {
		/* process */
	}

	return 0;
}

정방향 순회 삭제

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

vector<int> v;

int main(void) {

	/* iterator  */
	bool condition_to_erase = true;
	for (auto it = v.begin(); it != v.end();) {
		if (condition_to_erase) it = v.erase(it);
		else ++it;
	}

	return 0;
}

역방향 순회 삭제

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

vector<int> v;

int main(void) {

	/* iterator  */
	bool condition_to_erase = true;
	for (auto it = v.end(); it != v.begin();) {
		--it;
		if (condition_to_erase) it = v.erase(it);
	}

	return 0;
}

Container 별 Iterator

• vector : 배열에서 begin() / rbegin() ~ end() / rend()
• list : node 에서 begin() / rbegin() ~ end() / rend()
• set/map : Tree 형태로 이어져 우선 순위로 탐색 가능
• unordered_set/map : 순서대로 접근 가능하기 때문에 rbegin(), rend() 없음

→ Iterator 성질과 연결

Node 기반 list, set, map, … 등은 iterator 가 한 번 만들어지면 계속 고정이다.

이를 Iterator invalidation 이라 한다. id 별로 접근할 때, list, set, map 인 경우에는 삽입 후 id 와 iterator 를 연결해 사용하면 편하다. 그렇기 때문에 정렬 기준을 가진 set 과 iterator 기록을 통해 O(1) 시간 접근이 가능하다.

끝으로 iterator 는 end() 연산자로 초기화 시킬 수 있다.