241128 배운 점 - c++ equal_range()와 distance()

참고자료

• claude.ai
• c++ std::equal_range() 관련 자료

https://en.cppreference.com/w/cpp/algorithm/equal_range#:~:text=Although%20std::equal_range%20only%20requires%20[%20first%20%2C,binary%20search%20is%20valid%20for%20any%20value.&text=%E2%86%91%20Applying%20equal_range%20to%20a%20single%2Delement%20range,comparison%20is%20allowed%20by%20the%20complexity%20requirement.

시간 복잡도

O(logn)이다.

설명

std::equal_range 함수는 정렬된 범위에서 특정 값의 첫 번째와 마지막 위치를 반환합니다. 반환값은 pair<iterator, iterator> 형식으로, 첫 번째 반복자는 범위의 시작을 가리키고, 두 번째 반복자는 범위의 끝을 가리킵니다. std::distance 함수는 두 반복자 사이의 거리를 반환합니다.

다음은 std::equal_range와 std::distance의 동작 방식 및 반환값을 설명하는 예시입니다:

예시 배열

vector<int> CD = {1, 2, 2, 3, 4, 5};

찾는 값이 없을 때

예를 들어, target이 6인 경우:

int target = 6;
auto range = equal_range(CD.begin(), CD.end(), target);
int count = distance(range.first, range.second);

• range.first와 range.second는 모두 CD.end()를 가리킵니다.
• count는 0입니다.

찾는 값이 1개 있을 때

예를 들어, target이 3인 경우:

int target = 3;
auto range = equal_range(CD.begin(), CD.end(), target);
int count = distance(range.first, range.second);

• range.first는 CD에서 3의 위치를 가리킵니다.
• range.second는 3 다음의 위치를 가리킵니다.
• count는 1입니다.

찾는 값이 2개 이상 있을 때

예를 들어, target이 2인 경우:

int target = 2;
auto range = equal_range(CD.begin(), CD.end(), target);
int count = distance(range.first, range.second);

• range.first는 CD에서 첫 번째 2의 위치를 가리킵니다.
• range.second는 마지막 2 다음의 위치를 가리킵니다.
• count는 2입니다.

요약

• 값이 없을 때: range.first와 range.second는 모두 CD.end()를 가리키며, count는 0입니다.
• 값이 1개 있을 때: range.first는 값의 위치를, range.secon는 그 다음 위치를 가리키며, count는 1입니다.
• 값이 2개 이상 있을 때: range.first는 첫 번째 값의 위치를, range.second는 마지막 값 다음의 위치를 가리키며, count는 값의 개수입니다.