_C++_반복자

C++은 템플릿 기반의 컨테이너(자료구조)를 제공하고 컨테이너 항목들에 범용적인 접근 방복을 제공하기 위해 반복자 패턴을 사용하고 있다.

각 컨테이너는 그 컨테이너만의 반복자를 지원한다.

반복자는 특정 컨테이너의 항목을 어떻게 순회할지 알고 있는 포인터 객체이다.

포인터 객체는 C++ 표준에서 정하고 있는 공용 인터페이스를 따르고 있으며 일관된 방법으로 각 컨테이너를 순회할 수 있도록 해준다.

C++ STL에 포함된 알고리즘들 또한 대부분 반복자들을 파라미터로 받아 작동하며, 각 컨테이너의 구조에 종속되지 않게 구현이 된다.

C++ 표준에서 반복자의 카테고리 분류

반복자 기능	입력 반복자	출력 반복자	순방향 반복자	양방향 반복자	임의 접근 반복자
접근(operator→)	O	X	O	O	O
읽기(operator *)	O	X	O	O	O
쓰기(operator *)	X	O	O	O	O
증가(operator++)	O	O	O	O	O
감소(operator--)	X	X	X	O	O
인덱스(operator[])	X	X	X	X	O
산술 연산(operator+, -)	X	X	X	X	O
산술대입연산(operator+=, -=)	X	X	X	X	O
대소비교연산(operator<,<=,>=,>)	X	X	X	X	O

 

입력 반복자는 입력스트림에서, 출력 반복자는 출력 스트림에서만 쓰인다.

각각 입력 및 출력 전용 반복자로 기능이 상당히 제한적이다.

순차, 연관, 비순차 컨테이너 등은 순방향, 양방향 임의 접근 반복자 중 하나를 지원하지만, 컨테이너 어댑터 클래스와 bitset 클래스는 반복자를 지원하지 않는다.

반복자에 대한 증감, 산술 대소비교 등은 반복자가 순회하는 항목의 순열 안에서 반복자의 위치에 대해 수행되는 연산.

반복자를 지원하는 컨테이너는 typedef로 반복자의 타입을 정의한다.

iterator, const_iterator, reverse_iterator, const_reverse_iterator과 같은 이름으로 정의되어 있다.

iterator, const_iterator 은 순방향이 +, reverse_iterator, const_reverse_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.rbegin(); rIter != v.rend(); ++rIter)
	cout << *rIter << ' ';//output: 5 4 3 2 1

end는 메서드 마지막 항목의 다음 항목을 반환하고, rend는 첫 번째 항목의 이전 항목을 반환한다. 둘 다 유요하지 않은 대상을 가리킨다.

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도 더 큰폭으로 증가한다. 0 → 1 → 2 → 4 → 8 →...과 같이 capacity의 크기가 증가한다.

또한 벡터는 처음 생성될 때 size와 capacity가 같도록 생성된다.

만약 코드에서 길이가 1인 항목열을 초기화 리스트로 백터를 생성한다면, size, capacity가 모두 1이다.

즉 위의 예시에서 vector<int> v{ 1 };로 길이가 1인 벡터를 생성하면, size, capacity가 모두 1인 상태이다.

그런데 push_back(2)으로 항목을 새로 이어 붙이는 순간 메모리가 재할당이 발생하고 iter는 댕글링 포인터가 되어버린다.

 

각 컨테이너의 동작 방식을 잘 이해할 필요가 있으며, 잘 알지 못한다면, 새 항목이 추가되거나 기존 항목이 삭제될 경우 항목열의 변경이 발생했을때, 기존의 반복자들이 무효화 될 것이라고 생각하면 안전하다.