stl_algobase.h (copy_n + helpers, [...]): Move to...

2002-01-02  Paolo Carlini  <pcarlini@unitus.it>

	* include/bits/stl_algobase.h (copy_n + helpers,
	lexicographical_compare_3way + helpers):  Move to...
	* include/ext/algorithm:  ...here.
        * include/bits/stl_uninitialized.h (uninitialized_copy_n +
        helpers):  Move to...
        * include/ext/memory:  ...here, new file.
        * include/Makefile.am (ext_headers):  Add new file.
        * include/Makefile.in:  Regenerate.
        * testsuite/ext/headers.cc:  Include <ext/memory>.
	* include/backward/algobase.h:  Include <ext/memory> and
	<ext/algorithm>, tweak.
        * include/ext/ropeimpl.h:  Include <ext/memory>, tweak.
	* include/ext/stl_rope.h:  Include <ext/memory>, tweak.

From-SVN: r48467

11 files changed, 407 insertions, 307 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 9d61d67..72c97b8 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,19 @@
+2002-01-02  Paolo Carlini  <pcarlini@unitus.it>
+
+	* include/bits/stl_algobase.h (copy_n + helpers,
+	lexicographical_compare_3way + helpers):  Move to...
+	* include/ext/algorithm:  ...here.
+        * include/bits/stl_uninitialized.h (uninitialized_copy_n +
+        helpers):  Move to...
+        * include/ext/memory:  ...here, new file.
+        * include/Makefile.am (ext_headers):  Add new file.
+        * include/Makefile.in:  Regenerate.
+        * testsuite/ext/headers.cc:  Include <ext/memory>.
+	* include/backward/algobase.h:  Include <ext/memory> and
+	<ext/algorithm>, tweak.
+        * include/ext/ropeimpl.h:  Include <ext/memory>, tweak.
+	* include/ext/stl_rope.h:  Include <ext/memory>, tweak.
+
 2002-01-01  Roger Sayle <roger@eyesopen.com>
 
 	* libmath/stubs.c (sinf,cosf): Implement stubs to enable the
diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index 1f20d45..4211930 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -176,6 +176,7 @@ ext_headers = \
 	${ext_srcdir}/hash_map \
 	${ext_srcdir}/hash_set \
 	${ext_srcdir}/iterator \
+	${ext_srcdir}/memory \
 	${ext_srcdir}/rope \
 	${ext_srcdir}/ropeimpl.h \
 	${ext_srcdir}/slist \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index b25cd32..abde46d 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -1,6 +1,7 @@
-# Makefile.in generated automatically by automake 1.4 from Makefile.am
+# Makefile.in generated automatically by automake 1.5 from Makefile.am.
 
-# Copyright (C) 1994, 1995-8, 1999 Free Software Foundation, Inc.
+# Copyright 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001
+# Free Software Foundation, Inc.
 # This Makefile.in is free software; the Free Software Foundation
 # gives unlimited permission to copy and/or distribute it,
 # with or without modifications, as long as this notice is preserved.
@@ -10,6 +11,7 @@
 # even the implied warranty of MERCHANTABILITY or FITNESS FOR A
 # PARTICULAR PURPOSE.
 
+@SET_MAKE@
 
 SHELL = @SHELL@
 
@@ -31,13 +33,9 @@ infodir = @infodir@
 mandir = @mandir@
 includedir = @includedir@
 oldincludedir = /usr/include
-
-DESTDIR =
-
 pkgdatadir = $(datadir)/@PACKAGE@
 pkglibdir = $(libdir)/@PACKAGE@
 pkgincludedir = $(includedir)/@PACKAGE@
-
 top_builddir = ..
 
 ACLOCAL = @ACLOCAL@
@@ -46,11 +44,11 @@ AUTOMAKE = @AUTOMAKE@
 AUTOHEADER = @AUTOHEADER@
 
 INSTALL = @INSTALL@
-INSTALL_PROGRAM = @INSTALL_PROGRAM@ $(AM_INSTALL_PROGRAM_FLAGS)
+INSTALL_PROGRAM = @INSTALL_PROGRAM@
 INSTALL_DATA = @INSTALL_DATA@
 INSTALL_SCRIPT = @INSTALL_SCRIPT@
+INSTALL_HEADER = $(INSTALL_DATA)
 transform = @program_transform_name@
-
 NORMAL_INSTALL = :
 PRE_INSTALL = :
 POST_INSTALL = :
@@ -84,7 +82,6 @@ C_INCLUDE_DIR = @C_INCLUDE_DIR@
 DATADIRNAME = @DATADIRNAME@
 DEBUG_FLAGS = @DEBUG_FLAGS@
 DLLTOOL = @DLLTOOL@
-EXEEXT = @EXEEXT@
 EXTRA_CXX_FLAGS = @EXTRA_CXX_FLAGS@
 GCJ = @GCJ@
 GCJFLAGS = @GCJFLAGS@
@@ -108,7 +105,6 @@ LIBSUPCXX_PICFLAGS = @LIBSUPCXX_PICFLAGS@
 LIBTOOL = @LIBTOOL@
 LN_S = @LN_S@
 MAINT = @MAINT@
-MAKEINFO = @MAKEINFO@
 MKINSTALLDIRS = @MKINSTALLDIRS@
 MSGFMT = @MSGFMT@
 OBJDUMP = @OBJDUMP@
@@ -146,16 +142,23 @@ libtool_VERSION = @libtool_VERSION@
 release_VERSION = @release_VERSION@
 toplevel_srcdir = @toplevel_srcdir@
 
+# Cross compiler and multilib support.
+CXX = @glibcpp_CXX@
+glibcpp_builddir = @glibcpp_builddir@
+glibcpp_srcdir = @glibcpp_srcdir@
+
+# Target includes for threads
+glibcpp_thread_h = @glibcpp_thread_h@
+
+# One big happy istallation:  just copy everything from the build to the
+# install tree (except for the build stamps).
+gxx_include_dir = @gxx_include_dir@
+
 AUTOMAKE_OPTIONS = 1.3 gnits
 MAINT_CHARSET = latin1
 
 mkinstalldirs = $(SHELL) $(toplevel_srcdir)/mkinstalldirs
 
-# Cross compiler and multilib support.
-CXX = @glibcpp_CXX@
-glibcpp_srcdir = @glibcpp_srcdir@
-glibcpp_builddir = @glibcpp_builddir@
-
 bits_srcdir = ${glibcpp_srcdir}/include/bits
 bits_builddir = ./bits
 bits_headers = \
@@ -303,6 +306,7 @@ ext_headers = \
 	${ext_srcdir}/hash_map \
 	${ext_srcdir}/hash_set \
 	${ext_srcdir}/iterator \
+	${ext_srcdir}/memory \
 	${ext_srcdir}/rope \
 	${ext_srcdir}/ropeimpl.h \
 	${ext_srcdir}/slist \
@@ -410,116 +414,108 @@ thread_headers = \
 allstamps = stamp-std stamp-bits stamp-c_base stamp-backward stamp-ext \
 	stamp-target stamp-thread 
 
-
-# Target includes for threads
-glibcpp_thread_h = @glibcpp_thread_h@
 uppercase = [ABCDEFGHIJKLMNOPQRSTUVWXYZ_]
+subdir = include
+CONFIG_HEADER = $(top_builddir)/config.h
+CONFIG_CLEAN_FILES =
+depcomp =
+DIST_SOURCES =
+all: all-am
 
-# One big happy istallation:  just copy everything from the build to the
-# install tree (except for the build stamps).
-gxx_include_dir = @gxx_include_dir@
-CONFIG_HEADER = ../config.h
-CONFIG_CLEAN_FILES = 
-DIST_COMMON =  Makefile.am Makefile.in
-
-
-DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST)
-
-TAR = gtar
-GZIP_ENV = --best
-all: all-redirect
 .SUFFIXES:
-$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ Makefile.am $(top_srcdir)/configure.in $(ACLOCAL_M4) 
-	cd $(top_srcdir) && $(AUTOMAKE) --gnits include/Makefile
 
-Makefile: $(srcdir)/Makefile.in  $(top_builddir)/config.status $(BUILT_SOURCES)
-	cd $(top_builddir) \
-	  && CONFIG_FILES=$(subdir)/$@ CONFIG_HEADERS= $(SHELL) ./config.status
+mostlyclean-libtool:
+	-rm -f *.lo
 
+clean-libtool:
+	-rm -rf .libs _libs
+
+distclean-libtool:
+	-rm -f libtool
+$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ Makefile.am  $(top_srcdir)/configure.in $(ACLOCAL_M4)
+	cd $(top_srcdir) && \
+	  $(AUTOMAKE) --cygnus  include/Makefile
+Makefile: @MAINTAINER_MODE_TRUE@ $(srcdir)/Makefile.in  $(top_builddir)/config.status
+	cd $(top_builddir) && \
+	  CONFIG_HEADERS= CONFIG_LINKS= \
+	  CONFIG_FILES=$(subdir)/$@ $(SHELL) ./config.status
+uninstall-info-am:
 tags: TAGS
 TAGS:
 
+check-am:
+check: check-am
+all-am: Makefile all-local
 
-distdir = $(top_builddir)/$(PACKAGE)-$(VERSION)/$(subdir)
-
-subdir = include
+installdirs:
 
-distdir: $(DISTFILES)
-	here=`cd $(top_builddir) && pwd`; \
-	top_distdir=`cd $(top_distdir) && pwd`; \
-	distdir=`cd $(distdir) && pwd`; \
-	cd $(top_srcdir) \
-	  && $(AUTOMAKE) --include-deps --build-dir=$$here --srcdir-name=$(top_srcdir) --output-dir=$$top_distdir --gnits include/Makefile
-	@for file in $(DISTFILES); do \
-	  d=$(srcdir); \
-	  if test -d $$d/$$file; then \
-	    cp -pr $$d/$$file $(distdir)/$$file; \
-	  else \
-	    test -f $(distdir)/$$file \
-	    || ln $$d/$$file $(distdir)/$$file 2> /dev/null \
-	    || cp -p $$d/$$file $(distdir)/$$file || :; \
-	  fi; \
-	done
-info-am:
-info: info-am
-dvi-am:
-dvi: dvi-am
-check-am: all-am
-check: check-am
-installcheck-am:
-installcheck: installcheck-am
-install-exec-am:
+install: install-am
 install-exec: install-exec-am
-
-install-data-am: install-data-local
 install-data: install-data-am
+uninstall: uninstall-am
 
 install-am: all-am
 	@$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am
-install: install-am
-uninstall-am:
-uninstall: uninstall-am
-all-am: Makefile all-local
-all-redirect: all-am
-install-strip:
-	$(MAKE) $(AM_MAKEFLAGS) AM_INSTALL_PROGRAM_FLAGS=-s install
-installdirs:
-
 
+installcheck: installcheck-am
+install-strip:
+	$(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
+	  `test -z '$(STRIP)' || \
+	    echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install
 mostlyclean-generic:
 
 clean-generic:
 
 distclean-generic:
-	-rm -f Makefile $(CONFIG_CLEAN_FILES)
-	-rm -f config.cache config.log stamp-h stamp-h[0-9]*
+	-rm -f Makefile $(CONFIG_CLEAN_FILES) stamp-h stamp-h[0-9]*
 
 maintainer-clean-generic:
-mostlyclean-am:  mostlyclean-generic
+	@echo "This command is intended for maintainers to use"
+	@echo "it deletes files that may require special tools to rebuild."
+clean: clean-am
 
-mostlyclean: mostlyclean-am
+clean-am: clean-generic clean-libtool mostlyclean-am
 
-clean-am:  clean-generic mostlyclean-am
+distclean: distclean-am
 
-clean: clean-am
+distclean-am: clean-am distclean-generic distclean-libtool
 
-distclean-am:  distclean-generic clean-am
-	-rm -f libtool
+dvi: dvi-am
 
-distclean: distclean-am
+dvi-am:
 
-maintainer-clean-am:  maintainer-clean-generic distclean-am
-	@echo "This command is intended for maintainers to use;"
-	@echo "it deletes files that may require special tools to rebuild."
+info: info-am
+
+info-am:
+
+install-data-am: install-data-local
+
+install-exec-am:
+
+install-info:
+
+install-man:
+
+installcheck-am:
 
 maintainer-clean: maintainer-clean-am
 
-.PHONY: tags distdir info-am info dvi-am dvi check check-am \
-installcheck-am installcheck install-exec-am install-exec \
-install-data-local install-data-am install-data install-am install \
-uninstall-am uninstall all-local all-redirect all-am all installdirs \
-mostlyclean-generic distclean-generic clean-generic \
-maintainer-clean-generic clean mostlyclean distclean maintainer-clean
+maintainer-clean-am: distclean-am maintainer-clean-generic
+
+mostlyclean: mostlyclean-am
+
+mostlyclean-am: mostlyclean-generic mostlyclean-libtool
+
+uninstall-am:
+
+.PHONY: all all-am all-local check check-am clean clean-generic \
+	clean-libtool distclean distclean-generic distclean-libtool dvi \
+	dvi-am info info-am install install-am install-data \
+	install-data-am install-data-local install-exec install-exec-am \
+	install-info install-info-am install-man install-strip \
+	installcheck installcheck-am installdirs maintainer-clean \
+	maintainer-clean-generic mostlyclean mostlyclean-generic \
+	mostlyclean-libtool uninstall uninstall-am uninstall-info-am
 
 
 # Here are the rules for building the headers
@@ -626,7 +622,6 @@ install-data-local:
 
 # By adding these files here, automake will remove them for 'make clean'
 #CLEANFILES = ${allstamps}
-
 # Tell versions [3.59,3.63) of GNU make to not export all variables.
 # Otherwise a system limit (for SysV at least) may be exceeded.
 .NOEXPORT:
diff --git a/libstdc++-v3/include/backward/algobase.h b/libstdc++-v3/include/backward/algobase.h
index 3818c76..1606559 100644
--- a/libstdc++-v3/include/backward/algobase.h
+++ b/libstdc++-v3/include/backward/algobase.h
@@ -60,6 +60,8 @@
 #include "iterator.h"
 #include <bits/stl_algobase.h>
 #include <bits/stl_uninitialized.h>
+#include <ext/algorithm>
+#include <ext/memory>
 
 // Names from stl_algobase.h
 using std::iter_swap; 
@@ -68,20 +70,24 @@ using std::min;
 using std::max; 
 using std::copy; 
 using std::copy_backward; 
-using std::copy_n; 
 using std::fill; 
 using std::fill_n; 
 using std::mismatch; 
 using std::equal; 
 using std::lexicographical_compare; 
-using std::lexicographical_compare_3way; 
 
 // Names from stl_uninitialized.h
 using std::uninitialized_copy;
-using std::uninitialized_copy_n;
 using std::uninitialized_fill;
 using std::uninitialized_fill_n;
 
+// Names from ext/algorithm
+using __gnu_cxx::copy_n; 
+using __gnu_cxx::lexicographical_compare_3way; 
+
+// Names from ext/memory
+using __gnu_cxx::uninitialized_copy_n;
+
 #endif /* _CPP_BACKWARD_ALGOBASE_H */
 
 // Local Variables:
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index b75a808..2453976 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -492,58 +492,6 @@ namespace std
 						   __Normal());
     }
 
-  //--------------------------------------------------
-  // copy_n (not part of the C++ standard)
-
-  template<typename _InputIter, typename _Size, typename _OutputIter>
-    pair<_InputIter, _OutputIter>
-    __copy_n(_InputIter __first, _Size __count,
-	     _OutputIter __result,
-	     input_iterator_tag)
-    {
-      for ( ; __count > 0; --__count) {
-	*__result = *__first;
-	++__first;
-	++__result;
-      }
-      return pair<_InputIter, _OutputIter>(__first, __result);
-    }
-
-  template<typename _RAIter, typename _Size, typename _OutputIter>
-    inline pair<_RAIter, _OutputIter>
-    __copy_n(_RAIter __first, _Size __count,
-	     _OutputIter __result,
-	     random_access_iterator_tag)
-    {
-      _RAIter __last = __first + __count;
-      return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
-    }
-
-  /**
-   *  @brief Copies the range [first,first+count) into [result,result+count).
-   *  @param  first  An input iterator.
-   *  @param  count  The number of elements to copy.
-   *  @param  result An output iterator.
-   *  @return   A std::pair composed of first+count and result+count.
-   *
-   *  This is an SGI extension.
-   *  This inline function will boil down to a call to @c memmove whenever
-   *  possible.  Failing that, if random access iterators are passed, then the
-   *  loop count will be known (and therefore a candidate for compiler
-   *  optimizations such as unrolling).
-   *  @ingroup SGIextensions
-  */
-  template<typename _InputIter, typename _Size, typename _OutputIter>
-    inline pair<_InputIter, _OutputIter>
-    copy_n(_InputIter __first, _Size __count, _OutputIter __result)
-    {
-      // concept requirements
-      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
-      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
-	    typename iterator_traits<_InputIter>::value_type>)
-
-      return __copy_n(__first, __count, __result, __iterator_category(__first));
-    }
 
   //--------------------------------------------------
   // fill and fill_n
@@ -767,8 +715,7 @@ namespace std
     }
 
   //--------------------------------------------------
-  // lexicographical_compare and lexicographical_compare_3way.
-  // (the latter is not part of the C++ standard.)
+  // lexicographical_compare
 
   /**
    *  @brief Performs "dictionary" comparison on ranges.
@@ -866,88 +813,6 @@ namespace std
 #endif /* CHAR_MAX == SCHAR_MAX */
   }
 
-  template<typename _InputIter1, typename _InputIter2>
-    int
-    __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
-				   _InputIter2 __first2, _InputIter2 __last2)
-    {
-      while (__first1 != __last1 && __first2 != __last2) {
-	if (*__first1 < *__first2)
-	  return -1;
-	if (*__first2 < *__first1)
-	  return 1;
-	++__first1;
-	++__first2;
-      }
-      if (__first2 == __last2) {
-	return !(__first1 == __last1);
-      }
-      else {
-	return -1;
-      }
-    }
-
-  inline int
-  __lexicographical_compare_3way(const unsigned char* __first1,
-				 const unsigned char* __last1,
-				 const unsigned char* __first2,
-				 const unsigned char* __last2)
-  {
-    const ptrdiff_t __len1 = __last1 - __first1;
-    const ptrdiff_t __len2 = __last2 - __first2;
-    const int __result = memcmp(__first1, __first2, min(__len1, __len2));
-    return __result != 0 ? __result 
-			 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
-  }
-
-  inline int 
-  __lexicographical_compare_3way(const char* __first1, const char* __last1,
-				 const char* __first2, const char* __last2)
-  {
-#if CHAR_MAX == SCHAR_MAX
-    return __lexicographical_compare_3way(
-				  (const signed char*) __first1,
-				  (const signed char*) __last1,
-				  (const signed char*) __first2,
-				  (const signed char*) __last2);
-#else
-    return __lexicographical_compare_3way((const unsigned char*) __first1,
-					  (const unsigned char*) __last1,
-					  (const unsigned char*) __first2,
-					  (const unsigned char*) __last2);
-#endif
-  }
-
-  /**
-   *  @brief @c memcmp on steroids.
-   *  @param  first1  An input iterator.
-   *  @param  last1   An input iterator.
-   *  @param  first2  An input iterator.
-   *  @param  last2   An input iterator.
-   *  @return   An int, as with @c memcmp.
-   *
-   *  The return value will be less than zero if the first range is
-   *  "lexigraphically less than" the second, greater than zero if the second
-   *  range is "lexigraphically less than" the first, and zero otherwise.
-   *  This is an SGI extension.
-   *  @ingroup SGIextensions
-  */
-  template<typename _InputIter1, typename _InputIter2>
-    int
-    lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
-				 _InputIter2 __first2, _InputIter2 __last2)
-    {
-      // concept requirements
-      __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
-      __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
-      __glibcpp_function_requires(_LessThanComparableConcept<
-	    typename iterator_traits<_InputIter1>::value_type>)
-      __glibcpp_function_requires(_LessThanComparableConcept<
-	    typename iterator_traits<_InputIter2>::value_type>)
-
-      return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
-    }
-
 } // namespace std
 
 #endif /* __GLIBCPP_INTERNAL_ALGOBASE_H */
diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h
index c51ba58..f679d52 100644
--- a/libstdc++-v3/include/bits/stl_uninitialized.h
+++ b/libstdc++-v3/include/bits/stl_uninitialized.h
@@ -127,64 +127,6 @@ namespace std
     return __result + (__last - __first);
   }
 
-  // uninitialized_copy_n (not part of the C++ standard)
-
-  template<typename _InputIter, typename _Size, typename _ForwardIter>
-    pair<_InputIter, _ForwardIter>
-    __uninitialized_copy_n(_InputIter __first, _Size __count,
-			   _ForwardIter __result,
-			   input_iterator_tag)
-    {
-      _ForwardIter __cur = __result;
-      try {
-	for ( ; __count > 0 ; --__count, ++__first, ++__cur) 
-	  _Construct(&*__cur, *__first);
-	return pair<_InputIter, _ForwardIter>(__first, __cur);
-      }
-      catch(...)
-	{
-	  _Destroy(__result, __cur);
-	  __throw_exception_again; 
-	}
-    }
-
-  template<typename _RandomAccessIter, typename _Size, typename _ForwardIter>
-    inline pair<_RandomAccessIter, _ForwardIter>
-    __uninitialized_copy_n(_RandomAccessIter __first, _Size __count,
-			   _ForwardIter __result,
-			   random_access_iterator_tag)
-    {
-      _RandomAccessIter __last = __first + __count;
-      return pair<_RandomAccessIter, _ForwardIter>(
-		     __last,
-		     uninitialized_copy(__first, __last, __result));
-    }
-
-  template<typename _InputIter, typename _Size, typename _ForwardIter>
-    inline pair<_InputIter, _ForwardIter>
-    __uninitialized_copy_n(_InputIter __first, _Size __count,
-			 _ForwardIter __result) {
-      return __uninitialized_copy_n(__first, __count, __result,
-				    __iterator_category(__first));
-    }
-
-  /**
-   *  @brief Copies the range [first,last) into result.
-   *  @param  first  An input iterator.
-   *  @param  last   An input iterator.
-   *  @param  result An output iterator.
-   *  @return   result + (first - last)
-   *
-   *  Like copy(), but does not require an initialized output range.
-  */
-  template<typename _InputIter, typename _Size, typename _ForwardIter>
-    inline pair<_InputIter, _ForwardIter>
-    uninitialized_copy_n(_InputIter __first, _Size __count,
-			 _ForwardIter __result) {
-      return __uninitialized_copy_n(__first, __count, __result,
-				    __iterator_category(__first));
-    }
-
   // Valid if copy construction is equivalent to assignment, and if the
   // destructor is trivial.
   template<typename _ForwardIter, typename _Tp>
diff --git a/libstdc++-v3/include/ext/algorithm b/libstdc++-v3/include/ext/algorithm
index 3d9ccd6..588c722 100644
--- a/libstdc++-v3/include/ext/algorithm
+++ b/libstdc++-v3/include/ext/algorithm
@@ -61,6 +61,150 @@
 
 namespace __gnu_cxx
 {
+  using std::ptrdiff_t;
+  using std::min;
+  using std::pair;
+  using std::input_iterator_tag;
+  using std::random_access_iterator_tag;
+  using std::iterator_traits;
+
+  //--------------------------------------------------
+  // copy_n (not part of the C++ standard)
+
+  template<typename _InputIter, typename _Size, typename _OutputIter>
+    pair<_InputIter, _OutputIter>
+    __copy_n(_InputIter __first, _Size __count,
+	     _OutputIter __result,
+	     input_iterator_tag)
+    {
+      for ( ; __count > 0; --__count) {
+	*__result = *__first;
+	++__first;
+	++__result;
+      }
+      return pair<_InputIter, _OutputIter>(__first, __result);
+    }
+
+  template<typename _RAIter, typename _Size, typename _OutputIter>
+    inline pair<_RAIter, _OutputIter>
+    __copy_n(_RAIter __first, _Size __count,
+	     _OutputIter __result,
+	     random_access_iterator_tag)
+    {
+      _RAIter __last = __first + __count;
+      return pair<_RAIter, _OutputIter>(__last,
+					std::copy(__first, __last, __result));
+    }
+
+  /**
+   *  @brief Copies the range [first,first+count) into [result,result+count).
+   *  @param  first  An input iterator.
+   *  @param  count  The number of elements to copy.
+   *  @param  result An output iterator.
+   *  @return   A std::pair composed of first+count and result+count.
+   *
+   *  This is an SGI extension.
+   *  This inline function will boil down to a call to @c memmove whenever
+   *  possible.  Failing that, if random access iterators are passed, then the
+   *  loop count will be known (and therefore a candidate for compiler
+   *  optimizations such as unrolling).
+   *  @ingroup SGIextensions
+  */
+  template<typename _InputIter, typename _Size, typename _OutputIter>
+    inline pair<_InputIter, _OutputIter>
+    copy_n(_InputIter __first, _Size __count, _OutputIter __result)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+      __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
+	    typename iterator_traits<_InputIter>::value_type>)
+
+      return __copy_n(__first, __count, __result,
+		      std::__iterator_category(__first));
+    }
+
+  template<typename _InputIter1, typename _InputIter2>
+    int
+    __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
+				   _InputIter2 __first2, _InputIter2 __last2)
+    {
+      while (__first1 != __last1 && __first2 != __last2) {
+	if (*__first1 < *__first2)
+	  return -1;
+	if (*__first2 < *__first1)
+	  return 1;
+	++__first1;
+	++__first2;
+      }
+      if (__first2 == __last2) {
+	return !(__first1 == __last1);
+      }
+      else {
+	return -1;
+      }
+    }
+
+  inline int
+  __lexicographical_compare_3way(const unsigned char* __first1,
+				 const unsigned char* __last1,
+				 const unsigned char* __first2,
+				 const unsigned char* __last2)
+  {
+    const ptrdiff_t __len1 = __last1 - __first1;
+    const ptrdiff_t __len2 = __last2 - __first2;
+    const int __result = std::memcmp(__first1, __first2, min(__len1, __len2));
+    return __result != 0 ? __result 
+			 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
+  }
+
+  inline int 
+  __lexicographical_compare_3way(const char* __first1, const char* __last1,
+				 const char* __first2, const char* __last2)
+  {
+#if CHAR_MAX == SCHAR_MAX
+    return __lexicographical_compare_3way(
+				  (const signed char*) __first1,
+				  (const signed char*) __last1,
+				  (const signed char*) __first2,
+				  (const signed char*) __last2);
+#else
+    return __lexicographical_compare_3way((const unsigned char*) __first1,
+					  (const unsigned char*) __last1,
+					  (const unsigned char*) __first2,
+					  (const unsigned char*) __last2);
+#endif
+  }
+
+  /**
+   *  @brief @c memcmp on steroids.
+   *  @param  first1  An input iterator.
+   *  @param  last1   An input iterator.
+   *  @param  first2  An input iterator.
+   *  @param  last2   An input iterator.
+   *  @return   An int, as with @c memcmp.
+   *
+   *  The return value will be less than zero if the first range is
+   *  "lexigraphically less than" the second, greater than zero if the second
+   *  range is "lexigraphically less than" the first, and zero otherwise.
+   *  This is an SGI extension.
+   *  @ingroup SGIextensions
+  */
+  template<typename _InputIter1, typename _InputIter2>
+    int
+    lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
+				 _InputIter2 __first2, _InputIter2 __last2)
+    {
+      // concept requirements
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
+      __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
+      __glibcpp_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_InputIter1>::value_type>)
+      __glibcpp_function_requires(_LessThanComparableConcept<
+	    typename iterator_traits<_InputIter2>::value_type>)
+
+      return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
+    }
+
   // 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.
 
@@ -73,7 +217,7 @@ namespace __gnu_cxx
       // concept requirements
       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
       __glibcpp_function_requires(_EqualityComparableConcept<
-	    typename std::iterator_traits<_InputIter>::value_type >)
+	    typename iterator_traits<_InputIter>::value_type >)
       __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
       for ( ; __first != __last; ++__first)
 	if (*__first == __value)
@@ -89,7 +233,7 @@ namespace __gnu_cxx
       // concept requirements
       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
-	    typename std::iterator_traits<_InputIter>::value_type>)
+	    typename iterator_traits<_InputIter>::value_type>)
       for ( ; __first != __last; ++__first)
 	if (__pred(*__first))
 	  ++__n;
@@ -105,10 +249,10 @@ namespace __gnu_cxx
       // concept requirements
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
-		typename std::iterator_traits<_ForwardIter>::value_type>)
+		typename iterator_traits<_ForwardIter>::value_type>)
 
       _Distance __remaining = std::distance(__first, __last);
-      _Distance __m = std::min(__n, __remaining);
+      _Distance __m = min(__n, __remaining);
 
       while (__m > 0) {
 	if (std::__random_number(__remaining) < __m) {
@@ -133,12 +277,12 @@ namespace __gnu_cxx
       // concept requirements
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
-		typename std::iterator_traits<_ForwardIter>::value_type>)
+		typename iterator_traits<_ForwardIter>::value_type>)
       __glibcpp_function_requires(_UnaryFunctionConcept<
 		_RandomNumberGenerator, _Distance, _Distance>)
 
       _Distance __remaining = std::distance(__first, __last);
-      _Distance __m = std::min(__n, __remaining);
+      _Distance __m = min(__n, __remaining);
 
       while (__m > 0) {
 	if (__rand(__remaining) < __m) {
@@ -275,7 +419,7 @@ namespace __gnu_cxx
       // concept requirements
       __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
       __glibcpp_function_requires(_LessThanComparableConcept<
-	    typename std::iterator_traits<_RandomAccessIter>::value_type>)
+	    typename iterator_traits<_RandomAccessIter>::value_type>)
 
       return __is_heap(__first, __last - __first);
     }
@@ -288,8 +432,8 @@ namespace __gnu_cxx
       // 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>)
+	    typename iterator_traits<_RandomAccessIter>::value_type, 
+	    typename iterator_traits<_RandomAccessIter>::value_type>)
 
       return __is_heap(__first, __comp, __last - __first);
     }
@@ -305,7 +449,7 @@ namespace __gnu_cxx
       // concept requirements
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
       __glibcpp_function_requires(_LessThanComparableConcept<
-	    typename std::iterator_traits<_ForwardIter>::value_type>)
+	    typename iterator_traits<_ForwardIter>::value_type>)
 
       if (__first == __last)
 	return true;
@@ -326,8 +470,8 @@ namespace __gnu_cxx
       // 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>)
+	    typename iterator_traits<_ForwardIter>::value_type, 
+	    typename iterator_traits<_ForwardIter>::value_type>)
 
       if (__first == __last)
 	return true;
diff --git a/libstdc++-v3/include/ext/memory b/libstdc++-v3/include/ext/memory
new file mode 100644
index 0000000..e8b8574
--- /dev/null
+++ b/libstdc++-v3/include/ext/memory
@@ -0,0 +1,128 @@
+// Memory extensions -*- C++ -*-
+
+// Copyright (C) 2002 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_MEMORY
+#define _EXT_MEMORY
+
+#pragma GCC system_header
+#include <bits/std_memory.h>
+
+namespace __gnu_cxx
+{
+  using std::pair;
+  using std::__iterator_category;
+  
+  // uninitialized_copy_n (not part of the C++ standard)
+
+  template<typename _InputIter, typename _Size, typename _ForwardIter>
+    pair<_InputIter, _ForwardIter>
+    __uninitialized_copy_n(_InputIter __first, _Size __count,
+			   _ForwardIter __result,
+			   std::input_iterator_tag)
+    {
+      _ForwardIter __cur = __result;
+      try {
+	for ( ; __count > 0 ; --__count, ++__first, ++__cur) 
+	  std::_Construct(&*__cur, *__first);
+	return pair<_InputIter, _ForwardIter>(__first, __cur);
+      }
+      catch(...)
+	{
+	  std::_Destroy(__result, __cur);
+	  __throw_exception_again; 
+	}
+    }
+
+  template<typename _RandomAccessIter, typename _Size, typename _ForwardIter>
+    inline pair<_RandomAccessIter, _ForwardIter>
+    __uninitialized_copy_n(_RandomAccessIter __first, _Size __count,
+			   _ForwardIter __result,
+			   std::random_access_iterator_tag)
+    {
+      _RandomAccessIter __last = __first + __count;
+      return pair<_RandomAccessIter, _ForwardIter>(
+		     __last,
+		     std::uninitialized_copy(__first, __last, __result));
+    }
+
+  template<typename _InputIter, typename _Size, typename _ForwardIter>
+    inline pair<_InputIter, _ForwardIter>
+    __uninitialized_copy_n(_InputIter __first, _Size __count,
+			 _ForwardIter __result) {
+      return __uninitialized_copy_n(__first, __count, __result,
+				    __iterator_category(__first));
+    }
+
+  /**
+   *  @brief Copies the range [first,last) into result.
+   *  @param  first  An input iterator.
+   *  @param  last   An input iterator.
+   *  @param  result An output iterator.
+   *  @return   result + (first - last)
+   *
+   *  Like copy(), but does not require an initialized output range.
+  */
+  template<typename _InputIter, typename _Size, typename _ForwardIter>
+    inline pair<_InputIter, _ForwardIter>
+    uninitialized_copy_n(_InputIter __first, _Size __count,
+			 _ForwardIter __result) {
+      return __uninitialized_copy_n(__first, __count, __result,
+				    __iterator_category(__first));
+    }
+
+} // namespace __gnu_cxx
+
+#endif /* _EXT_MEMORY */
+
diff --git a/libstdc++-v3/include/ext/ropeimpl.h b/libstdc++-v3/include/ext/ropeimpl.h
index 54ddc26..6132494 100644
--- a/libstdc++-v3/include/ext/ropeimpl.h
+++ b/libstdc++-v3/include/ext/ropeimpl.h
@@ -49,6 +49,9 @@
 #include <bits/std_iostream.h>
 #include <bits/functexcept.h>
 
+#include <ext/algorithm> // For copy_n and lexicographical_compare_3way
+#include <ext/memory> // For uninitialized_copy_n
+
 namespace __gnu_cxx
 {
 using std::size_t;
@@ -58,8 +61,6 @@ using std::__throw_length_error;
 using std::__alloc;
 using std::_Destroy;
 using std::uninitialized_fill_n;
-using std::lexicographical_compare_3way;
-using std::uninitialized_copy_n;
 
 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
 // if necessary.  Assumes _M_path_end[leaf_index] and leaf_pos are correct.
@@ -983,7 +984,7 @@ rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, _CharT* __buffer)
 	case _RopeRep::_S_leaf:
 	    {
 		_RopeLeaf* __l = (_RopeLeaf*)__r;
-		return std::copy_n(__l->_M_data, __l->_M_size, __buffer).second;
+		return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
 	    }
 	case _RopeRep::_S_function:
 	case _RopeRep::_S_substringfn:
diff --git a/libstdc++-v3/include/ext/stl_rope.h b/libstdc++-v3/include/ext/stl_rope.h
index 9f23a60..04fa15c 100644
--- a/libstdc++-v3/include/ext/stl_rope.h
+++ b/libstdc++-v3/include/ext/stl_rope.h
@@ -61,6 +61,8 @@
 #   define __GC_CONST   // constant except for deallocation
 # endif
 
+#include <ext/memory> // For uninitialized_copy_n
+
 namespace __gnu_cxx
 {
 using std::size_t;
@@ -71,7 +73,6 @@ using std::reverse_iterator;
 using std::_Alloc_traits;
 using std::_Destroy;
 using std::_Refcount_Base;
-using std::uninitialized_copy_n;
 
 // The _S_eos function is used for those functions that
 // convert to/from C-like strings to detect the end of the string.
diff --git a/libstdc++-v3/testsuite/ext/headers.cc b/libstdc++-v3/testsuite/ext/headers.cc
index b751b82..bc7f8b2 100644
--- a/libstdc++-v3/testsuite/ext/headers.cc
+++ b/libstdc++-v3/testsuite/ext/headers.cc
@@ -27,6 +27,7 @@
 #include <ext/hash_map>
 #include <ext/hash_set>
 #include <ext/iterator>
+#include <ext/memory>
 #include <ext/rope>
 #include <ext/slist>