모두의 코드
C++ 레퍼런스 - std::lower_bound 와 upper_bound (<algorithm>)
lower_bound, upper_bound
<algorithm> 에 정의됨
// 참고로 C++ 20 부터 모두 constexpr 함수 이다. template <class ForwardIt, class T> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value); ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value); template <class ForwardIt, class T, class Compare> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp); ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);
lower_bound
범위 [first, last)
안의 원소들 중, value
보다 작지 않은 (크거나 같은) 첫 번째 원소를 리턴한다. 만일 그런 원소가 없다면 last
를 리턴한다. 이름 그대로 어떠한 값의 하한선 을 의미한다.
upper_bound
범위 [first, last)
안의 원소들 중, value
보다 큰 첫 번째 원소를 리턴한다. 만일 그런 원소가 없다면 last
를 리턴한다. 이름 그대로 어떠한 값의 상한선 을 의미한다.
이 때 위 두 함수가 작동하기 위해서는 범위안에 있는 원소들이 정렬된 상태여야 한다. 엄밀히 말하자면, lower_bound 함수의 경우 element < value
를 만족하는 모든 element
들은 해당 식을 만족하지 않는 원소들 보다 앞에 있어야 한다. 마찬가지로 upper_bound 의 경우 !(value < element) 를 만족하는 모든 element
들은 해당 식을 만족하지 않는 원소들 보다 앞에 있어야 한다. 물론, 범위 안에 있는 원소들이 정렬된 상태라면 해당 조건을 만족한다.
첫 번째 함수 버전은 operator<
를 사용해서 비교를 수행하고, 두 번째 버전은 Comp
함수를 사용해서 비교를 수행한다.
인자들
first, last
: 원소들의 범위를 나타내는 반복자. (각각 첫 번째 원소와 마지막 원소 바로 다음을 가리킴) 이 때 해당 원소들은 위의 조건에 맞게 정렬되어 있어야 한다.value
: 원소들의 값을 비교할 값comp
: 비교를 수행하는 이항 함수. 아래와 같은 꼴이어야 한다.
bool pred(const Type1 &a, const Type2 &b);
참고로 인자가 const&
일 필요는 없지만, 전달 받은 원소를 함수 내부에서 수정하면 안된다. 또한 Type1
과 Type2
는 반복자가 가리키고 있는 타입과 같거나 변환될 수 있어야 한다. 물론 알고리즘 내부적으로 pred
함수에 const
원소를 전달할 수 있으므로, Type1
과 Type2
가 const&
인 것이 좋다. (컴파일 오류가 발생할 수 도 있음)
참고로 ForwardIt
은 반드시 LegacyForwardIterator
를 만족해야 하며, Compare
은 반드시 BinaryPredicate
조건을 만족해야 한다.
리턴값
위 조건을 만족하는 반복자를 리턴한다. 이 때 해당 조건을 만족하는 반복자가 없을 시에 last
를 리턴한다.
시간 복잡도
전체 원소 개수에 로그에 비례한다. 즉 $O(\log(\text{last} - \text{first}))$ 이다.
구현 예시
lower_bound
template <class ForwardIt, class T> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value) { ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (*it < value) { first = ++it; count -= step + 1; } else count = step; } return first; }
upper_bound
template <class ForwardIt, class T> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value) { ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (!(value < *it)) { first = ++it; count -= step + 1; } else count = step; } return first; }
실행 예제
#include <algorithm> #include <iostream> #include <iterator> #include <vector> int main() { std::vector<int> data = {1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6}; auto lower = std::lower_bound(data.begin(), data.end(), 4); auto upper = std::upper_bound(data.begin(), data.end(), 4); std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " ")); return 0; }
실행 결과
4 4 4
참고 자료
equal_range
: 해당key
와 같이 같은 원소들의 범위를 리턴한다.partition : 두 그룹의 원소들로 파티션 한다.
댓글을 불러오는 중입니다..