Functions | |
template<typename ForwardIterator, typename Type> | |
ForwardIterator | std::lower_bound (ForwardIterator first, ForwardIterator last, const Type &__val) |
Finds the first position in which val could be inserted without changing the ordering. | |
template<typename ForwardIterator, typename Type, typename Compare> | |
ForwardIterator | std::lower_bound (ForwardIterator first, ForwardIterator last, const Type &__val, Compare comp) |
Finds the first position in which val could be inserted without changing the ordering. | |
template<typename ForwardIterator, typename Type> | |
ForwardIterator | std::upper_bound (ForwardIterator first, ForwardIterator last, const Type &__val) |
Finds the last position in which val could be inserted without changing the ordering. | |
template<typename ForwardIterator, typename Type, typename Compare> | |
ForwardIterator | std::upper_bound (ForwardIterator first, ForwardIterator last, const Type &__val, Compare comp) |
Finds the last position in which val could be inserted without changing the ordering. | |
template<typename ForwardIterator, typename Type> | |
pair< ForwardIterator, ForwardIterator > | std::equal_range (ForwardIterator first, ForwardIterator last, const Type &__val) |
Finds the largest subrange in which val could be inserted at any place in it without changing the ordering. | |
template<typename ForwardIterator, typename Type, typename Compare> | |
pair< ForwardIterator, ForwardIterator > | std::equal_range (ForwardIterator first, ForwardIterator last, const Type &__val, Compare comp) |
Finds the largest subrange in which val could be inserted at any place in it without changing the ordering. | |
template<typename ForwardIterator, typename Type> | |
bool | std::binary_search (ForwardIterator first, ForwardIterator last, const Type &__val) |
Determines whether an element exists in a range. | |
template<typename ForwardIterator, typename Type, typename Compare> | |
bool | std::binary_search (ForwardIterator first, ForwardIterator last, const Type &__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.
bool std::binary_search | ( | ForwardIterator | first, | |
ForwardIterator | last, | |||
const Type & | __val, | |||
Compare | comp | |||
) |
Determines whether an element exists in a range.
first | An iterator. | |
last | Another iterator. | |
val | The search term. | |
comp | A functor to use for comparisons. |
The comparison function should have the same effects on ordering as the function used for the initial sort.
Definition at line 3938 of file stl_algo.h.
References __glibcxx_function_requires, and std::lower_bound().
bool std::binary_search | ( | ForwardIterator | first, | |
ForwardIterator | last, | |||
const Type & | __val | |||
) |
Determines whether an element exists in a range.
first | An iterator. | |
last | Another iterator. | |
val | The search term. |
Definition at line 3906 of file stl_algo.h.
References __glibcxx_function_requires, and std::lower_bound().
pair<ForwardIterator, ForwardIterator> std::equal_range | ( | ForwardIterator | first, | |
ForwardIterator | last, | |||
const Type & | __val, | |||
Compare | comp | |||
) |
Finds the largest subrange in which val could be inserted at any place in it without changing the ordering.
first | An iterator. | |
last | Another iterator. | |
val | The search term. | |
comp | A functor to use for comparisons. |
std::make_pair(lower_bound(first, last, val, comp), upper_bound(first, last, val, comp))
Definition at line 3848 of file stl_algo.h.
References __glibcxx_function_requires, std::advance(), std::distance(), std::lower_bound(), and std::upper_bound().
pair<ForwardIterator, ForwardIterator> std::equal_range | ( | ForwardIterator | first, | |
ForwardIterator | last, | |||
const Type & | __val | |||
) |
Finds the largest subrange in which val could be inserted at any place in it without changing the ordering.
first | An iterator. | |
last | Another iterator. | |
val | The search term. |
std::make_pair(lower_bound(first, last, val), upper_bound(first, last, val))
Definition at line 3786 of file stl_algo.h.
References __glibcxx_function_requires, std::advance(), std::distance(), std::lower_bound(), and std::upper_bound().
Referenced by __gnu_debug_def::set< Key, Compare, Allocator >::equal_range(), __gnu_debug_def::multiset< Key, Compare, Allocator >::equal_range(), __gnu_debug_def::multimap< Key, Type, Compare, Allocator >::equal_range(), __gnu_debug_def::map< Key, Type, Compare, Allocator >::equal_range(), __gnu_debug_def::hash_set< Value, HashFcn, EqualKey, Alloc >::equal_range(), __gnu_debug_def::hash_multiset< Value, HashFcn, EqualKey, Alloc >::equal_range(), __gnu_debug_def::hash_multimap< Value, Type, HashFcn, EqualKey, Alloc >::equal_range(), and __gnu_debug_def::hash_map< Value, Type, HashFcn, EqualKey, Alloc >::equal_range().
ForwardIterator std::lower_bound | ( | ForwardIterator | first, | |
ForwardIterator | last, | |||
const Type & | __val, | |||
Compare | comp | |||
) |
Finds the first position in which val could be inserted without changing the ordering.
first | An iterator. | |
last | Another iterator. | |
val | The search term. | |
comp | A functor to use for comparisons. |
Definition at line 2662 of file stl_algo.h.
References __glibcxx_function_requires, std::advance(), and std::distance().
ForwardIterator std::lower_bound | ( | ForwardIterator | first, | |
ForwardIterator | last, | |||
const Type & | __val | |||
) |
Finds the first position in which val could be inserted without changing the ordering.
first | An iterator. | |
last | Another iterator. | |
val | The search term. |
Definition at line 2607 of file stl_algo.h.
References __glibcxx_function_requires, std::advance(), and std::distance().
Referenced by std::__merge_adaptive(), std::__merge_without_buffer(), std::binary_search(), std::equal_range(), __gnu_debug_def::set< Key, Compare, Allocator >::lower_bound(), __gnu_debug_def::multiset< Key, Compare, Allocator >::lower_bound(), __gnu_debug_def::multimap< Key, Type, Compare, Allocator >::lower_bound(), __gnu_debug_def::map< Key, Type, Compare, Allocator >::lower_bound(), std::map< Key, Type, Compare, Allocator >::operator[](), __gnu_cxx::BA_free_list_store::S_get_free_list(), __gnu_cxx::BA_free_list_store::S_validate_free_list(), and __gnu_cxx::stl_next_prime().
ForwardIterator std::upper_bound | ( | ForwardIterator | first, | |
ForwardIterator | last, | |||
const Type & | __val, | |||
Compare | comp | |||
) |
Finds the last position in which val could be inserted without changing the ordering.
first | An iterator. | |
last | Another iterator. | |
val | The search term. | |
comp | A functor to use for comparisons. |
Definition at line 2761 of file stl_algo.h.
References __glibcxx_function_requires, std::advance(), and std::distance().
ForwardIterator std::upper_bound | ( | ForwardIterator | first, | |
ForwardIterator | last, | |||
const Type & | __val | |||
) |
Finds the last position in which val could be inserted without changing the ordering.
first | An iterator. | |
last | Another iterator. | |
val | The search term. |
Definition at line 2709 of file stl_algo.h.
References __glibcxx_function_requires, std::advance(), and std::distance().
Referenced by std::__merge_adaptive(), std::__merge_without_buffer(), std::equal_range(), __gnu_debug_def::set< Key, Compare, Allocator >::upper_bound(), __gnu_debug_def::multiset< Key, Compare, Allocator >::upper_bound(), __gnu_debug_def::multimap< Key, Type, Compare, Allocator >::upper_bound(), and __gnu_debug_def::map< Key, Type, Compare, Allocator >::upper_bound().