이터레이터가 실제로 무엇인가
모든 표준 컨테이너 - vector, string, map, set, list - 는 내부에서 요소를 서로 다르게 저장합니다. vector는 연속된 블록이고, map은 균형 트리이며, list는 연결된 노드입니다. 그런데도 이들 모두를 같은 방식으로 순회할 수 있습니다. 그것을 가능하게 하는 것이 바로 이터레이터입니다. 하나의 요소를 "가리키며" 다음으로 어떻게 나아가는지 아는 작은 객체죠.
이터레이터를 일반화된 포인터라고 생각하세요. begin()에서 하나를 얻고, 그것이 가리키는 요소를 *로 읽으며, ++로 앞으로 옮깁니다. 조각들은 이렇게 맞물립니다.
v.begin()은 첫 요소를 가리키는 이터레이터를 반환하고, *it는 그 요소를 주며, ++it는 다음으로 이동합니다. 이 세 가지 - 역참조, 전진, 비교 - 가 전체 멘탈 모델입니다.
begin(), end(), 그리고 반열린 구간
나머지 절반은 end()입니다. 결정적으로, end()는 마지막 요소를 가리키지 않습니다 - 마지막 요소의 한 칸 뒤 자리를 가리킵니다. 이것은 의도적인 "반열린" 구간 [begin, end)입니다. begin은 포함되고, end는 멈춤 신호입니다.
이 설계 덕분에 표준 반복문이 깔끔해집니다 - 이터레이터가 end()와 같아질 때까지 나아가면 됩니다.
it < v.end()가 아니라 it != v.end()라는 점에 유의하세요. 대부분의 컨테이너 이터레이터(map이나 list 같은)는 <를 지원하지 않고 ==와 !=만 지원하므로, !=가 이식성 있는 선택입니다. 그리고 auto 키워드를 쓰면 vector<int>::iterator를 손으로 쓰지 않아도 됩니다 - 컴파일러가 추론해 줍니다.
빈 컨테이너의 경우는 자연스럽게 처리됩니다. 컨테이너가 비어 있으면 begin() == end()이므로 반복문 본문은 한 번도 실행되지 않습니다. 별도의 특수 처리가 필요 없습니다.
end()를 절대 역참조하지 마라
가장 흔한 이터레이터 버그는 end()를 역참조하는 것입니다. end()는 마지막 요소의 한 칸 뒤를 가리키므로, *v.end()는 당신 것이 아닌 메모리를 읽습니다 - 정의되지 않은 동작이며, 이는 친절한 오류가 아니라 크래시나 조용한 쓰레기 값을 뜻합니다.
vector<int> v = {1, 2, 3};
cout << *v.end(); // 정의되지 않은 동작 - end()는 요소가 아니다
같은 함정이 탐색 함수에도 도사리고 있습니다. std::find는 값을 찾지 못하면 end()를 반환하므로, 역참조하기 전에 반드시 확인해야 합니다.
반환된 이터레이터를 역참조하기 전에 항상 end()와 비교하세요. 이 if를 빠뜨리는 것은 초보자의 STL 코드에서 크래시를 일으키는 가장 잦은 원인 중 하나입니다.
const, cbegin, 그리고 reverse 이터레이터
컨테이너는 필요에 따라 서로 다른 종류의 이터레이터를 내어줍니다.
begin()/end()- 일반 읽기/쓰기 이터레이터 (*it = ...가 동작함).cbegin()/cend()-const_iterator. 이를 통해 읽을 수는 있지만 요소를 수정할 수는 없습니다.rbegin()/rend()- 뒤에서 앞으로 순회하는 reverse 이터레이터.++가 실제로는 뒤로 움직입니다.
reverse 이터레이터는 번거로운 인덱스 계산 없이 역순으로 순회하는 깔끔한 방법입니다.
reverse 이터레이터에서도 나아가려면 여전히 ++it라고 씁니다 - 이터레이터가 "뒤로 가는" 방향을 내부적으로 처리해 줍니다. 반복문이 읽기만 해야 한다면 cbegin()/cend()(또는 컨테이너에 대한 const 참조)를 사용해, 실수로 쓰는 것을 컴파일러가 막아주도록 하세요.
map 이터레이터는 pair를 내놓는다
모든 이터레이터가 포인터를 감싼 얇은 래퍼인 것은 아닙니다. std::map의 이터레이터는 트리를 따라가며, 역참조하면 키와 값의 std::pair를 얻고, ->first와 ->second로 접근합니다(포인터와 마찬가지로 이터레이터도 ->를 지원합니다).
범위 기반 for 반복문은 begin()/end() 위에 직접 만들어졌으므로, 단순한 전진 순회에는 보통 그쪽을 쓰게 됩니다. 명시적 이터레이터는 역순 순회, 요소의 위치, 또는 알고리즘에 구간을 넘겨야 할 때 그 값어치를 합니다.
가장 큰 함정: 이터레이터 무효화
이것은 결국 모두가 한 번은 당하는 함정입니다. 컨테이너의 구조를 바꾸면 기존 이터레이터가 무효화될 수 있습니다 - 해제되었거나 이동된 메모리를 가리키게 되는 것이죠. 그런 이터레이터를 사용하는 것은 정의되지 않은 동작입니다.
vector의 경우 push_back이 크기를 키우기 위해 버퍼 전체를 재할당하여 모든 살아 있는 이터레이터를 무효화할 수 있습니다. 순회하면서 삭제하는 것은 더욱 악명 높습니다 - 이것이 전형적인 크래시입니다.
vector<int> v = {1, 2, 3, 4};
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it % 2 == 0)
v.erase(it); // 버그 - erase가 it을 무효화하고, 그다음 ++it는 정의되지 않은 동작
}
해결책은 erase가 제거된 요소의 바로 다음 요소를 가리키는 유효한 이터레이터를 반환한다는 점입니다. 삭제하지 않았을 때만 전진하세요.
for 헤더에 ++it가 없다는 점에 주목하세요 - 전진할지는 본문이 결정합니다. (실제 코드에서는 erase-remove 관용구나 C++20의 std::erase_if가 이를 한 줄로 처리합니다.) 기억할 규칙은 이것입니다. 요소를 추가하거나 제거하는 모든 연산은 이터레이터를 무효화할 수 있으므로, 그런 변경을 가로질러 오래된 이터레이터를 붙들고 있지 마세요.
다음: 알고리즘
이제 구간을 begin/end 쌍으로 기술할 수 있게 되었으니, 당신은 STL 알고리즘 라이브러리 전체를 손에 넣은 셈입니다. sort, find, count, accumulate 같은 함수들은 당신이 어떤 컨테이너를 가졌는지 신경 쓰지 않습니다 - 이터레이터 구간 위에서 동작하므로, 같은 호출이 vector에서도, 배열에서도, 그 일부 조각에서도 작동합니다. 다음에는 이 이터레이터들을 실제로 일하게 하고, 반복은 표준 라이브러리가 대신하도록 맡겨 보겠습니다.
자주 묻는 질문
C++에서 이터레이터란 무엇인가요?
이터레이터는 컨테이너 안의 한 요소를 가리키며 다음 요소로 이동하는 방법을 아는 객체입니다. 첫 요소는 container.begin()으로, 마지막 요소의 한 칸 뒤를 가리키는 표시는 container.end()로 얻습니다. *it로 역참조해 요소를 읽거나 쓰고, ++it로 전진시킵니다. 이터레이터는 STL 알고리즘이 어떤 컨테이너에서든 동작하도록 해주는 공통 인터페이스입니다.
C++에서 이터레이터와 포인터의 차이는 무엇인가요?
vector나 배열의 경우 이터레이터는 거의 포인터와 똑같이 동작합니다 - *로 역참조하고, ++로 전진하며, ==/!=로 비교합니다. 하지만 이터레이터는 반드시 원시 포인터인 것은 아닌 개념입니다. map이나 list의 이터레이터는 트리나 연결된 노드를 따라가므로, *와 ++를 오버로드하는 클래스 타입입니다. 포인터는 이터레이터의 한 종류이며, 이터레이터는 그 개념을 모든 컨테이너로 일반화한 것입니다.
C++에서 이터레이터 무효화는 무엇 때문에 발생하나요?
컨테이너의 구조를 변경하면 기존 이터레이터가 해제되었거나 이동된 메모리를 가리킨 채 남을 수 있습니다. vector의 경우 push_back이 재할당을 일으켜 모든 이터레이터를 무효화할 수 있고, erase는 제거된 요소와 그 이후의 이터레이터를 무효화합니다. 무효화된 이터레이터를 사용하는 것은 정의되지 않은 동작입니다. 안전하게 하려면 erase가 반환하는 이터레이터를 사용하거나, 미리 용량을 예약하세요.
