From 820c6c55db9ebec8dc91adad8063d63b4ea62ae3 Mon Sep 17 00:00:00 2001 From: paolo Date: Fri, 19 Mar 2010 10:36:57 +0000 Subject: [PATCH] 2010-03-19 Paolo Carlini * 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 . * 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 --- libstdc++-v3/ChangeLog | 22 ++++ libstdc++-v3/include/bits/algorithmfwd.h | 2 +- libstdc++-v3/include/bits/random.h | 138 ++++++++++++++------- libstdc++-v3/include/bits/random.tcc | 20 +-- libstdc++-v3/include/bits/stl_algo.h | 59 +-------- libstdc++-v3/include/bits/stl_algobase.h | 60 ++++++++- .../requirements/explicit_instantiation/2.cc | 2 +- .../requirements/explicit_instantiation/pod.cc | 2 +- 8 files changed, 186 insertions(+), 119 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 53ae0f99221..1b06dae51d9 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,25 @@ +2010-03-19 Paolo Carlini + + * 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 . + * 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 * doc/xml/manual/debug_mode.xml: Correct debug headers. diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h index 645d8830fd8..803fa476947 100644 --- a/libstdc++-v3/include/bits/algorithmfwd.h +++ b/libstdc++-v3/include/bits/algorithmfwd.h @@ -521,7 +521,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) #if defined(__GXX_EXPERIMENTAL_CXX0X__) && defined(_GLIBCXX_USE_C99_STDINT_TR1) template void - shuffle(_RAIter, _RAIter, _UGenerator&); + shuffle(_RAIter, _RAIter, _UGenerator&&); #endif template diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h index 3f1a61535af..cc950f03ae2 100644 --- a/libstdc++-v3/include/bits/random.h +++ b/libstdc++-v3/include/bits/random.h @@ -1695,20 +1695,6 @@ namespace std { 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 @@ -1724,19 +1710,27 @@ namespace std { _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 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 result_type operator()(_UniformRandomNumberGenerator& __urng, @@ -1876,6 +1870,21 @@ namespace std { 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 @@ -1890,20 +1899,8 @@ namespace std { 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 result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2095,6 +2092,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2265,6 +2265,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2456,6 +2459,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2613,6 +2619,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2786,6 +2795,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2959,6 +2971,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -3129,6 +3144,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -3310,7 +3328,7 @@ namespace std { return std::numeric_limits::max(); } /** - * @brief Returns the next value in the Bernoullian sequence. + * @brief Generating functions. */ template result_type @@ -3510,6 +3528,19 @@ namespace std { return _M_param.t(); } /** + * @brief Generating functions. + */ + template + result_type + operator()(_UniformRandomNumberGenerator& __urng) + { return this->operator()(__urng, this->param()); } + + template + 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. @@ -3524,16 +3555,6 @@ namespace std { return __d1.param() == __d2.param(); } #endif - template - result_type - operator()(_UniformRandomNumberGenerator& __urng) - { return this->operator()(__urng, this->param()); } - - template - 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. @@ -3691,6 +3712,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -3860,6 +3884,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng); @@ -4040,6 +4067,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4219,6 +4249,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4396,6 +4429,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4568,6 +4604,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4756,6 +4795,9 @@ namespace std max() const { return this->_M_param._M_prob.size() - 1; } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4960,6 +5002,9 @@ namespace std max() const { return this->_M_param._M_int.back(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -5168,6 +5213,9 @@ namespace std max() const { return this->_M_param._M_int.back(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc index 5a66bd6b2e2..e47b1c83c7f 100644 --- a/libstdc++-v3/include/bits/random.tcc +++ b/libstdc++-v3/include/bits/random.tcc @@ -87,16 +87,16 @@ namespace std { return __a * __x + __c; } }; - template - _OutputIterator - __transform(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, _UnaryOperation __unary_op) - { - for (; __first != __last; ++__first, ++__result) - *__result = __unary_op(*__first); - return __result; - } + template + _OutputIterator + __transform(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _UnaryOperation __unary_op) + { + for (; __first != __last; ++__first, ++__result) + *__result = __unary_op(*__first); + return __result; + } } // namespace __detail diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index fe2edb9c8da..2f96d0670ef 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -2370,60 +2370,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // 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 not less - * than @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 - _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 @@ -4133,7 +4079,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename _UniformRandomNumberGenerator> void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, - _UniformRandomNumberGenerator& __g) + _UniformRandomNumberGenerator&& __g) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< @@ -4844,8 +4790,7 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) // "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; } diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 0489c413b95..1756966a5a1 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -748,8 +748,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __gnu_cxx::__enable_if::__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; } @@ -760,8 +759,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __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; } @@ -987,6 +985,60 @@ _GLIBCXX_BEGIN_NAMESPACE(std) 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 not less + * than @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 + _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 diff --git a/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/2.cc b/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/2.cc index 6941bd08779..4b921dca712 100644 --- a/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/2.cc +++ b/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/2.cc @@ -34,5 +34,5 @@ namespace std 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&&); } diff --git a/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/pod.cc b/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/pod.cc index a33ddd46bf9..0f0a1e19ea4 100644 --- a/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/pod.cc +++ b/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/pod.cc @@ -33,5 +33,5 @@ namespace std 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&&); } -- 2.11.0