[C++] std::distance, std::advance

(알고리즘 코드를 보다가 GPT를 통해서 얻은 답변을 따로 정리해둔 게시글이에요)

 

std::distance()와 std::advance() 함수는 C++ 표준 라이브러리에서 제공하는 반복자 관련 함수입니다. 이 두 함수는 반복자를 다루는 데 유용하게 사용될 수 있습니다.

std::distance()

std::distance(first, last) 함수는 두 개의 반복자 first와 last 사이의 거리를 계산하여 반환합니다. 이 함수는 다음과 같은 형태로 사용됩니다:

template <typename InputIt>
typename std::iterator_traits<InputIt>::difference_type
distance(InputIt first, InputIt last);

• first: 거리를 계산할 첫 번째 반복자
• last: 거리를 계산할 두 번째 반복자

반환값은 last에서 first까지의 거리이며, 이는 정수형(std::iterator_traits<InputIt>::difference_type)으로 반환됩니다. 예를 들어, std::distance(sequence.begin(), sequence.end())는 sequence 벡터의 요소 개수를 반환합니다.

std::advance()

std::advance() 함수는 반복자를 원하는 만큼 전진하거나 후퇴시키는 함수입니다. 다음과 같은 형태로 사용됩니다:

template <typename InputIt, typename Distance>
void advance(InputIt& it, Distance n);

• it: 전진할 반복자
• n: 이동할 거리(정수형)

이 함수는 it 반복자를 n만큼 전진(양수일 때) 또는 후퇴(음수일 때)시킵니다. 예를 들어, std::advance(first, 3)은 first 반복자를 세 번째 요소로 이동시킵니다.

EX) binary_search 함수에 적용

bool binary_search(int n, std::vector<int>& sequence) {
    auto first = sequence.begin();
    auto last = sequence.end();

    while (true) {
        auto range_length = std::distance(first, last);
        auto mid_index = std::floor(range_length / 2);  // 중간 인덱스 계산
        auto mid_element = *(first + mid_index);  // 중간 요소 가져오기

        // mid_element와 n 값을 비교하여 탐색 범위 조절
        if (mid_element == n) {
            return true;  // 원하는 값 찾은 경우
        } else if (mid_element > n) {
            std::advance(last, -mid_index);  // mid_element보다 큰 영역에서 탐색
        } else {
            std::advance(first, mid_index);  // mid_element보다 작은 영역에서 탐색
        }

        if (range_length == 1)
            return false;  // 범위의 길이가 1이면 찾지 못한 경우
    }
}

동작 설명

1. std::distance(first, last)를 사용하여 first와 last 사이의 거리(range_length)를 계산합니다.
2. std::floor(range_length / 2)를 통해 중간 인덱스(mid_index)를 계산합니다. 이때 std::floor() 함수는 정수 나눗셈의 소수점 이하를 버리기 위해 사용됩니다.
3. *(first + mid_index)를 통해 중간 요소(mid_element)를 가져옵니다.
4. mid_element와 n 값을 비교하여 탐색 범위를 조절합니다.
   • mid_element == n이면 원하는 값을 찾은 경우로 true를 반환합니다.
   • mid_element > n이면 last 반복자를 현재 위치에서 mid_index 만큼 전진시켜서 mid_element보다 큰 영역에서 탐색합니다.
   • 그 외의 경우(mid_element < n)는 first 반복자를 현재 위치에서 mid_index 만큼 전진시켜서 mid_element보다 작은 영역에서 탐색합니다.
5. 탐색을 반복하며 range_length가 1이 되면 찾지 못한 경우로 false를 반환합니다.

이와 같이 std::distance()와 std::advance() 함수를 이용하여 범위의 길이와 반복자를 조작하여 이진 탐색을 수행할 수 있습니다.