+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.
// <algorithm> declarations -*- C++ -*-
-// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
set_intersection
set_symmetric_difference
set_union
+ shuffle (C++0x)
sort
sort_heap
stable_partition
// set_symmetric_difference
// set_union
+#if defined(__GXX_EXPERIMENTAL_CXX0X__) && defined(_GLIBCXX_USE_C99_STDINT_TR1)
+ template<typename _RAIter, typename _UGenerator>
+ void
+ shuffle(_RAIter, _RAIter, _UGenerator&&);
+#endif
+
template<typename _RAIter>
void
sort_heap(_RAIter, _RAIter);
template<typename _RAIter, typename _Generator>
void
- random_shuffle(_RAIter, _RAIter, _Generator&);
+ random_shuffle(_RAIter, _RAIter,
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ _Generator&&);
+#else
+ _Generator&);
+#endif
template<typename _FIter, typename _Tp>
void
return __distance_fw(__first, __last, _Tag());
}
- template<typename _RAIter, typename _Tp>
- _RAIter
- __lower_bound(_RAIter __first, _RAIter __last, const _Tp& __val)
- {
- typedef typename std::iterator_traits<_RAIter>::difference_type _DType;
-
- _DType __len = __last - __first;
- while (__len > 0)
- {
- _DType __half = __len >> 1;
- _RAIter __middle = __first + __half;
- if (*__middle < __val)
- {
- __first = __middle;
- ++__first;
- __len = __len - __half - 1;
- }
- else
- __len = __half;
- }
- return __first;
- }
-
// Auxiliary types used for all instantiations of _Hashtable: nodes
// and iterators.
_Prime_rehash_policy::
_M_next_bkt(std::size_t __n) const
{
- const unsigned long* __p = __lower_bound(__prime_list, __prime_list
- + _S_n_primes, __n);
+ const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
+ + _S_n_primes, __n);
_M_next_resize =
static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
return *__p;
_M_bkt_for_elements(std::size_t __n) const
{
const float __min_bkts = __n / _M_max_load_factor;
- const unsigned long* __p = __lower_bound(__prime_list, __prime_list
- + _S_n_primes, __min_bkts);
+ const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
+ + _S_n_primes, __min_bkts);
_M_next_resize =
static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
return *__p;
{
__min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
const unsigned long* __p =
- __lower_bound(__prime_list, __prime_list + _S_n_primes,
- __min_bkts);
+ std::lower_bound(__prime_list, __prime_list + _S_n_primes,
+ __min_bkts);
_M_next_resize = static_cast<std::size_t>
(__builtin_ceil(*__p * _M_max_load_factor));
return std::make_pair(true, *__p);
{ 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)
* You should not attempt to use it directly.
*/
-#include <numeric>
-#include <algorithm>
+#include <numeric> // std::accumulate and std::partial_sum
namespace std
{
__calc(_Tp __x)
{ 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;
+ }
} // namespace __detail
const double __sum = std::accumulate(_M_prob.begin(),
_M_prob.end(), 0.0);
// Now normalize the probabilites.
- std::transform(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
- std::bind2nd(std::divides<double>(), __sum));
+ __detail::__transform(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
+ std::bind2nd(std::divides<double>(), __sum));
// Accumulate partial sums.
_M_cp.reserve(_M_prob.size());
std::partial_sum(_M_prob.begin(), _M_prob.end(),
const double __sum = std::accumulate(_M_den.begin(),
_M_den.end(), 0.0);
- std::transform(_M_den.begin(), _M_den.end(), _M_den.begin(),
- std::bind2nd(std::divides<double>(), __sum));
+ __detail::__transform(_M_den.begin(), _M_den.end(), _M_den.begin(),
+ std::bind2nd(std::divides<double>(), __sum));
_M_cp.reserve(_M_den.size());
std::partial_sum(_M_den.begin(), _M_den.end(),
}
// Now normalize the densities...
- std::transform(_M_den.begin(), _M_den.end(), _M_den.begin(),
- std::bind2nd(std::divides<double>(), __sum));
+ __detail::__transform(_M_den.begin(), _M_den.end(), _M_den.begin(),
+ std::bind2nd(std::divides<double>(), __sum));
// ... and partial sums...
- std::transform(_M_cp.begin(), _M_cp.end(), _M_cp.begin(),
- std::bind2nd(std::divides<double>(), __sum));
+ __detail::__transform(_M_cp.begin(), _M_cp.end(), _M_cp.begin(),
+ std::bind2nd(std::divides<double>(), __sum));
// ... and slopes.
- std::transform(_M_m.begin(), _M_m.end(), _M_m.begin(),
- std::bind2nd(std::divides<double>(), __sum));
+ __detail::__transform(_M_m.begin(), _M_m.end(), _M_m.begin(),
+ std::bind2nd(std::divides<double>(), __sum));
// Make sure the last cumulative probablility is one.
_M_cp[_M_cp.size() - 1] = 1.0;
}
#include <bits/stl_heap.h>
#include <bits/stl_tempbuf.h> // for _Temporary_buffer
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#include <random> // for std::uniform_int_distribution
+#endif
+
// See concept_check.h for the __glibcxx_*_requires macros.
_GLIBCXX_BEGIN_NAMESPACE(std)
}
}
- /// This is a helper function for the sort routines. 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); }
-
// sort
template<typename _RandomAccessIterator, typename _Size>
// nth_element
- /**
- * @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;
- }
+ // lower_bound moved to stl_algobase.h
/**
* @brief Finds the last position in which @a val could be inserted
std::minmax_element(__l.begin(), __l.end(), __comp);
return std::make_pair(*__p.first, *__p.second);
}
+
+#ifdef _GLIBCXX_USE_C99_STDINT_TR1
+ /**
+ * @brief Shuffle the elements of a sequence using a uniform random
+ * number generator.
+ * @ingroup mutating_algorithms
+ * @param first A forward iterator.
+ * @param last A forward iterator.
+ * @param g A UniformRandomNumberGenerator (26.5.1.3).
+ * @return Nothing.
+ *
+ * Reorders the elements in the range @p [first,last) using @p g to
+ * provide random numbers.
+ */
+ template<typename _RandomAccessIterator,
+ typename _UniformRandomNumberGenerator>
+ void
+ shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _UniformRandomNumberGenerator&& __g)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
+ _RandomAccessIterator>)
+ __glibcxx_requires_valid_range(__first, __last);
+
+ if (__first == __last)
+ return;
+
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _DistanceType;
+
+ typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
+ typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
+ typedef typename __distr_type::param_type __p_type;
+ __distr_type __d;
+
+ for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+ std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
+ }
+#endif
+
#endif // __GXX_EXPERIMENTAL_CXX0X__
_GLIBCXX_END_NAMESPACE
template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
void
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ _RandomNumberGenerator&& __rand)
+#else
_RandomNumberGenerator& __rand)
+#endif
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
__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)
// Sequential fallback.
template<typename _RAIter, typename _RandomNumberGenerator>
inline void
- random_shuffle(_RAIter __begin, _RAIter __end,
+ random_shuffle(_RAIter __begin, _RAIter __end,
_RandomNumberGenerator& __rand,
__gnu_parallel::sequential_tag)
{ _GLIBCXX_STD_P::random_shuffle(__begin, __end, __rand); }
// Parallel algorithm for random access iterators.
template<typename _RAIter, typename _RandomNumberGenerator>
void
- random_shuffle(_RAIter __begin, _RAIter __end,
+ random_shuffle(_RAIter __begin, _RAIter __end,
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ _RandomNumberGenerator&& __rand)
+#else
_RandomNumberGenerator& __rand)
+#endif
{
if (__begin == __end)
return;
// <algorithm> parallel extensions -*- C++ -*-
-// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
template<typename _RAIter, typename _RandomNumberGenerator>
void
- random_shuffle(_RAIter, _RAIter, _RandomNumberGenerator&);
+ random_shuffle(_RAIter, _RAIter,
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ _RandomNumberGenerator&&);
+#else
+ _RandomNumberGenerator&);
+#endif
template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
return __distance_fw(__first, __last, _Tag());
}
- template<typename _RAIter, typename _Tp>
- _RAIter
- __lower_bound(_RAIter __first, _RAIter __last, const _Tp& __val)
- {
- typedef typename std::iterator_traits<_RAIter>::difference_type _DType;
-
- _DType __len = __last - __first;
- while (__len > 0)
- {
- _DType __half = __len >> 1;
- _RAIter __middle = __first + __half;
- if (*__middle < __val)
- {
- __first = __middle;
- ++__first;
- __len = __len - __half - 1;
- }
- else
- __len = __half;
- }
- return __first;
- }
-
// Auxiliary types used for all instantiations of _Hashtable: nodes
// and iterators.
_Prime_rehash_policy::
_M_next_bkt(std::size_t __n) const
{
- const unsigned long* __p = __lower_bound(__prime_list, __prime_list
- + _S_n_primes, __n);
+ const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
+ + _S_n_primes, __n);
_M_next_resize =
static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
return *__p;
_M_bkt_for_elements(std::size_t __n) const
{
const float __min_bkts = __n / _M_max_load_factor;
- const unsigned long* __p = __lower_bound(__prime_list, __prime_list
- + _S_n_primes, __min_bkts);
+ const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
+ + _S_n_primes, __min_bkts);
_M_next_resize =
static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
return *__p;
{
__min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
const unsigned long* __p =
- __lower_bound(__prime_list, __prime_list + _S_n_primes,
- __min_bkts);
+ std::lower_bound(__prime_list, __prime_list + _S_n_primes,
+ __min_bkts);
_M_next_resize = static_cast<std::size_t>
(__builtin_ceil(*__p * _M_max_load_factor));
return std::make_pair(true, *__p);
--- /dev/null
+// { dg-options "-std=gnu++0x" }
+// { dg-require-cstdint "" }
+
+// 2010-03-19 Paolo Carlini <paolo.carlini@oracle.com>
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <algorithm>
+#include <random>
+#include <vector>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+
+ for (unsigned size = 0; size < 50; ++size)
+ {
+ std::vector<int> vref(size);
+ std::iota(vref.begin(), vref.end(), 0);
+ std::vector<int> v1(vref), v2(vref);
+
+ std::ranlux48_base g1(size), g2(size + 1);
+ std::shuffle(v1.begin(), v1.end(), g1);
+ std::shuffle(v2.begin(), v2.end(), g2);
+
+ if (size >= 10)
+ {
+ VERIFY( !std::equal(v1.begin(), v1.end(), vref.begin()) );
+ VERIFY( !std::equal(v2.begin(), v2.end(), vref.begin()) );
+ VERIFY( !std::equal(v1.begin(), v1.end(), v2.begin()) );
+ }
+
+ for (unsigned ind = 0; ind < size; ++ind)
+ {
+ auto it1 = std::find(v1.begin(), v1.end(), vref[ind]);
+ auto it2 = std::find(v2.begin(), v2.end(), vref[ind]);
+ VERIFY( it1 != v1.end() );
+ VERIFY( it2 != v2.end() );
+ v1.erase(it1);
+ v2.erase(it2);
+ }
+ VERIFY( v1.empty() );
+ VERIFY( v2.empty() );
+ }
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
--- /dev/null
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+// { dg-require-cstdint "" }
+
+// 2010-03-19 Paolo Carlini <paolo.carlini@oracle.com>
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+#include <algorithm>
+#include <random>
+#include <testsuite_api.h>
+
+namespace std
+{
+ using __gnu_test::NonDefaultConstructible;
+
+ typedef NonDefaultConstructible value_type;
+ typedef value_type* iterator_type;
+ typedef std::mt19937_64 ugenerator_type;
+
+ template void shuffle(iterator_type, iterator_type, ugenerator_type&&);
+}
--- /dev/null
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+// { dg-require-cstdint "" }
+
+// 2010-03-19 Paolo Carlini <paolo.carlini@oracle.com>
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <algorithm>
+#include <random>
+#include <testsuite_character.h>
+
+namespace std
+{
+ using __gnu_test::pod_int;
+
+ typedef pod_int value_type;
+ typedef value_type* iterator_type;
+ typedef std::mt19937_64 ugenerator_type;
+
+ template void shuffle(iterator_type, iterator_type, ugenerator_type&&);
+}
OSDN Git Service
