[C++] iterator (반복자) vector와 list의 비교

개념

어떤 컨테이너(자료구조)에 접근하든 동일한 방법으로 접근하기 위해서 제공되는 객체.

반복자는 원소의 위치를 갖고 있는 포인터와 비슷한 형태이다.

 

반복자를 이해하기 위해 먼저 벡터와 리스트의 접근 방식을 비교해보자.

 

벡터는 배열 기반으므로 연속된 메모리 공간을 가지고 있다. 그래서 인덱스 연산으로 임의 접근이 가능하고, 인덱스에 넣은 값을 증가시키는 방식으로 순회도 가능하다. 모든 컨테이너에 이런 간단한 방식으로 접근이 가능하다면 반복자는 필요하지 않을 것이다. 하지만 컨테이너들마다 접근 방식이 다르다.

 

하지만 리스트는 우선 연속된 메모리 공간을 가지지 않기 때문에 벡터처럼 인덱스 로 접근하는 것이 불가능하다. 즉 다른 방법으로 순회를 해야 한다. 리스트는 현재 가리키고 있는 노드와 다음 노드의 주소를 알기 때문에 현재 노드를 다음 노드로 갱신하는 방식으로 순회를 진행한다.

 

요는 벡터와 리스트는 서로 다른 방법으로 내부의 요소들에 접근하기 때문에 반복자가 필요해진다.

반복자를 사용하게 되면 컨테이너의 내부 구조를 몰라도 쉽게 컨테이너를 순회하는게 가능해지며, 서로 다른 컨테이너에 통일된 인터페이스로 접근이 가능하다.

사용 방법

STL이 제공하는 컨테이너의 내부에는 각각의 접근 방식에 맞는 반복자가 정의되어 있는데 이 반복자를 통해 컨테이너의 위치를 받아와서 접근하고, 순회하는 것이 가능해진다.

vector<int> v;
 
v.push_back(1);
v.push_back(2);
v.push_back(3);
 
vector<int>::iterator iter_begin = v.begin(); // 첫번째 원소 위치
vector<int>::iterator iter_end = v.end(); // 마지막 원소 다음 위치
 
for (; iter_begin != iter_end; ++iter_begin) // 증감 연산자로 순회 가능
    cout << *iter_begin << endl;  // 포인터처럼 역참조 연산으로 실제 값을 참조한다.

 

내부 구조가 다른 리스트도 같은 방법으로 접근이 가능하다.

list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
 
 
list<int>::iterator iter_begin = l.begin();
list<int>::iterator iter_end = l.end();
 
for (; iter_begin != iter_end; ++iter_begin)
    cout << *iter_begin << endl;

반복자의 무효화

반복자를 사용하는 도중에 반복자가 가리키는 요소가 변경되는 경우 반복자가 무효화될 수 있다.

 

예) vector의 요소를 삭제하는 경우 (erase)

vector<int> v = { 1,2,3 };
 
vector<int>::iterator iter = v.begin();
iter++;
 
v.erase(iter);
cout << *iter << endl; // 반복자 무효화!

 

iter가 가리키는 2를 삭제하면 배열의 뒤에 있던 요소들이 앞으로 당겨지면서 iter와 iter 이후의 값들이 모두 변경되므로 삭제한 위치~끝의 반복자들은 전부 무효화된다.

 

erase()는 삭제한 요소의 다음 반복자를 반환하는데 이를 직접 받아서 반복자를 갱신해주는 경우 반복자의 무효화를 피할 수 있다.

vector<int> v = { 1,2,3 };
 
vector<int>::iterator iter = v.begin();
iter++;
 
iter = v.erase(iter); // 반복자를 갱신
cout << *iter << endl;

 

예) vector에 값을 삽입하는 경우

삽입도 마찬가지로 배열의 요소들이 전부 뒤로 밀리므로 삽입한 위치~끝의 반복자들이 전부 무효화된다.

 

이때 삽입한 위치의 앞에 있는 반복자들은 무효화되지 않지만 벡터의 공간이 부족해서 메모리 재할당이 일어나는 경우에는 모든 반복자들이 무효화된다.

 

예) list의 경우

list의 삽입 삭제는 다른 노드에 영향을 주지 않기 떄문에 삭제하는 곳 외에 다른 위치의 반복자를 무효화시키지 않는다.

출처: https://spenshi.tistory.com/entry/C-반복자iterator [Toast:티스토리]