참고자료
c++.com : http://cplusplus.com/reference/
일반적프로그래밍과 STL책.
저도 잘 모르는 내용이지만 제 임의대로 제가 기억하려고 올리는 것이므로 태클 환영합니다.
Lower_bound : 2진검색 알고리즘. 구간 first-last안에서 value를 찾는다. value보다 작지않은 첫번째 인자를 리턴해줌.
|
template <class ForwardIterator, class T> ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value ) { ForwardIterator it; iterator_traits<ForwardIterator>::distance_type count, step; count = distance(first,last); while (count>0) { it = first; step=count/2; advance (it,step); if (*it<value) // or: if (comp(*it,value)), for the comp version { first=++it; count-=step+1; } else count=step; } return first; } |
Upper_bound : 정렬된 구간 first-last사이에서 value를 찾는 2진검색 알고리즘. 정렬순서를 위반하지않고 value를 assign할 수 있는 위치를 리턴해줌.
|
template <class ForwardIterator, class T> ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value ) { ForwardIterator it; iterator_traits<ForwardIterator>::distance_type count, step; count = distance(first,last); while (count>0) { it = first; step=count/2; advance (it,step); if (!(value<*it)) // or: if (!comp(value,*it)), for the comp version { first=++it; count-=step+1; } else count=step; } return first; } |
Equal_range : 정렬된 구간 first-last사이에서 value를 찾는다. 순서를 깨지않고 value를 삽입할 수 있는 첫번째 반복자(lower_bound)와 마지막 반복자(upper_bound)로 된 하나의 pair임. 즉, lower_bound와 upper_bound를 합친것임.
|
template <class ForwardIterator, class T> pair<ForwardIterator,ForwardIterator> equal_range ( ForwardIterator first, ForwardIterator last, const T& value ) { ForwardIterator it = lower_bound (first,last,value); return make_pair ( it, upper_bound(it,last,value) ); } |
Binary_search : 정렬된 구간에서 value와 같은 값을 가진 요소를 찾으면 true, 아니면 false
|
template <class ForwardIterator, class T> bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value ) { first = lower_bound(first,last,value); return (first!=last && !(value<*first)); } |
댓글