[STL] STL Iterator

2024.12.12 (강의), 13 (기록) 오늘은 그래도 강의가 들을만 했다!

Iterator

: pointer**와 비슷하게 container에 저장된 원소들을 참조할 때 사용되는 객체

container마다 제공되는 iterator의 종류가 다름 + 제공되는 연산도 다름.

**pointer : 주소값으로 움직이는 것이므로 종류가 없음. reference와 비슷하게 배열의 위치값 가리키고 있는 node 값에 접근하므로 이동이 가능함.

; RandomAccess Iterator에서 pointer에서 가능한 연산이 전부 가능한 이유?

= 제시된 container들이 메모리상에 연속적으로 자료들이 존재하기 때문임.

즉, reference 기반으로 움직이는 것이 가능해서 몇번째로 이동~ 이런 것들이 가능한 것이다.

 

Iterator Operation

• operation

distance(v.bigin(),it)  // 두 iterator 사이 거리 반환  
advance(it,3)        // it를 다음 3번째 iterator로 이동 (it가 움직이는 것) 때문에 viod사용
new_it = next(it, 3) // new_it에 it 다음 3번째 iterator 저장, it위치는 그대로, iterator
new_it = prev(it, 3) // new_it에 it 이전 3번째 iterator 저장, it위치는 그대로, iterator

// random access iterator는
// advance(it,3) -> it += 3, next(it, 3) -> it +3

• • • random access iterator : O(1)
    • otherwise : O(n)

​

Reverse_iterator

: 반대방향으로 진행하기 위한 iterator adaptor ( ∴ Bidirectinoal iterator부터 제공 )

container의 begin(), end()는 iterator type 반환, rbegin, rend는 reverse_iterator type 반환

++ reverse_it (역방향), --reverse_it(정방향)

// 연산이 되면 사용할 수 있고, 아니면 사용 불가능 ∴Bidirectional~ 가능함.
set<T>::iterator, list<T>::iterator // 한 덩어리 자체가 type, 길이가 기니까 auto 사용
set<T>::reverse_iterator, list<T>::reverse_iterator

 

​

Traverse

​	v.begin() ↓	(++) -----------①----------->						v.end() ↓
처음꺼 이전	시작 node	​	​	​	​	​	끝 node	마지막 다음
↑ v.begin()	<-----------②------------ (++)						↑ v.end()	​

​	① 정방향	② 역방향
순회	iterator for ( auto it = v.begin(); it != v.end(); ++it ){               /*process*/ } ​ ** 후위 i++: 임시 객체 생성 → 대입 → 처리 → 임시객체 파괴 과정 거침 전위 ++i: 이 과정 X => 보통 전위로 사용하는 것이 좋음.	iterator for ( auto it =v.end(); it != v.begin(); ){         --it;       /*process*/ } /*v.end는 마지막+1 ∴ 그 앞에서 시작해야되는데 그렇다고 end-1하면      begin에 문제가 생겨버림. */
		reverse_iterator for ( auto it = v.rbegin(); it != v.rend(); ++it ){ /*process*/ } // 그래서 보통 역순회는 이걸로 많이 사용함.
삭제	iterator for ( auto it = v.begin(); it != v.end(); ){ // 삭제는 ++i X        if ( condition to erase ) it = v.erase ( it );        else ++it // 그래서 여기에서 다음으로 넘어가도록 } // erase 하면 자동으로 다음으로 넘어가짐. 삭제O 자동 넘김, - 반환값 설정 후 지워진 다음값으로 반환되게 설정	iterator for ( auto it = v.begin(); it != v.end(); ){ --it; // 다음 node는 이미 한거라 --로 앞으로 넘어가기 if ( condition to erase ) it = v.erase ( it ); } // 이때는 반드시 iterator들어가야해서 reverse 지원X - 지워진 위치의 다음 위치를 반환하도록 되어있어서 -- 필수

​

Container 별 Iterator

vector	list ​
set/map ​ set, map은 트리이지만 우선순위 기준으로 탐색 가능함. 저장 자체가 Sequence 한 것은 아니고 iterator의 node가 우선순위기준으로 연결되어있어서 도회가 가능한것.	unordered_set, map ​ ​ ​   ​ ​ forward (단방향) 때문에 reverse 불가능 r.begin, r,end XXX

​

Iterator 성질

Continuous (vector, string …) ​ ​ ​ ​ ​ ​ ​ node를 추가 혹은 삭제할 때마다 마지막 node 의 위치 변동 → end의 위치도 계속 변동됨.

Node (list, set, map) ​ it 기록해두면 앞뒤 연결과 무관하게 항상 고정되어있음. 메모리상 띄엄띄엄 존재하고, begin, end, it 모두 결정되면 고정됨.

​

Iterator 초기화

: pointer(null값(0)초기화)와 달리 iterator은 null 값 존재X => 대신 end() 위치로 표현

container 멤버 함수, algorithm 함수에서도 원하는 결과를 찾지 못하면, 결과값이 없으면 end()가 반환됨.

​

∴ 값이 지워지면 it = s.end() 로 설정, it == s.end()이면 값이 없음을 판단

​

Iterator invalidation

list, set, map : iterator가 가리키는 element가 지워지지 않는 한 항상 유효함. (= 무효화 되는 겨우 거의 X)

= iterator를 기록하여 효율적인 활용이 가능함.