map
map<(key의 자료형), (value의 자료형)> m;
m["ABC"] = 1; // map에 데이터 추가
m.insert({"ABC", 1}); // insert(pair)로 추가 가능upper_bound(), lower_bound()
map, set은 upper_bound, lower_bound 메서드를 갖고 있다.
두 메서드를 쓰기 위해서는 컨테이너가 정렬되어 있어야 한다.
upper_bound(begin, end, target) : [begin, end) 에서 target보다 크거나 같은 첫 번째 원소 리턴, 없다면 last 리턴
lower_bound(begin, end, target) : [begin, end) 에서 target보다 큰 첫 번째 원소를 리턴, 없다면 last 리턴
vector<int> arr = {1, 2, 3, 4, 4, 5, 5, 5, 5, 6, 7, 8};
auto lower = lower_bound(arr.begin(), arr.end(), 5);
auto upper = upper_bound(arr.begin(), arr.end(), 5);
cout<<*lower<<' '<<*upper<<endl; // 5 6파이썬의 bisect 라이브러리 bisect_left, bisect_right와 같은 동작을 한다!
관련 문제
상한, 하한을 필요로 하는 문제에서 유용하다.
백준 19637번
