Functions | |
template<typename _ForwardIter, typename _Tp> _ForwardIter | std::lower_bound (_ForwardIter __first, _ForwardIter __last, const _Tp &__val) |
Finds the first position in which val could be inserted without changing the ordering. | |
template<typename _ForwardIter, typename _Tp, typename _Compare> _ForwardIter | std::lower_bound (_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare __comp) |
Finds the first position in which val could be inserted without changing the ordering. | |
template<typename _ForwardIter, typename _Tp> _ForwardIter | std::upper_bound (_ForwardIter __first, _ForwardIter __last, const _Tp &__val) |
Finds the last position in which val could be inserted without changing the ordering. | |
template<typename _ForwardIter, typename _Tp, typename _Compare> _ForwardIter | std::upper_bound (_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare __comp) |
Finds the last position in which val could be inserted without changing the ordering. | |
template<typename _ForwardIter, typename _Tp> pair< _ForwardIter, _ForwardIter > | std::equal_range (_ForwardIter __first, _ForwardIter __last, const _Tp &__val) |
Finds the largest subrange in which val could be inserted at any place in it without changing the ordering. | |
template<typename _ForwardIter, typename _Tp, typename _Compare> pair< _ForwardIter, _ForwardIter > | std::equal_range (_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare __comp) |
Finds the largest subrange in which val could be inserted at any place in it without changing the ordering. | |
template<typename _ForwardIter, typename _Tp> bool | std::binary_search (_ForwardIter __first, _ForwardIter __last, const _Tp &__val) |
Determines whether an element exists in a range. | |
template<typename _ForwardIter, typename _Tp, typename _Compare> bool | std::binary_search (_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare __comp) |
Determines whether an element exists in a range. |
The number of comparisons will be logarithmic (and as few as possible). The number of steps through the sequence will be logarithmic for random-access iterators (e.g., pointers), and linear otherwise.
The LWG has passed Defect Report 270, which notes: The proposed resolution reinterprets binary search. Instead of thinking about searching for a value in a sorted range, we view that as an important special case of a more general algorithm: searching for the partition point in a partitioned range. We also add a guarantee that the old wording did not: we ensure that the upper bound is no earlier than the lower bound, that the pair returned by equal_range is a valid range, and that the first part of that pair is the lower bound.
The actual effect of the first sentence is that a comparison functor passed by the user doesn't necessarily need to induce a strict weak ordering relation. Rather, it partitions the range.
|
Determines whether an element exists in a range.
The comparison function should have the same effects on ordering as the function used for the initial sort. Definition at line 3086 of file stl_algo.h. References std::lower_bound(). |
|
Determines whether an element exists in a range.
Definition at line 3055 of file stl_algo.h. References std::lower_bound(). |
|
Finds the largest subrange in which val could be inserted at any place in it without changing the ordering.
but does not actually call those functions. Definition at line 3006 of file stl_algo.h. References std::advance(), std::distance(), std::lower_bound(), and std::upper_bound(). |
|
Finds the largest subrange in which val could be inserted at any place in it without changing the ordering.
but does not actually call those functions. Definition at line 2951 of file stl_algo.h. References std::advance(), std::distance(), std::lower_bound(), and std::upper_bound(). |
|
Finds the first position in which val could be inserted without changing the ordering.
Definition at line 2819 of file stl_algo.h. References std::advance(), and std::distance(). |
|
Finds the first position in which val could be inserted without changing the ordering.
Definition at line 2771 of file stl_algo.h. References std::advance(), and std::distance(). Referenced by std::binary_search(), std::equal_range(), and std::map< _Key, _Tp, _Compare, _Alloc >::operator[](). |
|
Finds the last position in which val could be inserted without changing the ordering.
Definition at line 2904 of file stl_algo.h. References std::advance(), and std::distance(). |
|
Finds the last position in which val could be inserted without changing the ordering.
Definition at line 2859 of file stl_algo.h. References std::advance(), and std::distance(). Referenced by std::equal_range(). |