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 4260 of file stl_algo.h. References __glibcxx_function_requires, __glibcxx_requires_partitioned_pred, and std::lower_bound(). |
|
Determines whether an element exists in a range.
Definition at line 4228 of file stl_algo.h. References __glibcxx_function_requires, __glibcxx_requires_partitioned, and std::lower_bound(). |
|
Finds the largest subrange in which val could be inserted at any place in it without changing the ordering.
std::make_pair(lower_bound(first, last, val, comp), upper_bound(first, last, val, comp)) Definition at line 4170 of file stl_algo.h. References __glibcxx_function_requires, __glibcxx_requires_partitioned_pred, 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 2934 of file stl_algo.h. References __glibcxx_function_requires, __glibcxx_requires_partitioned_pred, std::advance(), and std::distance(). |
|
Finds the first position in which val could be inserted without changing the ordering.
Definition at line 2884 of file stl_algo.h. References __glibcxx_function_requires, __glibcxx_requires_partitioned, std::advance(), and std::distance(). Referenced by std::__merge_adaptive(), std::__merge_without_buffer(), __gnu_cxx::__stl_next_prime(), std::tr1::__detail::_Prime_rehash_policy::_M_bkt_for_elements(), std::tr1::__detail::_Prime_rehash_policy::_M_need_rehash(), std::tr1::__detail::_Prime_rehash_policy::_M_next_bkt(), std::map< _Key, _Tp, _Compare, _Allocator >::at(), std::binary_search(), std::equal_range(), and std::map< _Key, _Tp, _Compare, _Allocator >::operator[](). |
|
Finds the last position in which val could be inserted without changing the ordering.
Definition at line 3031 of file stl_algo.h. References __glibcxx_function_requires, __glibcxx_requires_partitioned_pred, std::advance(), and std::distance(). |
|
Finds the last position in which val could be inserted without changing the ordering.
Definition at line 2981 of file stl_algo.h. References __glibcxx_function_requires, __glibcxx_requires_partitioned, std::advance(), and std::distance(). Referenced by std::__merge_adaptive(), std::__merge_without_buffer(), and std::equal_range(). |