This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[v3] Move HP/SGI stl_algo.h extensions to <ext/algorithm>
- From: Paolo Carlini <pcarlini at unitus dot it>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 28 Dec 2001 19:57:52 +0100
- Subject: [v3] Move HP/SGI stl_algo.h extensions to <ext/algorithm>
Hi,
self explaining, I guess. Tested i686-pc-linux-gnu, approved by Benjamin Kosnik.
(In the next days we'll also move all off the extensions already present in
include/ext inside namespace __gnu_cxx for a cleaner namespace std.)
Cheers,
Paolo.
///////////////////
2001-12-28 Paolo Carlini <pcarlini@unitus.it>
* include/bits/stl_algo.h (count returning void,
count_if returning void, __random_sample, random_sample,
random_sample_n, __is_heap, is_heap, is_sorted): Move to...
* include/ext/algorithm: ...here, new file.
* include/Makefile.am (ext_headers): Add new file.
* include/Makefile.in: Regenerate.
* testsuite/ext/headers.cc: Include <ext/algorithm>.
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/Makefile.am,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -r1.14 -r1.15
--- gcc/libstdc++-v3/include/Makefile.am 2001/10/23 21:40:30 1.14
+++ gcc/libstdc++-v3/include/Makefile.am 2001/12/28 18:46:53 1.15
@@ -172,6 +172,7 @@
ext_srcdir = ${glibcpp_srcdir}/include/ext
ext_builddir = ./ext
ext_headers = \
+ ${ext_srcdir}/algorithm \
${ext_srcdir}/rope \
${ext_srcdir}/ropeimpl.h \
${ext_srcdir}/stl_rope.h \
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/testsuite/ext/headers.cc,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- gcc/libstdc++-v3/testsuite/ext/headers.cc 2001/03/31 20:15:43 1.2
+++ gcc/libstdc++-v3/testsuite/ext/headers.cc 2001/12/28 18:46:53 1.3
@@ -23,6 +23,7 @@
// This should include a list of all headers in the extension
// subdirectory that are meant to be directly included.
+#include <ext/algorithm>
#include <ext/hash_map>
#include <ext/hash_set>
#include <ext/rope>
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_algo.h,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -r1.15 -r1.16
--- gcc/libstdc++-v3/include/bits/stl_algo.h 2001/12/06 20:29:31 1.15
+++ gcc/libstdc++-v3/include/bits/stl_algo.h 2001/12/28 18:46:54 1.16
@@ -292,42 +292,7 @@
return __last;
}
- // count and count_if. There are two version of each, one whose return type
- // type is void and one (present only if we have partial specialization)
- // whose return type is iterator_traits<_InputIter>::difference_type. The
- // C++ standard only has the latter version, but the former, which was
present
- // in the HP STL, is retained for backward compatibility.
-
- template<typename _InputIter, typename _Tp, typename _Size>
- void
- count(_InputIter __first, _InputIter __last,
- const _Tp& __value,
- _Size& __n)
- {
- // concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_EqualityComparableConcept<
- typename iterator_traits<_InputIter>::value_type >)
- __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
- for ( ; __first != __last; ++__first)
- if (*__first == __value)
- ++__n;
- }
-
- template<typename _InputIter, typename _Predicate, typename _Size>
- void
- count_if(_InputIter __first, _InputIter __last,
- _Predicate __pred,
- _Size& __n)
- {
- // concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
- typename iterator_traits<_InputIter>::value_type>)
- for ( ; __first != __last; ++__first)
- if (__pred(*__first))
- ++__n;
- }
+ // count and count_if.
template<typename _InputIter, typename _Tp>
typename iterator_traits<_InputIter>::difference_type
@@ -1177,146 +1142,6 @@
iter_swap(__i, __first + __rand((__i - __first) + 1));
}
- // random_sample and random_sample_n (extensions, not part of the standard).
-
- template<typename _ForwardIter, typename _OutputIter, typename _Distance>
- _OutputIter
- random_sample_n(_ForwardIter __first, _ForwardIter __last,
- _OutputIter __out, const _Distance __n)
- {
- // concept requirements
- __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
- __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
- typename iterator_traits<_ForwardIter>::value_type>)
-
- _Distance __remaining = distance(__first, __last);
- _Distance __m = min(__n, __remaining);
-
- while (__m > 0) {
- if (__random_number(__remaining) < __m) {
- *__out = *__first;
- ++__out;
- --__m;
- }
-
- --__remaining;
- ++__first;
- }
- return __out;
- }
-
- template<typename _ForwardIter, typename _OutputIter, typename _Distance,
- typename _RandomNumberGenerator>
- _OutputIter
- random_sample_n(_ForwardIter __first, _ForwardIter __last,
- _OutputIter __out, const _Distance __n,
- _RandomNumberGenerator& __rand)
- {
- // concept requirements
- __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
- __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
- typename iterator_traits<_ForwardIter>::value_type>)
- __glibcpp_function_requires(_UnaryFunctionConcept<
- _RandomNumberGenerator, _Distance, _Distance>)
-
- _Distance __remaining = distance(__first, __last);
- _Distance __m = min(__n, __remaining);
-
- while (__m > 0) {
- if (__rand(__remaining) < __m) {
- *__out = *__first;
- ++__out;
- --__m;
- }
-
- --__remaining;
- ++__first;
- }
- return __out;
- }
-
- template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
- _RandomAccessIter
- __random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out,
- const _Distance __n)
- {
- _Distance __m = 0;
- _Distance __t = __n;
- for ( ; __first != __last && __m < __n; ++__m, ++__first)
- __out[__m] = *__first;
-
- while (__first != __last) {
- ++__t;
- _Distance __M = __random_number(__t);
- if (__M < __n)
- __out[__M] = *__first;
- ++__first;
- }
-
- return __out + __m;
- }
-
- template<typename _InputIter, typename _RandomAccessIter,
- typename _RandomNumberGenerator, typename _Distance>
- _RandomAccessIter
- __random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out,
- _RandomNumberGenerator& __rand,
- const _Distance __n)
- {
- // concept requirements
- __glibcpp_function_requires(_UnaryFunctionConcept<
- _RandomNumberGenerator, _Distance, _Distance>)
-
- _Distance __m = 0;
- _Distance __t = __n;
- for ( ; __first != __last && __m < __n; ++__m, ++__first)
- __out[__m] = *__first;
-
- while (__first != __last) {
- ++__t;
- _Distance __M = __rand(__t);
- if (__M < __n)
- __out[__M] = *__first;
- ++__first;
- }
-
- return __out + __m;
- }
-
- template<typename _InputIter, typename _RandomAccessIter>
- inline _RandomAccessIter
- random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out_first, _RandomAccessIter __out_last)
- {
- // concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIter>)
-
- return __random_sample(__first, __last,
- __out_first, __out_last - __out_first);
- }
-
-
- template<typename _InputIter, typename _RandomAccessIter,
- typename _RandomNumberGenerator>
- inline _RandomAccessIter
- random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out_first, _RandomAccessIter __out_last,
- _RandomNumberGenerator& __rand)
- {
- // concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIter>)
-
- return __random_sample(__first, __last,
- __out_first, __rand,
- __out_last - __out_first);
- }
-
// partition, stable_partition, and their auxiliary functions
template<typename _ForwardIter, typename _Predicate>
@@ -3489,114 +3314,6 @@
__iterator_category(__first1),
__iterator_category(__first2),
__comp);
- }
-
- // is_heap, a predicate testing whether or not a range is
- // a heap. This function is an extension, not part of the C++
- // standard.
-
- template<typename _RandomAccessIter, typename _Distance>
- bool
- __is_heap(_RandomAccessIter __first, _Distance __n)
- {
- _Distance __parent = 0;
- for (_Distance __child = 1; __child < __n; ++__child) {
- if (__first[__parent] < __first[__child])
- return false;
- if ((__child & 1) == 0)
- ++__parent;
- }
- return true;
- }
-
- template<typename _RandomAccessIter, typename _Distance,
- typename _StrictWeakOrdering>
- bool
- __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
- _Distance __n)
- {
- _Distance __parent = 0;
- for (_Distance __child = 1; __child < __n; ++__child) {
- if (__comp(__first[__parent], __first[__child]))
- return false;
- if ((__child & 1) == 0)
- ++__parent;
- }
- return true;
- }
-
- template<typename _RandomAccessIter>
- inline bool
- is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
- {
- // concept requirements
-
__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
- __glibcpp_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_RandomAccessIter>::value_type>)
-
- return __is_heap(__first, __last - __first);
- }
-
-
- template<typename _RandomAccessIter, typename _StrictWeakOrdering>
- inline bool
- is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
- _StrictWeakOrdering __comp)
- {
- // concept requirements
-
__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
- __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
- typename iterator_traits<_RandomAccessIter>::value_type,
- typename iterator_traits<_RandomAccessIter>::value_type>)
-
- return __is_heap(__first, __comp, __last - __first);
- }
-
- // is_sorted, a predicated testing whether a range is sorted in
- // nondescending order. This is an extension, not part of the C++
- // standard.
-
- template<typename _ForwardIter>
- bool
- is_sorted(_ForwardIter __first, _ForwardIter __last)
- {
- // concept requirements
- __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
- __glibcpp_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_ForwardIter>::value_type>)
-
- if (__first == __last)
- return true;
-
- _ForwardIter __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next) {
- if (*__next < *__first)
- return false;
- }
-
- return true;
- }
-
- template<typename _ForwardIter, typename _StrictWeakOrdering>
- bool
- is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering
__comp)
- {
- // concept requirements
- __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
- __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
- typename iterator_traits<_ForwardIter>::value_type,
- typename iterator_traits<_ForwardIter>::value_type>)
-
- if (__first == __last)
- return true;
-
- _ForwardIter __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next) {
- if (__comp(*__next, *__first))
- return false;
- }
-
- return true;
}
} // namespace std
diff -urN libstdc++-v3-orig/include/ext/algorithm
libstdc++-v3/include/ext/algorithm
--- libstdc++-v3-orig/include/ext/algorithm Thu Jan 1 01:00:00 1970
+++ libstdc++-v3/include/ext/algorithm Thu Dec 27 15:29:58 2001
@@ -0,0 +1,345 @@
+// Algorithm extensions -*- C++ -*-
+
+// Copyright (C) 2001 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// 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.
+
+/*
+ *
+ * Copyright (c) 1994
+ * Hewlett-Packard Company
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Hewlett-Packard Company makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ *
+ *
+ * Copyright (c) 1996
+ * Silicon Graphics Computer Systems, Inc.
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Silicon Graphics makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ */
+
+#ifndef _EXT_ALGORITHM
+#define _EXT_ALGORITHM
+
+#include <bits/std_algorithm.h>
+
+namespace __gnu_cxx
+{
+ // count and count_if: this version, whose return type is void, was present
+ // in the HP STL, and is retained as an extension for backward compatibility.
+
+ template<typename _InputIter, typename _Tp, typename _Size>
+ void
+ count(_InputIter __first, _InputIter __last,
+ const _Tp& __value,
+ _Size& __n)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+ __glibcpp_function_requires(_EqualityComparableConcept<
+ typename std::iterator_traits<_InputIter>::value_type >)
+ __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
+ for ( ; __first != __last; ++__first)
+ if (*__first == __value)
+ ++__n;
+ }
+
+ template<typename _InputIter, typename _Predicate, typename _Size>
+ void
+ count_if(_InputIter __first, _InputIter __last,
+ _Predicate __pred,
+ _Size& __n)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+ __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
+ typename std::iterator_traits<_InputIter>::value_type>)
+ for ( ; __first != __last; ++__first)
+ if (__pred(*__first))
+ ++__n;
+ }
+
+ // random_sample and random_sample_n (extensions, not part of the standard).
+
+ template<typename _ForwardIter, typename _OutputIter, typename _Distance>
+ _OutputIter
+ random_sample_n(_ForwardIter __first, _ForwardIter __last,
+ _OutputIter __out, const _Distance __n)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+ __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
+ typename std::iterator_traits<_ForwardIter>::value_type>)
+
+ _Distance __remaining = std::distance(__first, __last);
+ _Distance __m = std::min(__n, __remaining);
+
+ while (__m > 0) {
+ if (std::__random_number(__remaining) < __m) {
+ *__out = *__first;
+ ++__out;
+ --__m;
+ }
+
+ --__remaining;
+ ++__first;
+ }
+ return __out;
+ }
+
+ template<typename _ForwardIter, typename _OutputIter, typename _Distance,
+ typename _RandomNumberGenerator>
+ _OutputIter
+ random_sample_n(_ForwardIter __first, _ForwardIter __last,
+ _OutputIter __out, const _Distance __n,
+ _RandomNumberGenerator& __rand)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+ __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
+ typename std::iterator_traits<_ForwardIter>::value_type>)
+ __glibcpp_function_requires(_UnaryFunctionConcept<
+ _RandomNumberGenerator, _Distance, _Distance>)
+
+ _Distance __remaining = std::distance(__first, __last);
+ _Distance __m = std::min(__n, __remaining);
+
+ while (__m > 0) {
+ if (__rand(__remaining) < __m) {
+ *__out = *__first;
+ ++__out;
+ --__m;
+ }
+
+ --__remaining;
+ ++__first;
+ }
+ return __out;
+ }
+
+ template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
+ _RandomAccessIter
+ __random_sample(_InputIter __first, _InputIter __last,
+ _RandomAccessIter __out,
+ const _Distance __n)
+ {
+ _Distance __m = 0;
+ _Distance __t = __n;
+ for ( ; __first != __last && __m < __n; ++__m, ++__first)
+ __out[__m] = *__first;
+
+ while (__first != __last) {
+ ++__t;
+ _Distance __M = std::__random_number(__t);
+ if (__M < __n)
+ __out[__M] = *__first;
+ ++__first;
+ }
+
+ return __out + __m;
+ }
+
+ template<typename _InputIter, typename _RandomAccessIter,
+ typename _RandomNumberGenerator, typename _Distance>
+ _RandomAccessIter
+ __random_sample(_InputIter __first, _InputIter __last,
+ _RandomAccessIter __out,
+ _RandomNumberGenerator& __rand,
+ const _Distance __n)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_UnaryFunctionConcept<
+ _RandomNumberGenerator, _Distance, _Distance>)
+
+ _Distance __m = 0;
+ _Distance __t = __n;
+ for ( ; __first != __last && __m < __n; ++__m, ++__first)
+ __out[__m] = *__first;
+
+ while (__first != __last) {
+ ++__t;
+ _Distance __M = __rand(__t);
+ if (__M < __n)
+ __out[__M] = *__first;
+ ++__first;
+ }
+
+ return __out + __m;
+ }
+
+ template<typename _InputIter, typename _RandomAccessIter>
+ inline _RandomAccessIter
+ random_sample(_InputIter __first, _InputIter __last,
+ _RandomAccessIter __out_first, _RandomAccessIter __out_last)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+ __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+ _RandomAccessIter>)
+
+ return __random_sample(__first, __last,
+ __out_first, __out_last - __out_first);
+ }
+
+ template<typename _InputIter, typename _RandomAccessIter,
+ typename _RandomNumberGenerator>
+ inline _RandomAccessIter
+ random_sample(_InputIter __first, _InputIter __last,
+ _RandomAccessIter __out_first, _RandomAccessIter __out_last,
+ _RandomNumberGenerator& __rand)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+ __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+ _RandomAccessIter>)
+
+ return __random_sample(__first, __last,
+ __out_first, __rand,
+ __out_last - __out_first);
+ }
+
+ // is_heap, a predicate testing whether or not a range is
+ // a heap. This function is an extension, not part of the C++
+ // standard.
+
+ template<typename _RandomAccessIter, typename _Distance>
+ bool
+ __is_heap(_RandomAccessIter __first, _Distance __n)
+ {
+ _Distance __parent = 0;
+ for (_Distance __child = 1; __child < __n; ++__child) {
+ if (__first[__parent] < __first[__child])
+ return false;
+ if ((__child & 1) == 0)
+ ++__parent;
+ }
+ return true;
+ }
+
+ template<typename _RandomAccessIter, typename _Distance,
+ typename _StrictWeakOrdering>
+ bool
+ __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
+ _Distance __n)
+ {
+ _Distance __parent = 0;
+ for (_Distance __child = 1; __child < __n; ++__child) {
+ if (__comp(__first[__parent], __first[__child]))
+ return false;
+ if ((__child & 1) == 0)
+ ++__parent;
+ }
+ return true;
+ }
+
+ template<typename _RandomAccessIter>
+ inline bool
+ is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
+ {
+ // concept requirements
+
__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
+ __glibcpp_function_requires(_LessThanComparableConcept<
+ typename std::iterator_traits<_RandomAccessIter>::value_type>)
+
+ return __is_heap(__first, __last - __first);
+ }
+
+ template<typename _RandomAccessIter, typename _StrictWeakOrdering>
+ inline bool
+ is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
+ _StrictWeakOrdering __comp)
+ {
+ // concept requirements
+
__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
+ __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
+ typename std::iterator_traits<_RandomAccessIter>::value_type,
+ typename std::iterator_traits<_RandomAccessIter>::value_type>)
+
+ return __is_heap(__first, __comp, __last - __first);
+ }
+
+ // is_sorted, a predicated testing whether a range is sorted in
+ // nondescending order. This is an extension, not part of the C++
+ // standard.
+
+ template<typename _ForwardIter>
+ bool
+ is_sorted(_ForwardIter __first, _ForwardIter __last)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+ __glibcpp_function_requires(_LessThanComparableConcept<
+ typename std::iterator_traits<_ForwardIter>::value_type>)
+
+ if (__first == __last)
+ return true;
+
+ _ForwardIter __next = __first;
+ for (++__next; __next != __last; __first = __next, ++__next) {
+ if (*__next < *__first)
+ return false;
+ }
+
+ return true;
+ }
+
+ template<typename _ForwardIter, typename _StrictWeakOrdering>
+ bool
+ is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering
__comp)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+ __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
+ typename std::iterator_traits<_ForwardIter>::value_type,
+ typename std::iterator_traits<_ForwardIter>::value_type>)
+
+ if (__first == __last)
+ return true;
+
+ _ForwardIter __next = __first;
+ for (++__next; __next != __last; __first = __next, ++__next) {
+ if (__comp(*__next, *__first))
+ return false;
+ }
+
+ return true;
+ }
+
+} // namespace __gnu_cxx
+
+#endif /* _EXT_ALGORITHM */