C++ std::upper_bound with std::vector
DESCRIPTION:
This C++ article is about the upper_bound() algorithm function. It is an STL algorithm in <algorithm> header file. It returns an iterator pointing to the first element in the range
upper_bound() has two definition:
1)
template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
2)
template <class ForwardIterator, class T, class Compare> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
The elements are compared using
The function optimizes the number of comparisons performed by comparing
non-consecutive elements of the sorted range, which is specially
efficient for random-access iterators.
Unlike lower_bound, the value pointed by the iterator returned by this function cannot be equivalent to val, only greater.
Input:-
first, last
comp
This can either be a function pointer or a function object.
This article deals with the first definition.
The behavior of this function template is equivalent to:
template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val) { ForwardIterator it; iterator_traits<ForwardIterator>::difference_type count, step; count = std::distance(first,last); while (count>0) { it = first; step=count/2; std::advance (it,step); if (!(val<*it)) // or: if (!comp(val,*it)), for version (2) { first=++it; count-=step+1; } else count=step; } return first; }
IMPLEMENTATION:
using namespace std; int main () { int myints[] = {1,2,3,3,2,1,1,2}; vector<int> v(myints,myints+8); sort (v.begin(), v.end()); vector<int>::iterator up; up= std::upper_bound (v.begin(), v.end(), 2); std::cout << "upper_bound at position " << (up - v.begin()) << '\n'; return 0; }
OUTPUT:
upper_bound at position 6
This C++ article is about the upper_bound() algorithm function. It is an STL algorithm in <algorithm> header file. It returns an iterator pointing to the first element in the range
[first,last) which compares greater than val.upper_bound() has two definition:
1)
template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
2)
template <class ForwardIterator, class T, class Compare> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
The elements are compared using
operator< for the first version, and comp for the second. The elements in the range shall already be sorted according to this same criterion (operator< or comp), or at least partitioned with respect to val.The function optimizes the number of comparisons performed by comparing
non-consecutive elements of the sorted range, which is specially
efficient for random-access iterators.
Unlike lower_bound, the value pointed by the iterator returned by this function cannot be equivalent to val, only greater.
Input:-
first, last
Forward iterators to the initial and final positions of a sorted (or properly partitioned) sequence. The range used
is [first,last), which contains all the elements between first and last, including the element pointed by first but not
the element pointed by last.
val
Value of the upper bound to search for in the range. For (1), T shall be a type supporting being compared with elements of the range [first,last) as the left-hand
side operand of operator < .
Binary function that accepts two arguments (the first is always val, and the second of the type pointed
by ForwardIterator), and returns a value convertible to bool. The value returned indicates whether the
first argument is considered to go before the second.
The function shall not modify any of its arguments.This can either be a function pointer or a function object.
This article deals with the first definition.
The behavior of this function template is equivalent to:
template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val) { ForwardIterator it; iterator_traits<ForwardIterator>::difference_type count, step; count = std::distance(first,last); while (count>0) { it = first; step=count/2; std::advance (it,step); if (!(val<*it)) // or: if (!comp(val,*it)), for version (2) { first=++it; count-=step+1; } else count=step; } return first; }
IMPLEMENTATION:
using namespace std; int main () { int myints[] = {1,2,3,3,2,1,1,2}; vector<int> v(myints,myints+8); sort (v.begin(), v.end()); vector<int>::iterator up; up= std::upper_bound (v.begin(), v.end(), 2); std::cout << "upper_bound at position " << (up - v.begin()) << '\n'; return 0; }
OUTPUT:
upper_bound at position 6
Comments