C++ 반복자: 종류와 연산, iterator_traits, 범위 기반 for의 디슈가링
이 글의 핵심
반복자는 알고리즘과 컨테이너를 잇는 인터페이스라서, 카테고리를 잘못 이해하면 커스텀 반복자가 std::sort나 뷰와 맞물리지 않습니다. 필터·변환 반복자를 직접 만들어 보고, back_insert_iterator·move_iterator·counted_iterator 같은 어댑터와 센티널 범위를 언제 쓰는지 정리합니다.
반복자 기본
반복자(iterator)는 컨테이너 요소를 순회하는 객체입니다. 범위 기반 for와 vector에서 begin/end로 사용되며, size_t·ptrdiff_t로 거리·인덱스를 다룰 때와 Composite 패턴으로 트리 순회를 통일할 때도 자주 씁니다.
반복자 개념도
graph LR
A[Container] --> B[begin]
A --> C[end]
B --> D[Iter]
D -->|++| E[Iter]
E -->|++| F[Iter]
F -->|++| C
D -->|*| G[Elem 1]
E -->|*| H[Elem 2]
F -->|*| I[Elem 3]
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3, 4, 5};
// begin/end
for (auto it = v.begin(); it != v.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// 역방향
for (auto it = v.rbegin(); it != v.rend(); ++it) {
cout << *it << " "; // 5 4 3 2 1
}
}반복자 종류
반복자 계층 구조
graph TD
A[Input Iterator] --> C[Forward Iterator]
B[Output Iterator] --> C
C --> D[Bidirectional Iterator]
D --> E[Random Access Iterator]
E --> F[Contiguous Iterator C++20]
A -.->|읽기 전용| A1[istream_iterator]
B -.->|쓰기 전용| B1[ostream_iterator]
C -.->|단방향| C1[forward_list]
D -.->|양방향| D1[list, set, map]
E -.->|임의 접근| E1[vector, deque, array]
F -.->|연속 메모리| F1[vector, array, string]
반복자 기능 비교표
| 반복자 타입 | 읽기 | 쓰기 | 전진 | 후진 | 임의 접근 | 예시 컨테이너 |
|---|---|---|---|---|---|---|
| Input | O | X | O | X | X | istream_iterator |
| Output | X | O | O | X | X | ostream_iterator |
| Forward | O | * | O | X | X | forward_list |
| Bidirectional | O | * | O | O | X | list, set, map |
| Random Access | O | * | O | O | O | vector, deque |
* 쓰기는 가변(mutable) 반복자일 때만 가능합니다. const_iterator나 set·map 키처럼 수정이 금지된 원소는 Forward 이상이어도 쓸 수 없습니다.
Input Iterator
// 읽기 전용, 한 번만 순회
istream_iterator<int> in(cin);
istream_iterator<int> eof;
vector<int> v(in, eof); // 입력 읽기Output Iterator
// 쓰기 전용
ostream_iterator<int> out(cout, " ");
vector<int> v = {1, 2, 3};
copy(v.begin(), v.end(), out); // 1 2 3Forward Iterator
// 읽기/쓰기, 여러 번 순회
forward_list<int> fl = {1, 2, 3};
for (auto it = fl.begin(); it != fl.end(); ++it) {
*it *= 2;
}Bidirectional Iterator
// 양방향 이동
list<int> l = {1, 2, 3, 4, 5};
auto it = l.end();
--it; // 마지막 원소
cout << *it << endl; // 5Random Access Iterator
// 임의 접근
vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin();
it += 3; // 3칸 이동
cout << *it << endl; // 4
cout << v[2] << endl; // 3카테고리별 연산·복잡도 요구사항(표준 개념과의 대응)
표준은 반복자를 연산 집합으로 정의합니다. 알고리즘이 RandomAccessIterator를 요구하면 +=, -, <, [] 등이 상수 시간에 동작해야 하며, BidirectionalIterator까지만 되면 advance가 선형 시간이 될 수 있습니다. Contiguous Iterator(C++20)는 원소가 메모리에 연속으로 놓여 있어 std::to_address로 원시 포인터를 얻을 수 있는 임의 접근 반복자로, vector·array·string의 일반 반복자가 여기에 해당합니다.
| 카테고리 | 핵심 추가 연산 | 알고리즘에서의 의미 |
|---|---|---|
| Input | ==, !=, *(읽기), ++(한 번 소비) | 단일 패스, 같은 구간을 다시 순회할 수 있다는 보장 없음 |
| Output | *(쓰기), ++ | 쓰기 전용, 같은 위치에 두 번 쓰는 것도 보장되지 않음 |
| Forward | 다회 순회(multi-pass) 보장, 기본 생성 | 복사본으로 같은 순서를 다시 읽을 수 있음 |
| Bidirectional | -- | 한 칸 뒤로 가기가 O(1) |
| Random Access | +=, -, [], < 등 | distance·advance가 상수 시간 |
| Contiguous(C++20) | 메모리 연속 | 포인터를 받는 C API·memcpy·SIMD 코드에 넘길 수 있음 |
이 구분이 실무에서 중요한 이유는 알고리즘이 카테고리에 따라 다른 구현을 고르기 때문입니다. std::distance(l.begin(), l.end())는 list에서 원소 수만큼 ++를 반복하는 O(N)이고, vector에서는 뺄셈 한 번인 O(1)입니다. 그래서 list에서 루프 안에 std::distance나 std::next(it, i)를 넣으면 겉보기에는 O(N) 코드가 O(N²)이 됩니다. 반대로 std::sort는 임의 접근을 요구하므로 list에 넣으면 no match for 'operator-' 같은 긴 템플릿 오류가 나고, 이때는 멤버 함수 l.sort()를 써야 합니다.
C++20 Ranges에서는 위 분류가 std::input_iterator / forward_iterator / bidirectional_iterator / random_access_iterator / contiguous_iterator 같은 concept으로 재정리되었으며, 커스텀 반복자는 연산자뿐 아니라 의미론(복사본의 독립성, 동치 관계)까지 맞춰야 합니다. concept은 문법만 검사하므로 의미론은 작성자가 지켜야 합니다. 자세한 문법 요구사항은 cppreference의 LegacyIterator 계열 문서를 기준으로 삼는 것이 안전합니다.
실전 예시
커스텀 반복자
#include <iostream>
using namespace std;
class Range {
private:
int current;
int last; // 멤버 함수 end()와 같은 이름을 쓰면 컴파일 오류
public:
class Iterator {
private:
int value;
public:
using iterator_category = forward_iterator_tag;
using value_type = int;
using difference_type = ptrdiff_t;
using pointer = void;
using reference = int; // operator*가 값을 반환하므로 참조 타입이 아님
Iterator(int v) : value(v) {}
int operator*() const { return value; }
Iterator& operator++() {
++value;
return *this;
}
bool operator!=(const Iterator& other) const {
return value != other.value;
}
};
Range(int start, int end) : current(start), last(end) {}
Iterator begin() { return Iterator(current); }
Iterator end() { return Iterator(last); }
};
int main() {
for (int x : Range(0, 10)) {
cout << x << " "; // 0 1 2 ... 9
}
}이 Iterator는 범위 기반 for에 필요한 세 가지(*, 전위 ++, !=)만 구현한 최소 반복자입니다. range-for에서는 잘 동작하지만, forward_iterator_tag를 선언했다고 해서 표준 알고리즘의 요구사항을 만족하는 것은 아닙니다. ==, 후위 ++, 기본 생성자가 없으므로 std::find 같은 레거시 알고리즘에 넣었을 때 컴파일되는지는 표준 라이브러리 구현이 내부에서 어떤 연산을 쓰느냐에 달려 있고, 컴파일되더라도 요구사항 위반이라 이식성이 없습니다. C++20 std::forward_iterator 개념으로 검사하면 std::equality_comparable과 std::incrementable(후위 ++, 기본 생성) 제약에서 떨어집니다. 또 operator*가 값을 반환하므로 reference를 int&로 적으면 선언이 거짓이 됩니다. 이런 불일치는 컴파일은 되다가 iterator_traits를 보는 알고리즘에서만 이상하게 터지므로, 타입 별칭은 실제 연산자 시그니처와 맞춰야 합니다. 엄밀히 말하면 레거시 Forward 요구사항은 reference가 진짜 참조이기를 요구하므로, 이 반복자는 input_iterator_tag로 선언하는 편이 정직합니다.
커스텀 반복자를 검토할 때 가장 먼저 붙여 볼 것은 static_assert(std::forward_iterator<Range::Iterator>); 한 줄입니다. 이 한 줄이 실패하면 컴파일러가 어떤 요구사항이 빠졌는지 알려 주므로, 알고리즘에 넣었을 때 수백 줄짜리 오류를 해독하는 것보다 훨씬 빠르게 빈 곳을 찾을 수 있습니다.
필터 반복자
#include <iostream>
#include <vector>
using namespace std;
template<typename Iter, typename Pred>
class FilterIterator {
private:
Iter current;
Iter end;
Pred predicate;
void advance() {
while (current != end && !predicate(*current)) {
++current;
}
}
public:
FilterIterator(Iter begin, Iter end, Pred pred)
: current(begin), end(end), predicate(pred) {
advance();
}
auto operator*() const { return *current; }
FilterIterator& operator++() {
++current;
advance();
return *this;
}
bool operator!=(const FilterIterator& other) const {
return current != other.current;
}
};
int main() {
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
auto isEven = [](int x) { return x % 2 == 0; };
FilterIterator begin(v.begin(), v.end(), isEven);
FilterIterator end(v.end(), v.end(), isEven);
for (auto it = begin; it != end; ++it) {
cout << *it << " "; // 2 4 6 8 10
}
}필터 반복자에는 설계상 함정이 두 가지 있습니다. 첫째, end를 반복자 안에 들고 있어야 하므로 반복자 크기가 기반 반복자의 두 배 이상이 되고, 조건자(predicate)까지 복사됩니다. 둘째, 생성자와 ++에서 조건을 만족하는 원소를 찾을 때까지 앞으로 가기 때문에 begin()을 만드는 것 자체가 O(N)일 수 있습니다. 표준 views::filter가 첫 begin() 결과를 캐시하는 것도 이 비용 때문이며, 그 캐시 때문에 filter 뷰는 const로 순회할 수 없다는 제약이 생겼습니다. 이 예제는 --를 제공하지 않으므로 기반 반복자가 양방향이어도 전진 전용으로 동작합니다.
변환 반복자
#include <iostream>
#include <vector>
using namespace std;
template<typename Iter, typename Func>
class TransformIterator {
private:
Iter current;
Func transform;
public:
TransformIterator(Iter it, Func f) : current(it), transform(f) {}
auto operator*() const {
return transform(*current);
}
TransformIterator& operator++() {
++current;
return *this;
}
bool operator!=(const TransformIterator& other) const {
return current != other.current;
}
};
int main() {
vector<int> v = {1, 2, 3, 4, 5};
auto square = [](int x) { return x * x; };
TransformIterator begin(v.begin(), square);
TransformIterator end(v.end(), square);
for (auto it = begin; it != end; ++it) {
cout << *it << " "; // 1 4 9 16 25
}
}변환 반복자의 operator*는 값을 새로 계산해 prvalue로 반환합니다. 그래서 *it = 10; 같은 쓰기는 의미가 없고, reference가 진짜 참조가 아니라서 C++17 기준으로는 입력 반복자(Input)로만 분류됩니다. C++20의 views::transform이 iterator_category와 iterator_concept를 따로 두는 이유가 바로 이것입니다. 개념상으로는 기반 반복자처럼 임의 접근이지만 레거시 카테고리는 더 약하게 보고합니다.
반복자 연산
반복자 연산 함수 비교
| 함수 | 시간 복잡도 | 지원 반복자 | 설명 |
|---|---|---|---|
advance(it, n) | O(1) ~ O(n) | Input 이상(음수 n은 Bidirectional 이상) | n칸 이동 (제자리 수정) |
distance(first, last) | O(1) ~ O(n) | Input 이상 | 두 반복자 간 거리 |
next(it, n=1) | O(1) ~ O(n) | Input 이상 | n칸 앞 반복자 반환 |
prev(it, n=1) | O(1) ~ O(n) | Bidirectional 이상 | n칸 뒤 반복자 반환 |
iter_swap(it1, it2) | O(1) | Forward 이상 | 두 반복자가 가리키는 값 교환 |
복잡도가 “O(1) ~ O(n)“인 함수는 임의 접근 반복자에서 상수 시간, 그 밖에서는 n에 비례합니다.
vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin();
// 전진
advance(it, 3); // 3칸 이동
cout << *it << endl; // 4
// 거리
auto dist = distance(v.begin(), v.end());
cout << dist << endl; // 5
// 다음/이전
auto next_it = next(it);
auto prev_it = prev(it);advance는 인자로 받은 반복자를 직접 움직이고 아무것도 반환하지 않는 반면, next는 원래 반복자를 그대로 두고 이동한 복사본을 반환합니다.
graph LR
A[it = v.begin] --> B{Which?}
B -->|advance it, 3| C[Modify it]
C --> D[it = begin+3]
B -->|next it, 3| E[Return new]
E --> F[it = begin]
E --> G[return = begin+3]
이터레이터 특성(iterator_traits)과 타입 정보
템플릿 알고리즘은 구체 반복자 타입을 몰라도 iterator_traits<Iter>로 값 타입·차이 타입·카테고리를 얻습니다. C++98 시절에는 반복자 클래스에 typedef 다섯 종(iterator_category, value_type, difference_type, pointer, reference)을 붙이는 패턴이 표준이었으며, 포인터는 iterator_traits<T*> 부분 특수화로 같은 정보를 제공합니다.
iterator_category와 C++20 iterator_concept
C++17까지는 random_access_iterator_tag 등 태그 타입이 카테고리의 전부였습니다. C++20부터 반복자 타입은 멤버 iterator_concept로 contiguous_iterator_tag 같은 더 정밀한 개념 태그를 노출할 수 있습니다(포인터는 iterator_traits<T*>::iterator_concept로 제공). C++20 반복자 개념(std::random_access_iterator 등)과 std::ranges 알고리즘은 우선 iterator_concept를, 없으면 iterator_category를 보고 판단합니다. 반면 std::sort 같은 레거시 알고리즘은 여전히 iterator_category만 봅니다. 그래서 한 반복자가 두 세계에서 서로 다른 카테고리로 취급될 수 있습니다. 태그 디스패치와 연결해 이해하면 컴파일 타임 분기의 실체가 보입니다.
#include <iterator>
#include <vector>
#include <iostream>
#include <typeinfo>
template <class Iter>
void describe() {
using Tr = std::iterator_traits<Iter>;
// typeid(...).name()의 출력 형식은 구현마다 다름(GCC/Clang은 맹글링된 이름)
std::cout << "iterator_category: "
<< typeid(typename Tr::iterator_category).name() << '\n';
}
int main() {
describe<std::vector<int>::iterator>();
}pointer·reference와 프록시 반복자
일부 컨테이너(vector<bool> 등)는 프록시 참조를 쓰므로 reference가 T&가 아닐 수 있습니다. 이 경우 for (auto& b : bits)는 임시 프록시를 non-const 좌변값 참조에 묶으려다 컴파일 오류가 나고, auto로 받으면 복사본이 아니라 원본을 가리키는 프록시를 받게 됩니다. 범위 기반 for에서 auto&와 auto&&를 고르는 기준과 함께 읽는 것이 좋습니다. 연속 반복자가 아니면 반복자에서 얻은 포인터로 인접 원소에 접근하는 것도 허용되지 않습니다.
std::iter_difference_t, std::iter_value_t (C++20)
C++20에서는 iterator_traits를 직접 꺼내기보다 std::iter_value_t<It>, std::iter_reference_t<It>, std::iter_difference_t<It> 같은 별칭 템플릿으로 가독성을 높입니다. Ranges 알고리즘 시그니처는 이 타입들을 기본으로 가정합니다.
#include <iterator>
#include <vector>
template <class It>
void use(It first, It last) {
std::iter_difference_t<It> n = std::distance(first, last);
(void)n;
std::iter_value_t<It> copy = *first;
(void)copy;
}이터레이터 어댑터 패턴
어댑터는 기존 반복자나 출력 대상을 감싸 다른 연산 모델을 제공합니다. 직접 FilterIterator를 작성하기 전에 표준 조합으로 해결되는지 먼저 검토하는 것이 안전합니다.
삽입 반복자(back_insert_iterator 등)
std::back_inserter, std::front_inserter, std::inserter는 대입될 때마다 컨테이너의 push_back·push_front·insert를 호출하는 출력 반복자입니다. copy(src.begin(), src.end(), back_inserter(dest))는 대상 크기를 미리 맞추지 않고 뒤에 이어 붙일 때 유용합니다. 단, dest가 vector라면 삽입 중 재할당으로 dest를 가리키던 다른 반복자가 무효화된다는 점을 염두에 두어야 합니다. 원소 수를 안다면 dest.reserve()를 먼저 호출하면 재할당 횟수도 줄일 수 있습니다.
#include <vector>
#include <iterator>
#include <algorithm>
int main() {
std::vector<int> a{1, 2, 3}, b;
std::copy(a.begin(), a.end(), std::back_inserter(b));
}reverse_iterator·move_iterator
reverse_iterator는 내부에 기반 반복자를 들고 있으면서 *rit가 *std::prev(rit.base())를 돌려주도록 구현됩니다. 즉 rbegin()의 base()는 end()이고, 역참조할 때 한 칸 앞 원소를 봅니다. 이 한 칸 차이 때문에 역방향으로 찾은 원소를 erase할 때 v.erase(rit.base())라고 쓰면 엉뚱한 원소(찾은 것의 다음)가 지워집니다. 올바른 형태는 v.erase(std::next(rit).base())입니다.
move_iterator는 역참조 결과가 T&&(rvalue 참조)인 반복자 어댑터입니다. std::vector<std::string> dst(std::make_move_iterator(src.begin()), std::make_move_iterator(src.end()));처럼 쓰면 원소를 복사하지 않고 이동하므로, 큰 문자열이나 unique_ptr처럼 복사가 비싸거나 불가능한 원소를 옮길 때 유용합니다. 이동된 뒤 src의 원소는 유효하지만 값이 지정되지 않은(valid but unspecified) 상태가 됩니다.
counted_iterator + default_sentinel (C++20)
counted_iterator는 기반 반복자와 남은 개수를 함께 들고 다니며, 개수가 0이 되면 default_sentinel과 같다고 비교됩니다. 끝 위치를 반복자로 미리 구하지 않고 “앞에서부터 n개”만 순회할 때 쓰며, 끝이 반복자와 다른 타입이므로 센티널을 받는 std::ranges 알고리즘과 함께 씁니다.
#include <algorithm>
#include <iostream>
#include <iterator>
int main() {
int a[] = {1, 2, 3, 4, 5};
std::counted_iterator first(a, 3); // 앞에서 3개
// 레거시 std::for_each는 first와 last가 같은 타입이어야 하므로 컴파일되지 않음
std::ranges::for_each(first, std::default_sentinel,
[](int x) { std::cout << x << ' '; }); // 1 2 3
}뷰·파이프라인과의 역할 분담
C++20 std::ranges::views::filter, transform 등은 커스텀 반복자를 직접 만들지 않고도 지연 평가 파이프라인을 제공합니다. C++20 Ranges 기초와 함께 보면, “어댑터를 수작업으로 구현할지, 뷰로 조합할지” 판단이 쉬워집니다.
범위 기반 for의 디슈가링(desugaring)
range-for는 문법적 설탕(syntactic sugar)이지만, C++17에서 규칙이 조금 바뀌었습니다. 핵심은 범위 표현식을 한 번만 평가해 참조로 붙잡아 두고, 멤버 begin/end가 없으면 ADL로 자유 함수를 찾는다는 점입니다.
C++17 이후의 개략적 형태
대략 다음과 같은 구조입니다(실제 표준 문구와 begin/end 후보 집합은 더 길고, 배열·브레이스 초기화 등 특례가 있습니다).
// for (for-range-declaration : for-range-initializer) 문
// 내부적으로는 개념적으로:
// auto&& __range = for-range-initializer;
// auto __begin = begin(__range); // 멤버 begin이 있으면 그것, 없으면 ADL로 찾은 begin
// auto __end = end(__range);
// for (; __begin != __end; ++__begin) {
// for-range-declaration = *__begin;
// ...
// }여기서 나오는 결과가 몇 가지 있습니다. 클래스에 begin이나 end라는 이름의 멤버가 하나라도 있으면 멤버 버전이 쓰이고, 없을 때만 ADL로 자유 함수 begin/end를 찾습니다. 이때 일반 이름 검색은 하지 않으므로, 전역에 begin을 선언해도 타입이 속한 네임스페이스가 아니면 발견되지 않습니다. C++17에서 바뀐 점은 __begin과 __end를 따로 선언해 서로 다른 타입(센티널)을 허용한 것입니다. 임시 벡터를 돌릴 때 __range(auto&&)가 임시에 묶여 수명이 루프 전체로 연장되는 이유도 여기에서 나옵니다.
다만 수명 연장은 for-range-initializer의 최종 결과에만 적용됩니다. for (auto x : make_vector_of_vectors()[0])처럼 임시의 일부를 순회하면, 바깥 임시는 초기화식이 끝나는 순간 소멸하고 __range는 이미 해제된 내부 벡터를 가리킵니다. for (char c : getName().c_str())류도 같은 문제입니다. 이 함정은 C++23(P2718)에서 초기화식 안의 모든 임시가 루프 끝까지 살도록 고쳐졌지만, C++20 이하로 컴파일한다면 중간 결과를 먼저 지역 변수에 담아야 합니다. 세부는 범위 기반 for 전용 글의 예시와 함께 보는 것을 권합니다.
begin ≠ 멤버만
일부 서드파티 버퍼는 멤버가 아닌 자유 함수 begin/end만 제공합니다. 위 규칙 덕분에 같은 네임스페이스에 자유 함수만 두면 이런 타입도 range-for에 쓸 수 있습니다. 반대로 begin과 end의 결과를 !=로 비교할 수 없으면 템플릿 오류로 드러나므로, 커스텀 범위를 만들 때는 서로 비교 가능한 begin/end 쌍을 맞추는 것이 첫 번째 과제입니다.
실무에서 반복자를 다룰 때
end() 반복 호출
매 루프마다 end()를 호출하는 것은 최적화 빌드에서 인라인되면 대개 문제가 없지만, 디버그 빌드나 end()가 비싼 사용자 정의 범위에서는 auto e = c.end()로 한 번만 잡아 두기도 합니다. 범위 for는 디슈가링에서 보았듯이 __end를 한 번만 구합니다. 단, 루프 안에서 컨테이너에 삽입·삭제를 한다면 미리 잡아 둔 end가 무효화되므로 이 최적화를 쓰면 안 됩니다.
센티널 범위와 알고리즘 선택
C++20 이후에는 begin과 end가 다른 타입인 범위가 흔합니다(views::iota의 무한 범위, istream 뷰, counted_iterator 등). 레거시 std::sort(first, last)처럼 두 인자가 같은 타입이라고 가정하는 API에는 이런 범위를 넘길 수 없으므로, std::ranges:: 알고리즘을 쓰는 편이 안전합니다.
무효화를 먼저 정리하기
저수준 반복자 루프는 반복자 무효화 규칙과 얽혀 버그가 나기 쉽습니다. vector에서 erase 후에는 erase가 반환한 반복자를 사용하고, 루프 안에서 삽입으로 재할당이 일어날 수 있으면 인덱스 기반으로 바꾸는 식으로, 무효화 규칙을 먼저 정리한 뒤 반복자를 설계하는 것이 좋습니다.
직접 반복자 클래스를 만들기 전에
Boost.Iterator의 iterator_facade 같은 도우미, 인덱스와 std::span, std::ranges 뷰로 해결할 수 있다면 그쪽이 유지보수 비용이 낮습니다. 꼭 직접 만들어야 한다면 목표 카테고리를 정하고 static_assert로 해당 concept을 검사하며, 동치 관계(==)와 복사본의 독립성 같은 의미론을 주석으로 남겨 두세요.
자주 발생하는 문제
그림: 실제 실행 결과 — erase 뒤에 ++it를 하면 연속된 3 중 하나가 남아 1 2 3 5가 되고, erase 반환값을 쓰면 1 2 5가 된다. push_back 재할당 뒤의 옛 반복자는 heap-use-after-free, 용량이 꽉 찬 vector의 end() 역참조는 heap-buffer-overflow로 잡힌다. vector와 list의 반복자 타입은 서로 대입할 수 없다. (환경: macOS 27.0.1 · Apple clang 21.0.0 · AddressSanitizer)
무효화된 반복자
// ❌ 반복자 무효화
vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it == 3) {
v.erase(it); // it 무효화!
// ++it; // 위험!
}
}
// ✅ erase 반환값 사용
for (auto it = v.begin(); it != v.end();) {
if (*it == 3) {
it = v.erase(it); // 다음 반복자 반환
} else {
++it;
}
}앞의 잘못된 반복문은 erase(it) 직후 it을 다시 쓰는 것 자체가 정의되지 않은 동작입니다. 실제로는 vector에서 it이 다음 원소를 가리키므로, 뒤이어 ++it가 실행되면 그 원소를 건너뜁니다. 연속된 3이 있으면 하나가 남습니다(위 실행 화면의 1 2 3 5).
end() 역참조
// ❌ end() 역참조
vector<int> v = {1, 2, 3};
auto it = v.end();
// cout << *it << endl; // UB
// ✅ end() 체크
if (it != v.end()) {
cout << *it << endl;
}반복자 타입 불일치
// ❌ 타입 불일치
vector<int> v;
list<int> l;
// auto it = v.begin();
// it = l.begin(); // 에러
// ✅ 올바른 타입
auto vit = v.begin();
auto lit = l.begin();컨테이너별 무효화 규칙과 디버그 검사
컨테이너별 반복자 무효화 규칙:
vector/string: 삽입으로 재할당이 일어나면 모든 반복자·참조가 무효화되고, 재할당이 없으면 삽입 지점 이후만 무효화됩니다.erase는 지운 지점과 그 이후를 무효화합니다.deque: 양 끝 삽입은 모든 반복자를 무효화하지만 원소 참조는 유지됩니다. 중간 삽입·삭제는 전부 무효화합니다.list/map/set: 삽입은 아무것도 무효화하지 않고, 삭제는 삭제된 원소를 가리키던 것만 무효화합니다.unordered_map/unordered_set: 삽입으로 재해시(rehash)가 일어나면 모든 반복자가 무효화되지만, 원소 참조와 포인터는 유지됩니다.
이런 버그는 디버그 모드에서 잡을 수 있습니다. libstdc++는 -D_GLIBCXX_DEBUG, MSVC는 디버그 빌드의 기본 반복자 검사(_ITERATOR_DEBUG_LEVEL=2)로 무효화된 반복자 사용이나 다른 컨테이너 반복자 비교를 런타임에 잡아 줍니다. libstdc++ 디버그 모드는 attempt to increment a singular iterator 같은 메시지를 내고 중단합니다. 다만 _GLIBCXX_DEBUG는 컨테이너 ABI를 바꾸므로 이 매크로 없이 빌드한 라이브러리와 섞어 링크하면 안 됩니다.
성능 면에서는, 최적화 빌드에서 vector 반복자가 포인터를 감싼 얇은 래퍼라 인라인되어 포인터와 거의 차이가 없습니다. 디버그 빌드에서는 위의 검사 기능 때문에 눈에 띄게 느릴 수 있으므로, 성능 측정은 릴리스 빌드로 해야 합니다.