lower_bound와 upper_bound

둘 다 ForwardIterator, 즉 증가 연산 (++) 이 되는 iterator를 가진 컨테이너에 대해 동작한다.

즉,  vector, set, multiset, map, multimap ... 등에서 동작한다.

 

* lower_bound는, 첫 원소의 iterator에서 시작하여 iterator을 ++증가시키며 탐색하다가,

   '비교 결과 주어진 값보다 먼저 나오지 않는(not compare less than) 첫 원소'의 iterator를 반환한다.

* upper_bound는, 첫 원소의 iterator에서 시작하여 iterator을 ++증가시키며 탐색하는 것은 동일하나,

   '비교 결과 주어진 값보다 나중에 나오는(compare greater than) 첫 원소'의 iterator를 반환한다.

 

두 개가 똑같은 것처럼 보이지만, 사실 다르다.

 

예를 들어 보면, 벡터에 { 10, 20, 20, 20, 30, 40, 50 } 이 있다고 하자.

- lower_bound(20)은, 인자로 주어진 값 20보다 먼저 나오지 않는 첫 원소가 맨 왼쪽의 '20' 이므로, 그 원소의 iterator 반환.

- upper_bound(20)은, 20보다 나중에 나올 수 있는 첫 원소가 30이므로, 30의 iterator 반환.

 

다른 예를 들어보면,

- lower_bound(23) 은 30의 iterator를 반환한다. 23보다 작지 않은 최초의 원소는 30이기 때문이다.

- upper_bound(23) 또한 30의 iterator를 반환한다. 23보다 큰 최초의 원소 역시 30이기 때문이다.

 

이러한 이유로 정렬 된 상태에서 쓰는 것이 보통이며,

탐색 범위를 지정할 수 있어서, 범위를 지정하는 경우 그 범위만 정렬되어 있어도 상관없다.

 

더 자세한 사항은 : http://www.cplusplus.com/reference/algorithm/lower_bound/

 

--------------------------------------------------------------------------

Q. 처음 set을 만들 때 greater<int>() 으로 만들어져 있는 경우라면, lower_bound는 어떻게 동작할 것인가?

A. 직접 만들어보았다.

#include      // cout
#include     // lower_bound, upper_bound, sort
#include        // vector
using namespace std;

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  vector v(myints,myints+8);							// 10 20 30 30 20 10 10 20

  vector::iterator low,up;
  
  sort (v.begin(), v.end(), greater());						// 30 30 20 20 20 10 10 10  
  low = lower_bound (v.begin(), v.end(), 20, greater());		//        ^   
  up  = upper_bound (v.begin(), v.end(), 20, greater());		//                 ^

  cout << "lower_bound at position " << (low - v.begin()) << '\n';
  cout << "upper_bound at position " << (up  - v.begin()) << '\n';

  return 0;
}

 

결과는 다음과 같이 잘 동작한다.

lower_bound at position 2

upper_bound at position 5

 

위의 코드에서 주의할 점은, sort에도 greater<int>를, lower_ / upper_bound 에도 greater<int>를 써 주었다는 것이다.

이를 통일시키지 않은 경우, 이상한 결과가 나오는데 해석할 수가 없었다.

--------------------------------------------------------------------------

 

*** Important

위에서 소개한 lower_bound는 ForwardIterator만 있으면 사용 가능한 lower_bound이다.

그런데, map와 set의 경우, 각 컨테이너별로 독립적인 lower_bound가 존재한다.

(그들만의 독특한 트리 구조로 인해, 속도 향상을 목적으로 다르게 구현한 것 같다.)

 

이 각각의 lower_bound는 인자를 딱 하나밖에 받지 않으며, 객체에 소속된 함수를 호출하는 방식이다.

(ex. set<int> s;    s.lower_bound(20); )

(set 에서는 greater<int>와 같은 것을 쓸 수 없는 것 같다. 이건 정확히는 잘 모르겠다.)