C++에서 반복자, iterator의 차이

 

연결된 구조, 연속된 구조에서 둘 다 반복자, iterator를 쓰지만 서로 다르게 구현되어 있다.

그도 그럴 것인게..

 

메모리 주소 접근 방식을 생각해보면 쉽다.

단일 메모리 블럭에 들어있는 주소에 접근과

여러 메모리 블럭에 퍼져있는 주소에 접근하는 것은 다를게 분명하기 때문이다.

 

배열이나 벡터에서 우리가 쓰는 iterator는 random access iterator라고 한다. 

임의의 위치에 바로 접근이 가능하다.

 

forward_list 에서 쓰는 iterator는 forward iterator라고 한다.

 

**하지만 양방향 연결리스트를 들어봤다면 bidirectional iterator도 있겠네라고 생각할 수 있다.

정확하게 맞다.

 

아무튼 위 연결된 구조 연속된 구조와 다르게 임의의 위치에 바로 접근이 불가능하다.

 

---

 

iterator type에 따라 사용할 수 있는 함수가 있는데

 

advance(), next(), prev() 함수에 대해 알아보자

 

advance()는 반복자와의 거리 값을 인자로 받고 반복자를 거리 값만큼 증가시키는 것이다.

next(), prev() 도 반복자와의 거리 값을 인자로 받지만  해당 반복자에서 지정한 거리만큼의 떨어진 위치의 반복자를 반환한다.

 

++ 당연히 forward_list에서는 prev()는 지원하지 않는다.

 

 

우선 임의 접근 반복자에 대해서는

advance()나 next(), prev() 자체에 대해서는 O(1)의 시간복잡도를 갖지만

 

나머지 반복자에 대해서는

주어진 거리만큼 포인터를 받아 이동해야하기 때문에 선형 시간복잡도 O(N)을 가진다.

 

 

어떤 방식으로 iterator가 반환되는지를 잘 알아보면 sort()의 종류가 왜 2개인지도 알 수 있다.

 

---

 

마지막으로 가장 중요한 것.

 

어떤 반복자든, iterator 는 메모리 주소를 가리키는 포인터를 이용해서 구현했기 때문에

컨테이너가 중간에 변경될 경우 정상적으로 작동하지 않는 경우가 생긴다.

 

즉, 특정 노드, 특정 원소를 가리키는 메모리 주소가 바뀌면 사용하던 반복자가 작동하지 않을 수 있다는 말이다.

 

vector의 push_back() 같은 경우

용량이 꽉차면

새로운 메모리 공간에 할당하고 기존의 모든 원소를 새 메모리 공간으로 복사한다고 했다.

즉, 기존의 벡터를 가리키는 iterator를 이용하게 된다면 정상적인 작동을 할 수 없다는 말이다.

새로운 메모리 공간으로 옮겼으니 새로운 메모리 주소를 가리키는 iterator를 사용해야할 것이다.

 

 

다시 vector에서 insert() 함수로 메모리 재할당이 필요하다면 역시나 기존 iterator는 invalid하게 되고

메모리 재할당이 필요하지 않더라도 해당 위치의 뒤에 원소들은 뒤로 밀려나기 때문에

기존의 iterator 또한 정상적으로 작동할 수 없다.

 

 

*** But

연속된 자료구조와는 다르게 삽입에도 기존의 iterator가 변함이 없는 연결리스트는

반복자를 그대로 써도 된다.

 

다만 삭제에서는 삭제된 원소를 가리키면 안되기에 그건 예외다.