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

1 files changed, 22 insertions, 12 deletions

diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index fb2879ccf35..e47b1c83c7f 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -27,8 +27,7 @@
  *  You should not attempt to use it directly.
  */
 
-#include <numeric>
-#include <algorithm>
+#include <numeric> // std::accumulate and std::partial_sum
 
 namespace std
 {
@@ -87,6 +86,17 @@ 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
 
 
@@ -2177,8 +2187,8 @@ namespace std
       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(),
@@ -2299,8 +2309,8 @@ namespace std
       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(),
@@ -2499,14 +2509,14 @@ namespace std
 	}
 
       //  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;
      }