upper_bound, lower_bound

개념

• upper_bound : n보다 큰 첫번째 수의 자리 (n-1 보다 작거나 같은 마지막 수의 자리 + 1)

  1 2 3 3 3 4 5 5 6

  ​ ↑ upper_bound of 4

• lower_bound : n 보다 크거나 같은 첫번째 수의 자리

  1 2 3 3 3 4 5 5 6

  ​ ↑ lower_bound of 3

• 범위구하기

  ​ 3 3 3 4

  [ lower_bound(3), upper_bound(4) )

코드

#include <iostream>
#include <vector>
#include <algorithm> //lower_bound, upper_bound
using namespace std;
class pii
{
public:
int first;
int second;
pii() {}
pii(int f, int s) : first(f), second(s) {}
};

bool compare(const pii& lhs, const pii& rhs)
{
return lhs.second < rhs.second;
}

int main(void)
{
vector vec;
vec.push_back(pii(1, 1));
vec.push_back(pii(2, 1));
vec.push_back(pii(4, 3));
vec.push_back(pii(3, 5));

vector<pii>::iterator ub = upper_bound(vec.begin(), vec.end(), pii(0, 3), compare);

cout << ub->first << endl; //3을 초과하는 첫번째 element

return 0;