[C++/STL] Iterator

Iterator

포인터와 비슷하게 컨테이너에 저장된 원소들을 참조할 때 사용되는 객체

 

 

Iterator Operation

Operation	설명
distance(v.begin(), it)	두 iterator 사이 거리 반환
advance(it, 3)	it를 다음 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의 사칙 연산
Random Access Iterator는 +, - 연산을 통해 이동이 가능하며 O(1)로 수행된다.
(다른 iterator는 loop 돌며 O(n)으로 수행 )

advance(it, 3) → it += 3
next(it, 3) → it + 3

 

 

reverse iterator

반대 방향으로 진행하기 위한 iterator adaptor
Bidirectional Iterator 부터 제공

 

 

 

Traverse

정방향 순회

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

 

역방향 순회

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

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

 

정방향 순회 삭제

for (auto it = v.begin(); it != v.end();) {
    if (condition to erase) it = v.erase(it);
    else ++it;
}

 

역방향 순회 삭제

for(auto it = v.end(); it != v.begin();) {
    --it;
    if (condition to erase) it = v.erase(it);
}

 

 

 

컨테이너별 Iterator

vector	list

 

set/map	unordered_set/map

 

 

Iterator Invalidation

list, set, map은 iterator가 가리키는 element가 지워지지 않는 한, 항상 유효하다.
iterator를 기록하여 효율적인 활용이 가능하다.