+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.
+
2010-03-17 Jonathan Wakely <jwakely.gcc@gmail.com>
* doc/xml/manual/debug_mode.xml: Correct debug headers.
#if defined(__GXX_EXPERIMENTAL_CXX0X__) && defined(_GLIBCXX_USE_C99_STDINT_TR1)
template<typename _RAIter, typename _UGenerator>
void
- shuffle(_RAIter, _RAIter, _UGenerator&);
+ shuffle(_RAIter, _RAIter, _UGenerator&&);
#endif
template<typename _RAIter>
{ return _M_param.b(); }
/**
- * @brief Returns the inclusive lower bound of the distribution range.
- */
- result_type
- min() const
- { return this->a(); }
-
- /**
- * @brief Returns the inclusive upper bound of the distribution range.
- */
- result_type
- max() const
- { return this->b(); }
-
- /**
* @brief Returns the parameter set of the distribution.
*/
param_type
{ _M_param = __param; }
/**
- * Gets a uniformly distributed random number in the range
- * @f$(min, max)@f$.
+ * @brief Returns the inclusive lower bound of the distribution range.
+ */
+ result_type
+ min() const
+ { return this->a(); }
+
+ /**
+ * @brief Returns the inclusive upper bound of the distribution range.
+ */
+ result_type
+ max() const
+ { return this->b(); }
+
+ /**
+ * @brief Generating functions.
*/
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
{ return this->operator()(__urng, this->param()); }
- /**
- * Gets a uniform random number in the range @f$[0, n)@f$.
- *
- * This function is aimed at use with std::random_shuffle.
- */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng,
{ return _M_param.b(); }
/**
+ * @brief Returns the parameter set of the distribution.
+ */
+ param_type
+ param() const
+ { return _M_param; }
+
+ /**
+ * @brief Sets the parameter set of the distribution.
+ * @param __param The new parameter set of the distribution.
+ */
+ void
+ param(const param_type& __param)
+ { _M_param = __param; }
+
+ /**
* @brief Returns the inclusive lower bound of the distribution range.
*/
result_type
{ return this->b(); }
/**
- * @brief Returns the parameter set of the distribution.
- */
- param_type
- param() const
- { return _M_param; }
-
- /**
- * @brief Sets the parameter set of the distribution.
- * @param __param The new parameter set of the distribution.
+ * @brief Generating functions.
*/
- void
- param(const param_type& __param)
- { _M_param = __param; }
-
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
{ return std::numeric_limits<result_type>::max(); }
/**
- * @brief Returns the next value in the Bernoullian sequence.
+ * @brief Generating functions.
*/
template<typename _UniformRandomNumberGenerator>
result_type
{ return _M_param.t(); }
/**
+ * @brief Generating functions.
+ */
+ template<typename _UniformRandomNumberGenerator>
+ result_type
+ operator()(_UniformRandomNumberGenerator& __urng)
+ { return this->operator()(__urng, this->param()); }
+
+ template<typename _UniformRandomNumberGenerator>
+ result_type
+ operator()(_UniformRandomNumberGenerator& __urng,
+ const param_type& __p);
+
+ /**
* @brief Return true if two binomial distributions have
* the same parameters and the sequences that would
* be generated are equal.
{ return __d1.param() == __d2.param(); }
#endif
- template<typename _UniformRandomNumberGenerator>
- result_type
- operator()(_UniformRandomNumberGenerator& __urng)
- { return this->operator()(__urng, this->param()); }
-
- template<typename _UniformRandomNumberGenerator>
- result_type
- operator()(_UniformRandomNumberGenerator& __urng,
- const param_type& __p);
-
/**
* @brief Inserts a %binomial_distribution random number distribution
* @p __x into the output stream @p __os.
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng);
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return std::numeric_limits<result_type>::max(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return this->_M_param._M_prob.size() - 1; }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return this->_M_param._M_int.back(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
max() const
{ return this->_M_param._M_int.back(); }
+ /**
+ * @brief Generating functions.
+ */
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
{ return __a * __x + __c; }
};
- template<typename _InputIterator, typename _OutputIterator,
- typename _UnaryOperation>
- _OutputIterator
- __transform(_InputIterator __first, _InputIterator __last,
- _OutputIterator __result, _UnaryOperation __unary_op)
- {
- for (; __first != __last; ++__first, ++__result)
- *__result = __unary_op(*__first);
- return __result;
- }
+ template<typename _InputIterator, typename _OutputIterator,
+ typename _UnaryOperation>
+ _OutputIterator
+ __transform(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result, _UnaryOperation __unary_op)
+ {
+ for (; __first != __last; ++__first, ++__result)
+ *__result = __unary_op(*__first);
+ return __result;
+ }
} // namespace __detail
// 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
typename _UniformRandomNumberGenerator>
void
shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _UniformRandomNumberGenerator& __g)
+ _UniformRandomNumberGenerator&& __g)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
// "the type returned by a _Generator"
__typeof__(__gen())>)
- for (__decltype(__n + 0) __niter = __n;
- __niter > 0; --__niter, ++__first)
+ for (; __n > 0; --__n, ++__first)
*__first = __gen();
return __first;
}
__gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
__fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
{
- for (__decltype(__n + 0) __niter = __n;
- __niter > 0; --__niter, ++__first)
+ for (; __n > 0; --__n, ++__first)
*__first = __value;
return __first;
}
__fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
{
const _Tp __tmp = __value;
- for (__decltype(__n + 0) __niter = __n;
- __niter > 0; --__niter, ++__first)
+ for (; __n > 0; --__n, ++__first)
*__first = __tmp;
return __first;
}
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>
typedef value_type* iterator_type;
typedef std::mt19937_64 ugenerator_type;
- template void shuffle(iterator_type, iterator_type, ugenerator_type&);
+ template void shuffle(iterator_type, iterator_type, ugenerator_type&&);
}
typedef value_type* iterator_type;
typedef std::mt19937_64 ugenerator_type;
- template void shuffle(iterator_type, iterator_type, ugenerator_type&);
+ template void shuffle(iterator_type, iterator_type, ugenerator_type&&);
}