+2010-03-23 Paolo Carlini <paolo.carlini@oracle.com>
+
+ * include/bits/stl_algobase.h (lower_bound(_ForwardIterator,
+ _ForwardIterator, const _Tp&, _Compare)): Move...
+ * include/bits/stl_algo.h: ... here.
+
2010-03-22 Johannes Singler <singler@kit.edu>
* include/parallel/numeric (inner_product, partial_sum):
- Precede subsequent call with _GLIBCXX_STD_P:: to avoid ambiguity
+ Precede subsequent call with _GLIBCXX_STD_P:: to avoid ambiguity
between __gnu_parallel:: and std::
* include/parallel/algobase.h (equal): Likewise.
* include/parallel/algo.h (find_first_of, search_n, merge, nth_element,
// lower_bound moved to stl_algobase.h
/**
+ * @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;
+ }
+
+ /**
* @brief Finds the last position in which @a val could be inserted
* without changing the ordering.
* @ingroup binary_search_algorithms
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>