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 : 두 그룹의 원소들로 파티션 한다.

댓글이 1 개 있습니다!

강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요

다음으로 로그인

또는 직접 입력하세요 (댓글 수정시 비밀번호가 필요합니다)

댓글 달기

댓글을 불러오는 중입니다..