C++ 반복자 이동과 거리 계산, std::advance와 std::distance 완전 정리

🔗 std::advance란 무엇인가요?

C++ STL에서 std::advance는 반복자를 원하는 위치만큼 이동시켜주는 유틸리티 함수입니다.
즉, 현재 반복자 위치에서 지정한 만큼 앞으로 또는 뒤로 이동시키고 싶을 때 사용하는 함수죠.
이 함수는 특히 list처럼 인덱스로 직접 접근할 수 없는 컨테이너에서 매우 유용하게 쓰입니다.

사용 방법은 간단합니다.
반복자와 정수 값을 인자로 전달하면, 반복자가 해당 수만큼 이동됩니다.
음수를 전달하면 반대로 이동할 수도 있어요.

std::list<int> myList = {10, 20, 30, 40, 50};
auto it = myList.begin();
std::advance(it, 2);
// 이제 it는 30을 가리킴

이처럼 std::advance는 반복자 자체를 반환하지 않고, 전달된 반복자 자체를 변경한다는 특징이 있습니다.
원본 반복자를 이동시키기 때문에 주의해서 사용해야 해요.

🛠️ std::distance는 어떤 역할인가요?

std::distance는 C++ STL에서 두 반복자 간의 거리를 계산할 때 사용되는 함수입니다.
시작 반복자와 끝 반복자를 인자로 넘기면, 그 사이에 있는 요소 개수를 정수 값으로 반환해줍니다.
list, set, map처럼 인덱스로 접근할 수 없는 컨테이너에서 요소 간 위치 차이를 알고 싶을 때 매우 유용하죠.

사용 방법도 간단합니다.
두 반복자를 넘기기만 하면 끝입니다.
단, 두 반복자는 같은 컨테이너 내에 있어야 하며, 시작 반복자가 앞쪽에 위치해야 해요.

std::list<int> nums = {10, 20, 30, 40, 50};
auto begin = nums.begin();
auto end = nums.end();
int count = std::distance(begin, end); // 결과: 5

이처럼 반복자를 통해 컨테이너 내부의 거리 정보를 알 수 있기 때문에, 범위 기반 루프를 직접 구성하거나, 중간 위치 계산에도 활용할 수 있습니다.
또한 알고리즘 내부에서 iterator 범위 유효성 검사에도 종종 쓰여요.

⚙️ list, set, vector에서의 활용 차이

반복자 관련 함수들은 모든 컨테이너에서 동일하게 동작하지 않습니다.
그 이유는 컨테이너가 제공하는 반복자의 종류가 서로 다르기 때문인데요.
C++ STL 컨테이너들은 iterator category에 따라 반복자의 기능과 성능이 달라집니다.

아래에서 각각의 대표 컨테이너에서 std::advance와 std::distance가 어떤 차이로 동작하는지 살펴보겠습니다.

• 🔁list: 반복자 이동 시 노드를 하나하나 순회해야 하므로 advance와 distance 모두 O(n)
• 🌲set: 내부적으로 균형 이진 트리 구조라서 이동 시에도 O(log n) 정도의 성능, distance는 O(n)
• ⚡vector: random access가 가능하므로 advance와 distance 모두 O(1)

이처럼 컨테이너에 따라 반복자의 성능이 달라지기 때문에, 동일한 함수라도 실행 속도는 매우 차이날 수 있습니다.
특히 list나 set처럼 직접 접근이 불가능한 컨테이너에서는 advance나 distance의 호출 횟수 자체를 줄이는 것이 핵심입니다.

🔌 반복자 카테고리에 따른 성능 차이

C++ STL에서 반복자는 단순히 컨테이너를 순회하는 도구에 그치지 않고, 동작 방식에 따라 분류됩니다.
이러한 분류를 iterator category라고 하며, 이는 반복자가 지원하는 기능과 성능에 직접적인 영향을 미칩니다.

대표적인 반복자 카테고리는 다음과 같으며, advance나 distance 사용 시 내부 동작 방식이 달라집니다.

• ➡️InputIterator: 단방향 이동만 가능, advance는 순차적 반복
• ↔️BidirectionalIterator: 양방향 이동 가능, list 등에서 사용
• 🚀RandomAccessIterator: 인덱스 기반 점프 가능, advance는 단순 덧셈처럼 작동

이러한 차이점 때문에 동일한 advance, distance 함수를 호출하더라도 성능이 크게 달라질 수 있습니다.
예를 들어 vector는 RandomAccessIterator이기 때문에 advance(it, 1000)을 해도 바로 이동하지만, list에서는 내부적으로 1,000번 ++ 연산이 일어나죠.

따라서 반복자를 다룰 때는 문법만 외우지 말고, 반복자의 카테고리를 정확히 이해하고 사용하는 것이 중요합니다.
특히 대규모 데이터를 처리할 때 성능 차이가 수십 배 이상 벌어질 수 있기 때문에, 실전 코드에서는 반드시 고려해야 할 요소예요.

💡 advance와 distance 사용 시 주의할 점

반복자 관련 함수는 문법은 단순해 보여도, 실제 사용할 때는 몇 가지 주의할 점이 있습니다.
특히 컨테이너 구조와 반복자의 특성을 이해하지 못하면 의도치 않은 오류나 성능 저하가 발생할 수 있어요.

다음은 advance와 distance를 사용할 때 꼭 유의해야 할 사항들입니다.

• ⚠️advance는 원본 반복자를 직접 변경합니다. 복사본이 필요한 경우 미리 복제해서 써야 해요.
• 📏distance는 두 반복자의 상대 위치를 기준으로 계산되며, 순서가 바뀌면 음수가 반환될 수 있어요.
• 🐢list나 set에서는 advance, distance가 선형 시간이 걸리므로 루프 안에서 반복 호출하면 성능 저하 발생
• 🚫advance의 거리 값이 너무 크면 end()를 초과할 수 있어 segmentation fault 발생 위험
• 🧭distance 사용 전에는 반드시 두 반복자가 동일한 컨테이너 소속인지 확인해야 합니다

❓ 자주 묻는 질문 (FAQ)