diff options
author | paolo <paolo@138bc75d-0d04-0410-961f-82ee72b054a4> | 2010-03-19 10:36:57 +0000 |
---|---|---|
committer | paolo <paolo@138bc75d-0d04-0410-961f-82ee72b054a4> | 2010-03-19 10:36:57 +0000 |
commit | 5f94d8fe06e58a4e4782516c8ed435a398e9c0a2 (patch) | |
tree | 884bdcb882db407e570871577799d5642ec6cc56 /libstdc++-v3/include/bits/stl_algobase.h | |
parent | 1384f0b0dd87e0468c18173e2ae7ac74640aace2 (diff) | |
download | ppe42-gcc-5f94d8fe06e58a4e4782516c8ed435a398e9c0a2.tar.gz ppe42-gcc-5f94d8fe06e58a4e4782516c8ed435a398e9c0a2.zip |
2010-03-19 Paolo Carlini <paolo.carlini@oracle.com>
* include/bits/stl_algo.h (shuffle): Add, per D3056.
(random_shuffle): Fix signature in C++0x mode.
(lower_bound, __lg): Move...
* include/bits/stl_algobase.h: ... here.
* include/bits/algorithmfwd.h: Adjust.
* include/parallel/algorithmfwd.h: Likewise.
* include/parallel/algo.h: Likewise.
* include/bits/hashtable_policy.h (__lower_bound): Remove,
adjust callers.
* include/tr1/hashtable_policy.h (__lower_bound): Likewise.
* include/bits/random.tcc (__detail::__transform): Add,
adjust std::transform callers; don't include <algorithm>.
* testsuite/25_algorithms/shuffle/1.cc: Add.
* testsuite/25_algorithms/shuffle/requirements/
explicit_instantiation/2.cc: Likewise.
* testsuite/25_algorithms/shuffle/requirements/
explicit_instantiation/pod.cc: Likewise.
* include/bits/random.h: Add comments.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@157564 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'libstdc++-v3/include/bits/stl_algobase.h')
-rw-r--r-- | libstdc++-v3/include/bits/stl_algobase.h | 125 |
1 files changed, 125 insertions, 0 deletions
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 3575279226b..1756966a5a1 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -938,6 +938,131 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __first2, __last2); } + /** + * @brief Finds the first position in which @a val could be inserted + * without changing the ordering. + * @param first An iterator. + * @param last Another iterator. + * @param val The search term. + * @return An iterator pointing to the first element <em>not less + * than</em> @a val, or end() if every element is less than + * @a val. + * @ingroup binary_search_algorithms + */ + template<typename _ForwardIterator, typename _Tp> + _ForwardIterator + lower_bound(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __val) + { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + typedef typename iterator_traits<_ForwardIterator>::difference_type + _DistanceType; + + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) + __glibcxx_requires_partitioned_lower(__first, __last, __val); + + _DistanceType __len = std::distance(__first, __last); + _DistanceType __half; + _ForwardIterator __middle; + + while (__len > 0) + { + __half = __len >> 1; + __middle = __first; + std::advance(__middle, __half); + if (*__middle < __val) + { + __first = __middle; + ++__first; + __len = __len - __half - 1; + } + else + __len = __half; + } + return __first; + } + + /** + * @brief Finds the first position in which @a val could be inserted + * without changing the ordering. + * @ingroup binary_search_algorithms + * @param first An iterator. + * @param last Another iterator. + * @param val The search term. + * @param comp A functor to use for comparisons. + * @return An iterator pointing to the first element <em>not less + * than</em> @a val, or end() if every element is less + * than @a val. + * @ingroup binary_search_algorithms + * + * The comparison function should have the same effects on ordering as + * the function used for the initial sort. + */ + template<typename _ForwardIterator, typename _Tp, typename _Compare> + _ForwardIterator + lower_bound(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __val, _Compare __comp) + { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + typedef typename iterator_traits<_ForwardIterator>::difference_type + _DistanceType; + + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType, _Tp>) + __glibcxx_requires_partitioned_lower_pred(__first, __last, + __val, __comp); + + _DistanceType __len = std::distance(__first, __last); + _DistanceType __half; + _ForwardIterator __middle; + + while (__len > 0) + { + __half = __len >> 1; + __middle = __first; + std::advance(__middle, __half); + if (__comp(*__middle, __val)) + { + __first = __middle; + ++__first; + __len = __len - __half - 1; + } + else + __len = __half; + } + return __first; + } + + /// This is a helper function for the sort routines and for random.tcc. + // Precondition: __n > 0. + template<typename _Size> + inline _Size + __lg(_Size __n) + { + _Size __k; + for (__k = 0; __n != 0; __n >>= 1) + ++__k; + return __k - 1; + } + + inline int + __lg(int __n) + { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } + + inline long + __lg(long __n) + { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } + + inline long long + __lg(long long __n) + { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } + _GLIBCXX_END_NAMESPACE _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) |