Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h	(revision 137173)
+++ include/bits/stl_algo.h	(working copy)
@@ -730,8 +730,8 @@
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
   /**
-   *  @brief Checks that a predicate is true for all the elements
-   *         of a sequence.
+   *  @brief  Checks that a predicate is true for all the elements
+   *          of a sequence.
    *  @param  first   An input iterator.
    *  @param  last    An input iterator.
    *  @param  pred    A predicate.
@@ -746,8 +746,8 @@
     { return __last == std::find_if_not(__first, __last, __pred); }
 
   /**
-   *  @brief Checks that a predicate is false for all the elements
-   *         of a sequence.
+   *  @brief  Checks that a predicate is false for all the elements
+   *          of a sequence.
    *  @param  first   An input iterator.
    *  @param  last    An input iterator.
    *  @param  pred    A predicate.
@@ -762,8 +762,8 @@
     { return __last == _GLIBCXX_STD_P::find_if(__first, __last, __pred); }
 
   /**
-   *  @brief Checks that a predicate is false for at least an element
-   *         of a sequence.
+   *  @brief  Checks that a predicate is false for at least an element
+   *          of a sequence.
    *  @param  first   An input iterator.
    *  @param  last    An input iterator.
    *  @param  pred    A predicate.
@@ -778,8 +778,8 @@
     { return !std::none_of(__first, __last, __pred); }
 
   /**
-   *  @brief Find the first element in a sequence for which a
-   *         predicate is false.
+   *  @brief  Find the first element in a sequence for which a
+   *          predicate is false.
    *  @param  first  An input iterator.
    *  @param  last   An input iterator.
    *  @param  pred   A predicate.
@@ -799,6 +799,24 @@
       return std::__find_if_not(__first, __last, __pred,
 				std::__iterator_category(__first));
     }
+
+  /**
+   *  @brief  Checks whether the sequence is partitioned.
+   *  @param  first  An input iterator.
+   *  @param  last   An input iterator.
+   *  @param  pred   A predicate.
+   *  @return  True if the range @p [first,last) is partioned by @p pred,
+   *  i.e. if all elements that satisfy @p pred appear before those that
+   *  do not.
+  */
+  template<typename _InputIterator, typename _Predicate>
+    inline bool
+    is_partitioned(_InputIterator __first, _InputIterator __last,
+		   _Predicate __pred)
+    {
+      __first = std::find_if_not(__first, __last, __pred);
+      return std::none_of(__first, __last, __pred);
+    }
 #endif
 
 
Index: include/bits/algorithmfwd.h
===================================================================
--- include/bits/algorithmfwd.h	(revision 137173)
+++ include/bits/algorithmfwd.h	(working copy)
@@ -49,6 +49,7 @@
   inplace_merge
   is_heap (C++0x)
   is_heap_until (C++0x)
+  is_partitioned (C++0x)
   is_sorted (C++0x)
   is_sorted_until (C++0x)
   iter_swap
@@ -231,6 +232,10 @@
     _RAIter 
     is_heap_until(_RAIter, _RAIter, _Compare);
 
+  template<typename _IIter, typename _Predicate>
+    bool
+    is_partitioned(_IIter, _IIter, _Predicate);
+
   template<typename _FIter>
     bool 
     is_sorted(_FIter, _FIter);
Index: testsuite/25_algorithms/is_partitioned/check_type.cc
===================================================================
--- testsuite/25_algorithms/is_partitioned/check_type.cc	(revision 0)
+++ testsuite/25_algorithms/is_partitioned/check_type.cc	(revision 0)
@@ -0,0 +1,50 @@
+// 2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
+
+// Copyright (C) 2008 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+struct X { };
+
+using __gnu_test::input_iterator_wrapper;
+
+bool
+pred_function(const X&)
+{ return true; }
+
+struct pred_obj
+{
+  bool 
+  operator()(const X&)
+  { return true; }
+};
+
+bool
+test1(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end)
+{ return std::is_partitioned(begin, end, pred_function); }
+
+bool
+test2(input_iterator_wrapper<X>& begin,
+      input_iterator_wrapper<X>& end)
+{ return std::is_partitioned(begin, end, pred_obj()); }
Index: testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/2.cc
===================================================================
--- testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/2.cc	(revision 0)
+++ testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/2.cc	(revision 0)
@@ -0,0 +1,46 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// 2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
+
+// Copyright (C) 2008 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_api.h>
+
+namespace std
+{
+  using __gnu_test::NonDefaultConstructible;
+
+  typedef NonDefaultConstructible 		value_type;
+  typedef value_type* 		iterator_type;
+  typedef std::pointer_to_unary_function<value_type, bool> predicate_type;
+
+  template bool is_partitioned(iterator_type, iterator_type, predicate_type);
+} 
Index: testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/pod.cc
===================================================================
--- testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/pod.cc	(revision 0)
+++ testsuite/25_algorithms/is_partitioned/requirements/explicit_instantiation/pod.cc	(revision 0)
@@ -0,0 +1,45 @@
+// { dg-do compile }
+// { dg-options "-std=gnu++0x" }
+
+// 2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
+
+// Copyright (C) 2008 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <algorithm>
+#include <testsuite_character.h>
+
+namespace std
+{
+  using __gnu_test::pod_int;
+
+  typedef pod_int 		value_type;
+  typedef value_type* 		iterator_type;
+  typedef std::pointer_to_unary_function<value_type, bool> predicate_type;
+
+  template bool is_partitioned(iterator_type, iterator_type, predicate_type);
+} 
Index: testsuite/25_algorithms/is_partitioned/1.cc
===================================================================
--- testsuite/25_algorithms/is_partitioned/1.cc	(revision 0)
+++ testsuite/25_algorithms/is_partitioned/1.cc	(revision 0)
@@ -0,0 +1,81 @@
+// { dg-options "-std=gnu++0x" }
+
+// 2008-06-27  Paolo Carlini  <paolo.carlini@oracle.com>
+
+// Copyright (C) 2008 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+
+typedef test_container<int, input_iterator_wrapper> Container;
+int array[] = {0, 0, 1, 1, 1, 0, 0, 1};
+
+bool
+predicate(const int& i) 
+{ return i == 1; }
+
+void
+test1()
+{
+  bool test __attribute__((unused)) = true;
+
+  Container con(array, array);
+  VERIFY( std::is_partitioned(con.begin(), con.end(), predicate) );
+}
+
+void
+test2()
+{
+  bool test __attribute__((unused)) = true;
+  
+  Container con(array, array + 1);
+  VERIFY( std::is_partitioned(con.begin(), con.end(), predicate) );
+}
+
+void
+test3()
+{
+  bool test __attribute__((unused)) = true;
+
+  Container con(array, array + 8);
+  VERIFY( !std::is_partitioned(con.begin(), con.end(), predicate) );
+}
+
+void
+test4()
+{
+  bool test __attribute__((unused)) = true;
+
+  Container con(array + 2, array + 7);
+  VERIFY( std::is_partitioned(con.begin(), con.end(), predicate) );
+}
+
+int 
+main()
+{
+  test1();
+  test2();
+  test3();
+  test4();
+  return 0;
+}
Index: testsuite/25_algorithms/headers/algorithm/synopsis.cc
===================================================================
--- testsuite/25_algorithms/headers/algorithm/synopsis.cc	(revision 137173)
+++ testsuite/25_algorithms/headers/algorithm/synopsis.cc	(working copy)
@@ -51,6 +51,10 @@
   template<typename _IIter, typename _Predicate>
     _IIter
     find_if_not(_IIter, _IIter, _Predicate);
+
+  template<typename _IIter, typename _Predicate>
+    bool
+    is_partitioned(_IIter, _IIter, _Predicate);
 #endif
 
   template<typename _FIter1, typename _FIter2>