1. 이터레이터 카테고리가 필요한 이유
만약 지금까지 이터레이터를 “거의 포인터”로 받아들였다면, 당신만 그런 것이 아닙니다: 많은 사람이 그렇게 생각합니다. 저도 C++ 초창기에 그렇게 생각했습니다. 그러나 STL에서 이터레이터는 메모리 주소가 아니라 가능성에 대한 계약입니다: 이 이터레이터로 정확히 무엇을 할 수 있고 무엇을 기대할 수 없는지에 대한 규정입니다.
이터레이터 카테고리는 바로 이러한 가능성을 표준화하기 위해 존재합니다. 그러면 STL 알고리즘은 정직하게 말할 수 있습니다: “내가 필요한 것은 ++it를 수행하고 *it를 읽을 수 있다는 것” — 또는 반대로: “아니요, 여러분, it + n과 it2 - it1 없이는 정렬을 수행하지 않겠다”고요.
실생활에 더 가깝게 비유하자면: 이터레이터는 교통수단과 같습니다. 자전거로는 앞으로만 갈 수 있고 때때로 조심스럽게 뒤로 갈 수 있지만 “10km를 순간이동”할 수는 없습니다. 반면 지하철(비유적 의미의 vector)은 원하는 역으로 빠르게 “뛰어갈” 수 있게 해줍니다.
이터레이터와 범위 [first, last)
카테고리로 이터레이터를 나누기 전에 기본 모델을 상기하는 것이 중요합니다: STL은 거의 모든 곳에서 반열린 구간 [first, last)을 사용합니다. 이는 first가 범위의 첫 요소를 가리키고, last는 마지막 이후의 위치를 가리킨다는 뜻입니다. 즉 last는 역참조할 수 없으며 — 마치 "더 이상 갈 수 없음"을 알리는 표지판과 같습니다.
학습용 예제로 작은 데모를 들어보겠습니다: 작업 목록이 있다고 합시다(예제에서는 이 목록을 “문맥”으로 사용합니다).
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> tasks{"Read", "Code", "Sleep"};
for (auto it = tasks.begin(); it != tasks.end(); ++it) {
std::cout << *it << '\n';
}
}
// Read
// Code
// Sleep
여기서는 이터레이터와 일반적으로 연결되는 기본 연산들을 볼 수 있습니다: 비교 !=, 역참조 *it, 그리고 전진 ++it. 하지만 더 흥미로운 부분은 다음입니다: 모든 이터레이터가 “고급” 연산을 지원하지는 않습니다. 예를 들어 it + 5나 --it 같은 연산은 항상 가능한 것이 아닙니다.
이터레이터의 기능 사다리
이터레이터 카테고리는 본질적으로 다음 질문에 대한 답입니다: 어떤 연산이 보장되어 작동하는가 (그리고 그 연산들은 무슨 의미인가). 표준에서는 이것이 단순한 취향 문제가 아니라 표준 라이브러리 알고리즘이 의존하는 정확한 요건입니다.
'기능 사다리'를 머릿속에 두면 편합니다: 카테고리가 높을수록 더 많은 연산이 허용됩니다. 아래는 실용적인 요약표(표준의 정식 표는 아니며 학습용 메모입니다).
| 카테고리 | 읽기 가능 *it | 쓰기 가능 *it = ... | 가능 ++it | 가능 --it | 가능 it + n, it[n] | 전형적 연관 |
|---|---|---|---|---|---|---|
|
예 | 때때로(하지만 보통은 "읽기 전용") | 예 | 아니요 | 아니요 | 데이터 스트림, 도착한 대로 읽기 |
|
예 | 보통 예 | 예 | 아니요 | 아니요 | 다중 통과 가능한 "앞으로만" |
|
예 | 예 | 예 | 예 | 아니요 | 뒤로 한 걸음 가능 |
|
예 | 예 | 예 | 예 | 예 | 거의 배열과 같은 능력 |
이 표의 목적은 암기하려는 것이 아니라, “vector에서 작동했으니 어디서든 작동할 것”이라는 습관을 버리게 하는 것입니다. STL에서는 보증(이터레이터가 무엇을 약속하는지) 중심의 사고방식을 매우 중시합니다. 이것이 바로 중요한 차이점입니다.
2. 실전에서의 이터레이터 카테고리
input
: 이동하면서 읽기, 단일 통과
inputInput 이터레이터는 데이터가 컨테이너에 전부 존재하지 않고 순차적으로 도착하는 경우에 주로 사용됩니다: 수도꼭지에서 나오는 물처럼요. 현재 값을 컵에 따른다(현재 값 읽기), 그다음 수도꼭지를 한 번 더 돌려 다음 값으로 간다(++it) — 하지만 "이전 물방울로 돌아가서 다시 마신다"는 불가능합니다. 그래서 input 이터레이터는 종종 단일 통과입니다: 같은 데이터를 다시 두 번째로 통과할 수 없습니다.
가장 전형적인 예는 std::istream_iterator<T>로, 스트림에서 값을 읽습니다. 이것은 스트림을 컨테이너처럼 보이게 하지만 본질적으로는 스트림입니다: 한 번 읽으면 그게 끝이고 뒤로 되돌릴 수 없습니다.
#include <iostream>
#include <iterator>
#include <sstream>
int main() {
std::istringstream in("10 20 30");
std::istream_iterator<int> it(in);
std::istream_iterator<int> end;
std::cout << *it << '\n'; // 10
++it;
std::cout << *it << '\n'; // 20
}
심리적 포인트에 주목하세요: istream_iterator는 평범한 이터레이터처럼 보이지만 그 본성은 "스캐너"에 가깝습니다. 여러분은 "5번째 요소를 달라"가 아니라 "다음 것을 달라"고 말합니다.
input 이터레이터를 random-access처럼 생각하고 "100만 앞으로 점프"하려고 하면, 컴파일러가 정직하게 알려줄 것입니다: “그건 약속하지 않았습니다.”
forward
: 전진만 가능하나 여러 번 통과 가능
forwardForward 이터레이터는 input과 비슷하게 오직 전진(++it)하지만 중요한 실무 차이가 있습니다: 보통 그것들을 복사해서 재사용할 수 있어 여러 번 순회할 수 있습니다. 즉 더 이상 "한 번 쓰고 버려지는 스트림"이 아니라 "정상적인 시퀀스"입니다. 다만 뒤로 가는 것은 보장되지 않습니다.
실제 컨테이너에서는 forward 이터레이터가 데이터 구조상 뒤로 가기가 저렴하게 지원되지 않는 경우에 흔히 나타납니다. 개념적으로는 벽에 붙어 있는 작업 목록처럼 위에서 아래로 읽는 것은 가능하지만 인터페이스 차원에서 --it를 보장하지 않습니다.
작동 여부를 검증하는 짧은 현실 점검: 개인적으로는 뒤로 갈 수 있어도, 이터레이터 인터페이스가 그것을 허용하지 않을 수 있습니다. STL은 최소한의 보장을 기반으로 설계됩니다.
이 강의에서는 forward 이터레이터를 특정한 새 컨테이너에 묶지 않겠습니다(다음 주제로 벗어나지 않기 위해). 핵심은 다음과 같습니다: forward = 다중 통과 가능 + 전진(++)만 가능. 즉 전진은 가능하지만 뒤로 가기는 불가하고, 첫 순회 후 시퀀스는 사라지지 않습니다.
bidirectional
: 뒤로 가기 --it
bidirectionalBidirectional 이터레이터는 편의성이 한 단계 올라간 것입니다: ++it에 더해 --it가 가능합니다. 마음속으로는 "뒤로 갈 수 있는 이터레이터"로 이해하면 되지만, 실무적 의미는 일부 알고리즘이 양방향 이동을 요구한다는 것입니다. 예를 들어 앞과 뒤에서 서로 만나며 처리하는 알고리즘이 있습니다.
Bidirectional 이터레이터의 전형적인 예로 std::map과 std::set의 이터레이터가 있습니다. 트리 기반 컨테이너는 순서대로 다음 및 이전 요소로 이동할 수 있지만, 여전히 "+100으로 점프"하는 것은 불가능합니다: 트리는 배열이 아니기 때문입니다.
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<int, std::string> users{{1, "Ann"}, {3, "Bob"}, {5, "Cat"}};
auto it = users.end();
--it; // 한 걸음 뒤로: 이제 마지막 요소입니다
std::cout << it->first << " " << it->second << '\n'; // 5 Cat
}
여기에서 철학적 차이가 보입니다: vector에서는 "마지막 요소"를 종종 인덱스나 back()으로 취급하지만, map에서는 자연스럽게 이터레이터로 이동합니다. map은 "순회를 위한 컨테이너"에 가깝고, 인덱스를 위한 컨테이너는 아닙니다.
중요한 추가 유의점: --users.end()는 유효합니다. 왜냐하면 end()는 "마지막 이후 위치"이고 한 걸음 뒤로 가면 마지막 요소가 되기 때문입니다. 반면에 --users.begin()를 시도하면 범위를 벗어나므로 해서는 안 됩니다.
random-access
: 점프, 인덱싱 및 차이 연산
random-accessRandom-access는 이터레이터의 "프리미엄 구독"입니다. 여기서는 배열을 닮은 모든 기능이 제공됩니다: n만큼 빠르게 점프(it + n), 인덱싱(it[n]), 순서 비교, 그리고 이터레이터 간 거리 계산(차이) 등이 가능합니다.
일반적인 random-access 이터레이터는 자주 접했을 것입니다, 이름을 붙여 부르지 않았다 해도: std::vector<T>::iterator와 std::string의 이터레이터가 대표적입니다.
#include <iostream>
#include <vector>
int main() {
std::vector<int> scores{10, 20, 30, 40};
auto it = scores.begin();
std::cout << it[2] << '\n'; // 30
std::cout << *(it + 3) << '\n'; // 40
}
이것이 STL에서 중요한 이유는 일부 알고리즘(예: std::sort)이 역사적으로 random-access 이터레이터를 요구하기 때문입니다(고전적인 STL 버전에서는). 따라서 컨테이너의 이터레이터가 random-access가 아니면 std::sort로 바로 정렬할 수 없습니다: 이는 악의가 아니라 알고리즘이 빠른 주소 지정 능력을 필요로 하기 때문입니다.
이 시점에서 카테고리는 단순한 꼬리표가 아니라 허용되는 연산과 알고리즘 적용 가능성에 대한 정직한 제약입니다.
5. 이동과 알고리즘의 요구
예제: 왜 it + n이 map에서 동작하지 않는가
매우 흔한 시나리오: vector에서 잘 동작하던 멋진 코드를 작성한 뒤, "거기 키가 있으니까" 하고 컨테이너를 map으로 바꿨더니 갑자기 많은 연산이 사라집니다. 이는 map이 "나쁘기" 때문이 아니라, 그 이터레이터가 다른 카테고리에 속하기 때문입니다.
다음 예제는 vector에서는 동작하는 코드이지만 map에서는 동작할 필요가 없는 코드입니다. 컴파일이 되도록 "문제가 되는 줄"을 주석 처리해 두었습니다:
#include <map>
#include <string>
int main() {
std::map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};
auto it = m.begin();
// it = it + 1; // 불가: map의 이터레이터는 random-access가 아닙니다
(void)it;
}
여기서 성숙한 습관이 중요해집니다: "n만큼 이동"이 필요하면, 먼저 이터레이터 카테고리를 확신하기 전까지는 it + n를 사용하지 마세요. 대신 다양한 카테고리에서 동작하는 범용 도구인 std::advance를 사용하세요.
std::advance(it, n) 와 연산 비용
std::advance는 단순한 편의 함수처럼 보이지만, 실제로는 올바른 사고를 반영합니다: 이터레이터를 n만큼 이동하고 싶지만 그 이터레이터가 random-access인지 가정하고 싶지 않다는 뜻입니다. 그러면 컴파일러와 표준 라이브러리가 적절한 방법을 선택합니다.
random-access 이터레이터에서는 보통 빠른 점프로 처리됩니다. 더 약한 카테고리에서는 이것이 n번의 ++it로 변환되며(그리고 이는 정상입니다), 비용이 발생한다는 점을 기억해야 합니다.
#include <iostream>
#include <iterator>
#include <map>
#include <string>
int main() {
std::map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};
auto it = m.begin();
std::advance(it, 2);
std::cout << it->second << '\n'; // three
}
알고리즘적 사고 관점에서 이것은 매우 유용합니다: 코드를 특정 컨테이너에 묶지 않게 해줍니다. 성능 관점에서는 정직한 대가가 존재합니다: 트리에서 advance로 1_000_000만큼 이동하면 실제로 백만 번의 단계가 수행됩니다. 따라서 범용성이 항상 무조건적인 정답은 아니며 상황에 맞게 판단해야 합니다.
카테고리에 따른 연산 선택 도식
모든 것을 "마법의 규칙"으로 외워두는 대신 다음과 같이 생각하면 편합니다: 먼저 컨테이너/이터레이터가 어떤 카테고리에 속하는지 파악한 뒤, 그에 맞는 허용 연산을 선택하세요. 아래는 기억을 돕는 간단한 도식입니다.
flowchart TD
A["컨테이너와 이터레이터 begin/end이 있다"] --> B["이터레이터 카테고리는 무엇인가?"]
B --> C["input: 읽기, ++"]
B --> D["forward: 읽기/쓰기, ++, 여러 번 순회 가능"]
B --> E["bidirectional: ++ 와 --"]
B --> F["random-access: ++/--, it+n, it[n], it2-it1"]
F --> G["random-access가 필요한 알고리즘(예: sort) 사용 가능"]
E --> H["뒤로 가기가 필요한 알고리즘(예: reverse) 가능"]
C --> I["스트림과 유사: 읽고 앞으로 이동"]
이 도식이 실습을 대체하지는 않지만, 가장 흔한 초보자의 결론인 "한 번 본 it[n]은 항상 존재한다"라는 오해를 방지하는 데 도움을 줍니다.
6. 이터레이터 카테고리 작업 시 흔한 실수들
실수 №1: 어떤 이터레이터든 vector::iterator처럼 보고 모든 곳에서 it + n을 기대하는 것.
이것은 가장 흔한 함정입니다: 배열처럼 코드를 작성해 두고 나중에 map/set으로 옮기면 연산자들이 사라진 것을 보고 당황합니다. 올바른 모델은 카테고리가 보장하는 것을 따르는 것입니다. 범용적인 이동이 필요하면 std::advance를 사용하고, 인덱스 접근이 빠르게 필요하면 random-access 이터레이터를 제공하는 컨테이너를 선택하세요.
실수 №2: "범용"과 "빠름"을 혼동하는 것.
std::advance를 알게 되면 "아, 이제 어디서나 10000건 점프해도 된다"고 생각하기 쉽습니다. 가능은 하지만 비용이 다릅니다. random-access에서는 it += 10000와 비슷하지만 더 약한 카테고리에서는 여러 번의 ++it로 변합니다. 결과적으로 코드는 올바르지만 성능이 의외로 안 좋을 수 있습니다.
실수 №3: input 이터레이터를 컨테이너처럼 여러 번 순회하려 시도하는 것.
std::istream_iterator와 유사한 이터레이터는 종종 스트림에서 데이터를 읽습니다: 이것은 "한 번만 읽는" 소스입니다. 한 번 앞으로 나가면 스트림 상태가 변경됩니다. 따라서 같은 데이터를 두 번째로 순회하려면 먼저 데이터를 컨테이너(예: std::vector)에 실체화(store)해야 합니다.
실수 №4: end()를 역참조하거나 경계를 넘어서는 연산을 하는 것.
end()는 "마지막"이 아니라 "마지막 이후" 위치이므로 역참조할 수 없습니다. 마찬가지로 --begin()이나 잘못된 위치에서의 연산은 범위를 벗어나며, 이런 오류는 항상 즉시 붕괴하지 않고 가끔 이상한 증상으로 나타나 디버깅을 어렵게 만듭니다.
실수 №5: 이터레이터 카테고리에 맞지 않는 알고리즘을 사용하려다 'STL의 버그'로 오해하는 것.
만약 std::sort가 여러분의 이터레이터로 컴파일되지 않는다면, 그것은 변덕이 아니라 알고리즘이 요구하는 이터레이터 능력이 충족되지 않았기 때문입니다. 이럴 때는 컴파일러와 싸우려 하기보다 "내 컨테이너가 랜덤 액세스를 지원하는가?" 또는 "나는 정렬이 아니라 다른 접근법(예: 트리 기반 정렬)을 선택해야 하는가?"를 먼저 고민하는 것이 더 생산적입니다.
GO TO FULL VERSION