September 24, 2021
// Default
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
// Custom
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
[first, last) 범위에서 val보다 작지 않은 첫 번째 원소를 가리키는 iterator를 반환한다. 즉, iterator가 가리키는 원소는 val과 같거나 더 크다.
범위 내의 모든 원소는 정렬되거나 val에 대하여 partitioned이어야 한다.
// Default
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
// Custom
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
[first, last) 범위에서 val보다 큰 첫 번째 원소를 가리키는 iterator를 반환한다. 따라서, 반환되는 iterator가 가리키는 원소는 val보다 크다.
범위 내의 모든 원소는 정렬되거나 val에 대하여 partitioned이어야 한다.
기본적으로 두 함수는 operator<를 기준으로 동작한다. 다음을 이용하면 새로운 기준으로 함수를 동작시킬 수 있다.
// 반환 값은 첫 번째 인자가 두 번째 인자 이전인지를 의미한다.
bool compare(T& a, T& b) {
// ...
}
<aside> 💡 lower_bound와 upper_bound 함수는 binary search 알고리즘을 이용한다.
</aside>