25. c++ stl lower_bound() upper_bound()

▶ stl  lower_bound() upper_bound()에 대해 알아보도록 하겠습니다.

▷ a.lower_bound(k) - k보다 작지 않은 값의 키를 갖는 첫번째 원소를 가리키는 이터레이터 반환

▷ a.upper_bound(k) - k보다 큰 값을 갖는 첫번째 키를 갖는 첫번째 원소를 가리키는 이터레이터 반환

▷ lower_bound(p, q, v) - [p, q]구간에서 v와 값이 같은 첫번째 원소를 가리키는 이터레이터 반환

▷ upper_bound(p, q, v) - [p, q]구간에서 v보다 값이 큰 첫번째 원소를 가리키는 이터레이터 반환

 

[  lower_bound() upper_bound() 예제 1]

#include <stdio.h> 
using namespace std; 

int main() 
{ 
	int arr[10] = {2, 6, 10, 16, 16,  12, 28, 30, 50, 52}; 
	
	int *t = lower_bound( &arr[0], &arr[10], 16); 
	int *y = upper_bound( &arr[0], &arr[10], 16); 
	
	printf("index = %d\n", t - arr);
	printf("값출력= %d\n", *t);
			
	printf("index = %d\n", y - arr);
	printf("값출력= %d\n", *y);

	return 0; 
}

※ lower_bound는우리가 찾고자 하는 16의 위치를 반환합니다.

※ upper_bound는우리가 찾고자 하는 16을 지나쳐 다음 원소의 위치를 반환합니다.

※ lower_boune 는 “어디서부터 시작하니?”, upper_bound는 “어디서 끝나?” 라고 물어 답을 얻어오는 것이다.

 

[  lower_bound() upper_bound() 예제 2]

< 입력데이터 >

5

3 1 2 7 8

#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
int main()
{
	int i, n, data;
	set<int> A;

	scanf("%d", &n);
    
	for(i=0;i<n;i++)
	{
		scanf("%d", &data);
		A.insert(data);
	}
    
//set내용출력
	set<int>::iterator str;
	for(str=A.begin(); str!=A.end(); str++)
	{
		printf("%d\n", *str);
	}
	printf("=============\n");

//4보다큰수중작은값의위치출력
	set<int>::iterator t=lower_bound(A.begin(), A.end(), 4);
	printf("%d\n", *t);
	A.erase(t);
	printf("=============\n");

//4보다큰수삭제후출력
	for(str=A.begin(); str!=A.end(); str++)
	{
		printf("%d\n", *str);
	}	
	return 0;
}

 

[  lower_bound() upper_bound() 예제 3 ]

< 입력데이터 > 

6

7 1

7 2

7 3

7 4

7 15

7 25

#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<int, int> ci;
multiset <ci> A;

int main()
{
	int i, n, data, no;
	ci t, q;
	scanf("%d", &n);
	for(i=0;i<n;i++)
	{
		scanf("%d %d", &no, &data);
		t = make_pair(no, data);
		A.insert(t);
	}
    
//set내용출력
	multiset<ci>::iterator str;
	for(str=A.begin(); str!=A.end(); str++)
	{
		t = *str;
		printf("%d %d\n", t.first, t.second);
	}
	printf("=============\n");
    
//(7, 10)보다큰수중작은값찾기
	q = make_pair (7, 10);
	multiset<ci>::iterator d;
	d = A.lower_bound(q);
	printf("%d\n", *d);
	A.erase(d);
	printf("=============\n");

//set내용출력
	for(str=A.begin(); str!=A.end(); str++)
	{
		t = *str;
		printf("%d %d\n", t.first, t.second);
	}
	printf("=============\n");

	return 0;
}