Chapter8. 반복자
C++은 템플릿 기반의 컨테이너(자료구조)를 제공하고 컨테이너의 항목들에 범용적인 접근 방법을 제공하기 위해 반복자 패턴을 채용하고 있다. 각 컨테이너는 그 컨테이너만의 반복자를 지원하며, 반복자는 특정 컨테이너의 항목을 어떻게 순회할지 알고 있는 포인터 객체이다. 이들은 C++ 표준에서 정하고 있는 공용 인터페이스를 따르고 있어, 일관된 방법으로 각 컨테이너를 순회할 수 있도록 해준다.
C++ STL(Standard Template Library)에 포함된 알고리즘들 또한 대부분 반복자들을 파라미터로 받아 작동하며, 각 컨테이너의 구조에 종속되지 않게 구현되어 있다.
C++ 표준에서는 반복자를 다섯가지의 카테고리로 분류한다.
| 반복자 기능 | 입력 반복자 | 순방향 반복자 | 양방향 반복자 | 임의 접근 반복자 |
|---|---|---|---|---|
| 접근 (operator->) | O | X | O | O |
| 읽기 (operator*) | O | X | O | O |
| 쓰기 (operator*) | X | O | O | O |
| 증가 (operator++) | O | O | O | O |
| 감소 (operator--) | X | X | X | O |
| 인덱스 (operator[]) | X | X | X | O |
| 산술 연산 (operator+, operator-) | X | X | X | X |
| 산술 대입 연산 (operator+=, operator-=) | X | X | X | X |
| 대소 비교 연산 (operator<, <=, >, >=) | X | X | X | X |
입력 반복자는 입력스트림에서, 출력 반복자는 출력 스트림에서만 쓰입니다. 각각 입력 전용, 출력 전용 반복자이며 기능이 상당히 제한적이다.
순차 컨테이너, 연관 컨테이너, 비순차 컨테이너 등은 순방향, 양방향, 임의 접근 반복자 중 하나를 지원하지만 컨테이너 어댑터 클래스 (다른 컨테이너를 활용하여 새로운 인터페이스를 구현한 것)와 bitset(비트열을 이용해 중복 원소가 없는 집합을 표현) 클래스는 반복자를 지원하지 않는다.
반복자에 대한 증감, 산술, 대소비교 등은 반복자가 순회하는 항목의 순열 안에서 반복자의 위치에 대해 수행되는 연산이다. 이를 통해 반복자가 가리키는 항목을 변경하거나 서로 다른 두 반복자에 대하여 항목열에서의 선후 관계를 비교할 수 있다.
반복자를 지원하는 컨테이너는 typedef로 반복자 타입을 정의하고 있는데 iterator, const_iterator, reverse_iterator, const_reverse_iterator와 같은 이름으로 정의되어 있다. iterator와 const_iterator는 순방향이 + 방향으로 취급되는 반복자이며 reverse_iterator와 const_iterator는 역방향이 +방향으로 취급되는 반복자이다. const_iterator와 const_reverse_iterator는 가리키고 있는 항목을 변조할 수 없는 반복자이다.
vector<int> v;
vector<int>::iterator iter = v.begin();
vector<int>::const_iterator cIter = v.cbegin(); //cIter를 통해 대상 변경 불가
vector<int>::reverse_iterator rIter = v.rbegin(); //항목열을 역순으로 순회(++연산시 이전 항목)
vector<int>::const_reverse_iterator crIter = v.crbegin(); //const이면서 reverse인 반복자위에 코드에서처럼 각 컨테이너는 이터레이터를 반환하는 메서드를 제공한다.
vector<int> v {1,2,3,4,5};
for (auto iter = v.begin(); iter != v.end(); ++iter)
cout << *iter << ' '; //output: 1 2 3 4 5
for (auto rIter = v.begin(); rIter != v.rend(); ++rIter)
cout << *rIter << ' '; //output: 5 4 3 2 1end 메서드는 마지막 항목을 가리키는 반복자를 반환한다. 즉 유효하지 않은 대상을 가리키는데, C++의 반복자는 반개방형으로 디자인 되었기 때문이다. 마찬가리로 rend 메서드는 첫번째 항목 이전 항목을 가리키는 반복자를 반환한다.
reverse_iterator나 const_reverse_iterator는 base메서드로 reverse 속성을 제거할 수 있다. 이때 가리키는 항목이 그대로인 것이 아니라 원래 가리키던 항목의 바로 다음 항목을 가리키도록 바뀌게 된다. 따라서 rend().base()는 begin()과 같고 rbegin().base()는 end()와 같다.
reverse_iterator의 생성자 중 iterator를 파라미터로 받는 버전이 있는데 이를 통해 iterator에 reverse 속성을 추가한 반복자를 얻을 수도 있다. 이때는 반대로 원래 가리키던 항목의 바로 이전 항목을 가리키도록 바뀌게 된다. 따라서 reverse_iterator(v.begin())는 v.rend()와 같고 reverse_iterator(v.end())는 v.rbegin()과 같다.
vector<int> v{ 1,2,3,4,5 };
cout << boolalpha; //bool 출력을 알파벳으로 하게 하는 매니퓰레이터
cout << (v.rend().base() == v.begin()) << endl; //true
cout << (v.rbegin().base() == v.end()) << endl; //true
cout << (vector<int>::reverse_iterator(v.begin()) == v.rend()) << endl; //true
cout << (vector<int>::reverse_iterator(v.end() == v.rbegin()) << endl; //true;반복자를 복사하여 따로 관리할 수도 있으나 이때는 반복자 무효화 현상에 유의할 필요가 있다. 반복자는 포인터와 다를 바 없이 가리키는 대상이 다른 곳으로 이동하거나 소멸하더라도 그 사실을 알지 못한다.
vector<int> v{ 1,2,3,4,5 };
auto iter = v.end();
--iter; //5를 가리킨
v.pop_back();
cout << *iter; //out of range위와 같이 대상 컨테이너의 항목열이 변화하면서 기존에 저장해두었던 반복자는 범위를 벗어나거나 다른 항목을 가리키게 될 수 있다. 심지어 컨테이너의 작동 방식을 제대로 알지 못하면 반복자가 무효화되지 않았다고 오해할 수도 있다.
vector<int> v{ 1 };
auto iter = v.begin();
v.push_back(2);
cout << *iter; //버그위 코드에서 기존 항목열에 새로운 항목열을 추가했을 뿐이므로 첫 번째 항목을 가리키고 있던 반복자 iter는 여전히 유효할 것이라고 생각하기 쉽다. 그러나 벡터의 동작 방식을 이해하면 위 코드는 무효화된 반복자에 접근하고 있는 위험한 코드임을 알 수 있다.
- 벡터의 동작 방식
벡터는 동적 배열을 구현한 컨테이너 클래스로서 힙 메모리 상에서 연속적인 메모리 공간을 할당받아 사용한다. 그래야만 산술 연산자를 통해 주소를 계산하는 랜덤 액세스를 제공할 수 있기 때문이다.
그런데 힙 메모리는 무한하지 않고 가용 메모리들은 파편화되어 있다. 그렇기 때문에 제자리에서 크기를 키우는데 한계가 생기면 전체 항목열을 더 넓은 가용 메모리로 복사해서 옮기고 확장하게 된다. 이때 항목열을 옮기지 않고 확장 가능한 크기를 capacity라고 하며 셀제로 사용중인 항목열의 크기를 size라고 한다. capacity를 예약된 메모리 크기라고 생각해도 좋다.
컴파일러의 구현에 따라 capacity가 어떤식으로 확장될 지 다를 수 있지만 size가 작을 때는 capacity를 조금씩 키우고 size가 클 때는 capacity도 더 큰 폭으로 증가한다. 일반적으로 zero 사이즈에서 항목을 하나씩 추가한다면 0->1->2->4->8->16->... 과 같이 capacity가 증가한다.
또한 벡터는 처음 생성될 때 size와 capacity가 같도록 생성된다. 즉 위 코드에서 길이가 1인 항목열을 초기화 리스트로 하여 벡터를 생성했으므로 size와 capacity가 모두 1이다. 따라서 push_bakc(2)로 새 항목을 이어 붙이는 순간 메모리 재할당이 발생하게 되고 iter는 댕글링 포인터가 되어버린다.
이렇듯 반복자가 일관된 인터페이스로 컨테이너를 다룰 수 있게 해주지만, 반복자 무효화가 발생하는 경위를 인지하기 위해서는 각 컨테이너의 동작 방식을 이해할 필요가 있다.
만약 컨테이너의 동작 방식을 잘 알지 못한다면 새 항목이 추가되거나 기존 항목이 삭제되는 등의 항목열의 변경이 발생했을 때 기존의 반복자들이 무효화 될 것이라고 생각하는 것이 안전하다.
