This commit was manufactured by cvs2svn to create tag

'Version_1_22_0'.

[SVN r10239]

development/boost/iterator_concepts.hpp

@@ -3,6 +3,8 @@
 
 #include <boost/concept_check.hpp>
 #include <boost/iterator_traits.hpp>
+#include <boost/type_traits/conversion_traits.hpp>
+#include <boost/static_assert.hpp>
 
 namespace boost_concepts {
   // Used a different namespace here (instead of "boost") so that the
@@ -11,6 +13,7 @@ namespace boost_concepts {
 
 
   //===========================================================================
+  // Iterator Access Concepts
 
   template <typename Iterator>
   class ReadableIteratorConcept {
@@ -23,11 +26,12 @@ namespace boost_concepts {
     void constraints() {
       boost::function_requires< boost::SGIAssignableConcept<Iterator> >();
       boost::function_requires< boost::EqualityComparableConcept<Iterator> >();
-      boost::function_requires< boost::DefaultConstructibleConcept<Iterator> >();
-      
       boost::function_requires< 
-        boost::ConvertibleConcept<return_category, boost::readable_iterator_tag> >();
-
+        boost::DefaultConstructibleConcept<Iterator> >();
+      
+      BOOST_STATIC_ASSERT((boost::is_convertible<return_category*,
+                           boost::readable_iterator_tag*>::value));
+                          
       reference r = *i; // or perhaps read(x)
       value_type v(r);
       boost::ignore_unused_variable_warning(v);
@@ -44,10 +48,11 @@ namespace boost_concepts {
     void constraints() {
       boost::function_requires< boost::SGIAssignableConcept<Iterator> >();
       boost::function_requires< boost::EqualityComparableConcept<Iterator> >();
-      boost::function_requires< boost::DefaultConstructibleConcept<Iterator> >();
-      
       boost::function_requires< 
-        boost::ConvertibleConcept<return_category, boost::writable_iterator_tag> >();
+        boost::DefaultConstructibleConcept<Iterator> >();
+      
+      BOOST_STATIC_ASSERT((boost::is_convertible<return_category*,
+                           boost::writable_iterator_tag*>::value));
 
       *i = v; // an alternative could be something like write(x, v)
     }
@@ -65,12 +70,12 @@ namespace boost_concepts {
 
     void constraints() {
       boost::function_requires< ReadableIteratorConcept<Iterator> >();
-      
-      boost::function_requires< 
-        boost::ConvertibleConcept<return_category, 
-          boost::constant_lvalue_iterator_tag> >();
 
-      typedef typename boost::require_same<reference, const value_type&>::type req;
+      BOOST_STATIC_ASSERT((boost::is_convertible<return_category*, 
+                           boost::constant_lvalue_iterator_tag*>::value));
+
+      BOOST_STATIC_ASSERT((boost::is_same<reference, 
+                           const value_type&>::value));
 
       reference v = *i;
       boost::ignore_unused_variable_warning(v);
@@ -88,13 +93,13 @@ namespace boost_concepts {
 
     void constraints() {
       boost::function_requires< ReadableIteratorConcept<Iterator> >();
-      boost::function_requires< WritableIteratorConcept<Iterator, value_type> >();
-      
       boost::function_requires< 
-        boost::ConvertibleConcept<return_category, 
-          boost::constant_lvalue_iterator_tag> >();
+        WritableIteratorConcept<Iterator, value_type> >();
+      
+      BOOST_STATIC_ASSERT((boost::is_convertible<return_category*, 
+                           boost::mutable_lvalue_iterator_tag*>::value));
 
-      typedef typename boost::require_same<reference, value_type&>::type req;
+      BOOST_STATIC_ASSERT((boost::is_same<reference, value_type&>::value));
 
       reference v = *i;
       boost::ignore_unused_variable_warning(v);
@@ -103,24 +108,25 @@ namespace boost_concepts {
   };
   
   //===========================================================================
+  // Iterator Traversal Concepts
 
   template <typename Iterator>
   class SinglePassIteratorConcept {
   public:
-    typedef typename boost::iterator_traits<Iterator>::motion_category 
-      motion_category;
+    typedef typename boost::iterator_traits<Iterator>::traversal_category 
+      traversal_category;
     typedef typename boost::iterator_traits<Iterator>::difference_type
       difference_type;
 
     void constraints() {
       boost::function_requires< boost::SGIAssignableConcept<Iterator> >();
       boost::function_requires< boost::EqualityComparableConcept<Iterator> >();
-      boost::function_requires< boost::DefaultConstructibleConcept<Iterator> >();
-
       boost::function_requires< 
-        boost::ConvertibleConcept<motion_category, 
-          boost::single_pass_iterator_tag> >();
-      
+        boost::DefaultConstructibleConcept<Iterator> >();
+
+      BOOST_STATIC_ASSERT((boost::is_convertible<traversal_category*, 
+                           boost::single_pass_iterator_tag*>::value));
+
       // difference_type must be a signed integral type
 
       ++i;
@@ -133,30 +139,28 @@ namespace boost_concepts {
   template <typename Iterator>
   class ForwardIteratorConcept {
   public:
-    typedef typename boost::iterator_traits<Iterator>::motion_category 
-      motion_category;
+    typedef typename boost::iterator_traits<Iterator>::traversal_category 
+      traversal_category;
 
     void constraints() {
       boost::function_requires< SinglePassIteratorConcept<Iterator> >();
 
-      boost::function_requires< 
-        boost::ConvertibleConcept<motion_category, 
-          boost::forward_iterator_tag> >();
+      BOOST_STATIC_ASSERT((boost::is_convertible<traversal_category*, 
+                           boost::forward_iterator_tag*>::value));
     }
   };
   
   template <typename Iterator>
   class BidirectionalIteratorConcept {
   public:
-    typedef typename boost::iterator_traits<Iterator>::motion_category 
-      motion_category;
+    typedef typename boost::iterator_traits<Iterator>::traversal_category 
+      traversal_category;
 
     void constraints() {
       boost::function_requires< ForwardIteratorConcept<Iterator> >();
       
-      boost::function_requires< 
-        boost::ConvertibleConcept<motion_category, 
-          boost::bidirectional_iterator_tag> >();
+      BOOST_STATIC_ASSERT((boost::is_convertible<traversal_category*, 
+                           boost::bidirectional_iterator_tag*>::value));
 
       --i;
       (void)i--;
@@ -167,18 +171,17 @@ namespace boost_concepts {
   template <typename Iterator>
   class RandomAccessIteratorConcept {
   public:
-    typedef typename boost::iterator_traits<Iterator>::motion_category 
-      motion_category;
+    typedef typename boost::iterator_traits<Iterator>::traversal_category 
+      traversal_category;
     typedef typename boost::iterator_traits<Iterator>::difference_type
       difference_type;
 
     void constraints() {
       boost::function_requires< BidirectionalIteratorConcept<Iterator> >();
 
-      boost::function_requires< 
-        boost::ConvertibleConcept<motion_category, 
-          boost::random_access_iterator_tag> >();
-
+      BOOST_STATIC_ASSERT((boost::is_convertible<traversal_category*, 
+                           boost::random_access_iterator_tag*>::value));
+      
       i += n;
       i = i + n;
       i = n + i;
@@ -190,92 +193,6 @@ namespace boost_concepts {
     Iterator i, j;
   };
 
-  //===========================================================================
-
-  template <typename Iterator>
-  class ReadableRandomAccessIteratorConcept {
-  public:
-    typedef typename boost::iterator_traits<Iterator>::value_type value_type;
-    typedef typename boost::iterator_traits<Iterator>::reference reference;
-    typedef typename boost::iterator_traits<Iterator>::difference_type
-      difference_type;
-
-    void constraints() {
-      boost::function_requires< RandomAccessIteratorConcept<Iterator> >();
-      boost::function_requires< ReadableIteratorConcept<Iterator> >();
-      
-      reference r = i[n];
-      value_type v(r);
-      boost::ignore_unused_variable_warning(v);
-    }
-    difference_type n;
-    Iterator i;
-  };
-
-  template <typename Iterator>
-  class WritableRandomAccessIteratorConcept {
-  public:
-    typedef typename boost::iterator_traits<Iterator>::value_type value_type;
-    typedef typename boost::iterator_traits<Iterator>::difference_type
-      difference_type;
-
-    void constraints() {
-      boost::function_requires< RandomAccessIteratorConcept<Iterator> >();
-      boost::function_requires< WritableIteratorConcept<Iterator, value_type> >();
-
-      i[n] = v;
-      boost::ignore_unused_variable_warning(v);
-    }
-    difference_type n;
-    value_type v;
-    Iterator i;
-  };
-
-  template <typename Iterator>
-  class ConstantLvalueRandomAccessIteratorConcept {
-  public:
-    typedef typename boost::iterator_traits<Iterator>::value_type value_type;
-    typedef typename boost::iterator_traits<Iterator>::reference reference;
-    typedef typename boost::iterator_traits<Iterator>::difference_type
-      difference_type;
-
-    void constraints() {
-      boost::function_requires< RandomAccessIteratorConcept<Iterator> >();
-      boost::function_requires< ReadableIteratorConcept<Iterator> >();
-
-      typedef typename boost::require_same<reference, const value_type&>::type req;
-
-      reference v = i[n];
-      boost::ignore_unused_variable_warning(v);
-    }
-    difference_type n;
-    value_type v;
-    Iterator i;
-  };
-  
-  template <typename Iterator>
-  class MutableLvalueRandomAccessIteratorConcept {
-  public:
-    typedef typename boost::iterator_traits<Iterator>::value_type value_type;
-    typedef typename boost::iterator_traits<Iterator>::reference reference;
-    typedef typename boost::iterator_traits<Iterator>::difference_type
-      difference_type;
-
-    void constraints() {
-      boost::function_requires< RandomAccessIteratorConcept<Iterator> >();
-      boost::function_requires< WritableIteratorConcept<Iterator, value_type> >();
-      boost::function_requires< ReadableIteratorConcept<Iterator> >();
-
-      typedef typename boost::require_same<reference, value_type&>::type req;
-
-      reference v = i[n];
-      boost::ignore_unused_variable_warning(v);
-    }
-    difference_type n;
-    value_type v;
-    Iterator i;
-  };
-  
 } // namespace boost_concepts
 
 

development/boost/iterator_traits.hpp

@@ -2,21 +2,14 @@
 #define BOOST_ITERATOR_TRAITS_HPP
 
 #include <boost/config.hpp>
-#include <boost/type_traits.hpp>
+#include <boost/type_traits/conversion_traits.hpp>
+#include <boost/type_traits/cv_traits.hpp>
+#include <boost/pending/ct_if.hpp>
+#include <boost/detail/iterator.hpp>
 
 namespace boost {
-  
-  template <typename Iterator>
-  struct iterator_traits {
-    typedef typename Iterator::value_type value_type;
-    typedef typename Iterator::reference reference;
-    typedef typename Iterator::pointer pointer;
-    typedef typename Iterator::difference_type difference_type;
-    typedef typename Iterator::return_category return_category;
-    typedef typename Iterator::motion_category motion_category;
-  };
 
-  // Motion Categories
+  // Traversal Categories
   struct single_pass_iterator_tag { };
   struct forward_iterator_tag : public single_pass_iterator_tag { };
   struct bidirectional_iterator_tag : public forward_iterator_tag { };
@@ -28,29 +21,113 @@ namespace boost {
   struct mutable_lvalue_iterator_tag : virtual public writable_iterator_tag,
     virtual public readable_iterator_tag { };
   struct constant_lvalue_iterator_tag : public readable_iterator_tag { };
-  
-#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
+
+  struct error_iterator_tag { };
+
+  // Inherit from iterator_base if your iterator defines its own
+  // return_category and traversal_category. Otherwise, the "old style"
+  // iterator category will be mapped to the return_category and
+  // traversal_category.
+  struct new_iterator_base { };
 
   namespace detail {
-    template <bool IsConst>
-    struct pointer_return_category {
-      typedef constant_lvalue_iterator_tag type;
+
+    struct iter_traits_from_nested_types {
+      template <typename Iterator> struct bind {
+        typedef typename Iterator::value_type value_type;
+        typedef typename Iterator::reference reference;
+        typedef typename Iterator::pointer pointer;
+        typedef typename Iterator::difference_type difference_type;
+        typedef typename Iterator::return_category return_category;
+        typedef typename Iterator::traversal_category traversal_category;
+      };
     };
-    template <>
-    struct pointer_return_category<false> {
-      typedef mutable_lvalue_iterator_tag type;
+
+    template <typename ValueType>
+    struct choose_lvalue_return {
+      typedef typename ct_if<is_const<ValueType>::value,
+			     boost::constant_lvalue_iterator_tag,
+			     boost::mutable_lvalue_iterator_tag>::type type;
     };
+    
+    
+    template <typename Category, typename ValueType>
+    struct iter_category_to_return {
+      typedef typename ct_if<
+        is_convertible<Category*, std::forward_iterator_tag*>::value,
+        typename choose_lvalue_return<ValueType>::type,
+        typename ct_if<
+          is_convertible<Category*, std::input_iterator_tag*>::value,
+          boost::readable_iterator_tag,
+          typename ct_if<
+            is_convertible<Category*, std::output_iterator_tag*>::value,
+            boost::writable_iterator_tag,
+            boost::error_iterator_tag
+          >::type
+       >::type
+      >::type type;
+    };
+
+    template <typename Category>
+    struct iter_category_to_traversal {
+      typedef typename ct_if<
+        is_convertible<Category*, std::random_access_iterator_tag*>::value,
+        boost::random_access_iterator_tag,
+        typename ct_if<
+          is_convertible<Category*, std::bidirectional_iterator_tag*>::value,
+          boost::bidirectional_iterator_tag,
+          typename ct_if<
+            is_convertible<Category*, std::forward_iterator_tag*>::value,
+            boost::forward_iterator_tag,
+            boost::single_pass_iterator_tag>::type
+          >::type
+        >::type type;
+    };
+
+    struct iter_traits_from_old_traits {
+      template <typename Iterator> class bind {
+        typedef boost::detail::iterator_traits<Iterator> OldTraits;
+        typedef typename OldTraits::iterator_category Cat;
+      public:
+        typedef typename OldTraits::value_type value_type;
+        typedef typename OldTraits::reference reference;
+        typedef typename OldTraits::pointer pointer;
+        typedef typename OldTraits::difference_type difference_type;
+        typedef iter_category_to_return<Cat,value_type>::type return_category;
+        typedef iter_category_to_traversal<Cat>::type traversal_category;
+      };      
+    };
+
+    template <typename Iterator>
+    class choose_iter_traits {
+      typedef typename ct_if<is_convertible<Iterator*,
+                                            new_iterator_base*>::value,
+                             iter_traits_from_nested_types,
+                             iter_traits_from_old_traits>::type Choice;
+    public:
+      typedef typename Choice:: template bind<Iterator> type;
+    };
+    
   } // namespace detail
+  
+  template <typename Iterator>
+  class iterator_traits
+    : public detail::choose_iter_traits<Iterator>::type { };
+
+#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
 
   template <typename T>
-  struct iterator_traits<T*> {
+  struct iterator_traits<T*>
+  {
     typedef T value_type;
     typedef T& reference;
     typedef T* pointer;
     typedef std::ptrdiff_t difference_type;
-    typedef typename detail::pointer_return_category<is_const<T>::value>::type
+    typedef typename ct_if<is_const<T>::value,
+			   boost::constant_lvalue_iterator_tag,
+			   boost::mutable_lvalue_iterator_tag>::type
       return_category;
-    typedef random_access_iterator_tag motion_category;
+    typedef boost::random_access_iterator_tag traversal_category;
   };
 
 #endif

development/libs/iterator/concept_tests.cpp

@@ -1,13 +1,76 @@
 #include <boost/iterator_concepts.hpp>
+#include <boost/operators.hpp>
+
+struct new_iterator
+  : public boost::iterator<std::random_access_iterator_tag, int>,
+    public boost::new_iterator_base
+{
+  typedef boost::random_access_iterator_tag traversal_category;
+  typedef boost::mutable_lvalue_iterator_tag return_category;
+
+  int& operator*() const { return *m_x; }
+  new_iterator& operator++() { return *this; }
+  new_iterator operator++(int) { return *this; }
+  new_iterator& operator--() { return *this; }
+  new_iterator operator--(int) { return *this; }
+  new_iterator& operator+=(std::ptrdiff_t) { return *this; }
+  new_iterator operator+(std::ptrdiff_t) { return *this; }
+  new_iterator& operator-=(std::ptrdiff_t) { return *this; }
+  std::ptrdiff_t operator-(const new_iterator&) const { return 0; }
+  new_iterator operator-(std::ptrdiff_t) const { return *this; }
+  bool operator==(const new_iterator&) const { return false; }
+  bool operator!=(const new_iterator&) const { return false; }
+  bool operator<(const new_iterator&) const { return false; }
+  int* m_x;
+};
+new_iterator operator+(std::ptrdiff_t, new_iterator x) { return x; }
+
+struct old_iterator
+  : public boost::iterator<std::random_access_iterator_tag, int>
+{
+  int& operator*() const { return *m_x; }
+  old_iterator& operator++() { return *this; }
+  old_iterator operator++(int) { return *this; }
+  old_iterator& operator--() { return *this; }
+  old_iterator operator--(int) { return *this; }
+  old_iterator& operator+=(std::ptrdiff_t) { return *this; }
+  old_iterator operator+(std::ptrdiff_t) { return *this; }
+  old_iterator& operator-=(std::ptrdiff_t) { return *this; }
+  old_iterator operator-(std::ptrdiff_t) const { return *this; }
+  std::ptrdiff_t operator-(const old_iterator&) const { return 0; }
+  bool operator==(const old_iterator&) const { return false; }
+  bool operator!=(const old_iterator&) const { return false; }
+  bool operator<(const old_iterator&) const { return false; }
+  int* m_x;
+};
+old_iterator operator+(std::ptrdiff_t, old_iterator x) { return x; }
+
+struct bar { };
+void foo(bar) { }
 
 int
 main()
 {
-  boost::function_requires< 
-    boost_concepts::MutableLvalueRandomAccessIteratorConcept<int*> >();
+#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
+  boost::function_requires<
+    boost_concepts::MutableLvalueIteratorConcept<int*> >();
+  boost::function_requires<
+    boost_concepts::RandomAccessIteratorConcept<int*> >();
 
-  boost::function_requires< 
-    boost_concepts::ConstantLvalueRandomAccessIteratorConcept<const int*> >();
+  boost::function_requires<
+    boost_concepts::ConstantLvalueIteratorConcept<const int*> >();
+  boost::function_requires<
+    boost_concepts::RandomAccessIteratorConcept<const int*> >();
+#endif
 
+  boost::function_requires<
+    boost_concepts::MutableLvalueIteratorConcept<new_iterator> >();
+  boost::function_requires<
+    boost_concepts::RandomAccessIteratorConcept<new_iterator> >();
+
+  boost::function_requires<
+    boost_concepts::MutableLvalueIteratorConcept<old_iterator> >();
+  boost::function_requires<
+    boost_concepts::RandomAccessIteratorConcept<old_iterator> >();
   return 0;
 }

development/libs/iterator/iterator_concepts.htm

@@ -0,0 +1,606 @@
+<HTML>
+<!--
+  -- Copyright (c) Jeremy Siek 2000
+  --
+  -- 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 appears in all copies and
+  -- that both that copyright notice and this permission notice appear
+  -- in supporting documentation.  I make no representations about the
+  -- suitability of this software for any purpose.  It is provided "as is"
+  -- without express or implied warranty.
+  -->
+<!--
+  -- Copyright (c) 1996-1999
+  -- 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 appears 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.
+  --
+  -- 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 appears 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.
+  --
+  -->
+<Head>
+<Title>Iterator Concepts</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
+	ALINK="#ff0000"> 
+<IMG SRC="../../../../c++boost.gif" 
+     ALT="C++ Boost" width="277" height="86"> 
+
+<BR Clear>
+
+<h1>Iterator Concepts</h1>
+
+<p>The standard iterator concepts (the iterator requirements defined
+in the C++ Standard) have a flaw. They glom together two separate
+issues into a single set of concepts. The two issues are iterator
+traversal and dereference return type semantics. These two issues are
+inherently orthogonal and therefore ought to be represented by two
+separate sets of concepts. The concepts described here do just
+that.</p>
+
+One set of concepts handles the return type semantics: 
+<ul>
+  <li><a href="#concept:ReadableIterator">Readable Iterator</a></li>
+  <li><a href="#concept:WritableIterator">Writable Iterator</a></li>
+  <li><a href="#concept:MutableLvalueIterator">Mutable Lvalue Iterator</a></li>
+  <li><a href="#concept:ConstantLvalueIterator">Constant Lvalue Iterator</a></li>
+</ul>
+
+The other set of concepts handles iterator traversal: 
+
+<ul>
+  <li><a href="#concept:SinglePassIterator">Single-Pass Iterator</a></li>
+  <li><a href="#concept:ForwardIterator">Forward Iterator</a></li>
+  <li><a href="#concept:BidirectionalIterator">Bidirectional Iterator</a></li>
+  <li><a href="#concept:RandomAccessIterator">Random Access Iterator</a></li>
+</ul>
+
+<p></p>
+<DIV ALIGN="CENTER"><A NAME="fig:graph-concepts"></A></A>
+<TABLE>
+<CAPTION ALIGN="TOP"><STRONG>Figure 1:</STRONG>
+The iterator concepts and refinement relationships.
+</CAPTION>
+<TR><TD><IMG SRC="./iterator_concepts.gif" width="541" height="214"></TD></TR>
+</TABLE>
+</DIV>
+<p></p>
+
+<h2>Relationship with the standard iterator concepts</h2>
+
+<p>
+std::Input Iterator refines boost::Single-Pass Iterator and
+boost::ReadableIterator.
+
+<p>
+std::Output Iterator refines boost::Single-Pass Iterator and
+boost::Writable Iterator.
+
+<p>
+std::Forward Iterator refines boost::Forward Iterator and
+boost::Constant Lvalue Iterator or boost::Mutable Lvalue Iterator.
+
+<p>
+std::Bidirectional Iterator refines boost::Bidirectional Iterator and
+boost::Constant Lvalue Iterator or boost::Mutable Lvalue Iterator.
+
+<p>
+std::Random Access Iterator refines boost::Random Access Iterator and
+boost::Constant Lvalue Iterator or boost::Mutable Lvalue Iterator.
+
+
+<h3>Notation</h3>
+<Table>
+  <TR>
+    <TD><tt>X</tt></TD>
+    <TD>The iterator type.</TD>
+  </TR>
+  <TR>
+    <TD><tt>T</tt></TD>
+    <TD>The value type of <tt>X</tt>.</TD>
+  </TR>
+  <TR>
+    <TD><tt>x</tt>, <tt>y</tt></TD>
+    <TD>An object of type <tt>X</tt>.</TD>
+  </TR>
+  <TR>
+    <TD><tt>t</tt></TD>
+    <TD>An object of type <tt>T</tt>.</TD>
+  </tr>
+</table>
+
+<p>
+
+<hr>
+
+<H2><A NAME="concept:ReadableIterator"></A>
+Readable Iterator
+</H2>
+
+A Readable Iterator is an iterator that dereferences to produce an
+rvalue that is convertible to the <tt>value_type</tt> of the
+iterator. For example, derefencing may return a temporary object and
+therefore it would be a mistake to bind the result to a reference.
+Also, an attempt to assign a value to the result will most likely
+cause an error.
+
+<pre>
+  template &lt;class Readable Iterator&gt;
+  void foo(Readable Iterator x)
+  {
+    typedef std::iterator_traits&lt;Readable Iterator&gt;::value_type T;
+    T t = *x;  // Read a value. This is OK.
+    T& s = *x; // Bind to a reference. This is a bad idea.
+    *x = t;    // Try to assign. This is a really bad idea.
+  }
+</pre>
+ 
+
+<h3>Associated Types</h3>
+
+<Table border>
+
+  <TR>
+    <TD>Value type</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::value_type</tt></TD>
+    <TD>
+    The type of the value obtained by dereferencing a LvalueIterator
+    </TD>
+  </tr>
+
+  <TR>
+    <TD>Return Category</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::return_category</tt></TD>
+    <TD>
+    A type convertible to <tt>boost::readable_iterator_tag</tt>
+    </TD>
+  </tr>
+
+</Table>
+
+<h3>Refinement of</h3>
+
+<A href="http://www.sgi.com/Technology/STL/Assignable.html">Assignable</A>,
+<A href="http://www.sgi.com/Technology/STL/EqualityComparable.html">Equality Comparable</A>,
+<A href="http://www.sgi.com/Technology/STL/DefaultConstructible.html">Default Constructible</A>
+
+<h3>Valid expressions</h3>
+
+<Table border>
+<TR><TH>Name</TH><TH>Expression</TH><TH>Type requirements</TH><TH>Return type</TH></TR>
+<TR>
+ <TD>Dereference</TD>
+ <TD><tt>*x</tt></TD>
+ <TD>&nbsp;</TD>
+ <TD>Convertible to <tt>T</tt>.</TD>
+</TR>
+<TR>
+ <TD>Member access</TD>
+ <TD><tt>x-&gt;m</tt></TD>
+ <TD><tt>T</tt> is a type with a member named <tt>m</tt>.</TD>
+ <TD>
+ &nbsp;
+ </TD>
+</tr>
+</table>
+
+<p>
+
+<hr>
+
+<H2><A NAME="concept:WritableIterator"></A>
+Writable Iterator
+</H2>
+
+A Writable Iterator is an iterator that can be used to store a value
+using the dereference-assignment expression.
+
+<h3>Definitions</h3>
+
+If <tt>x</tt> is an Writable Iterator of type <tt>X</tt>, then the
+expression <tt>*x = a;</tt> stores the value <tt>a</tt> into
+<tt>x</tt>.  Note that <tt>operator=</tt>, like other C++ functions,
+may be overloaded; it may, in fact, even be a template function.  In
+general, then, <tt>a</tt> may be any of several different types.  A
+type <tt>A</tt> belongs to the <i>set of value types</i> of <tt>X</tt>
+if, for an object <tt>a</tt> of type <tt>A</tt>, <tt>*x = a;</tt> is
+well-defined and does not require performing any non-trivial
+conversions on <tt>a</tt>.
+
+<h3>Associated Types</h3>
+
+<Table border>
+
+  <TR>
+    <TD>Return Category</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::return_category</tt></TD>
+    <TD>
+    A type convertible to <tt>boost::writable_iterator_tag</tt>
+    </TD>
+  </tr>
+
+</Table>
+
+
+
+<h3>Refinement of</h3>
+
+<A href="http://www.sgi.com/Technology/STL/Assignable.html">Assignable</A>,
+<A href="http://www.sgi.com/Technology/STL/EqualityComparable.html">Equality Comparable</A>,
+<A href="http://www.sgi.com/Technology/STL/DefaultConstructible.html">Default Constructible</A>
+
+<h3>Valid expressions</h3>
+
+<Table border>
+  <TR>
+    <TH>Name</TH><TH>Expression</TH><TH>Return type</TH>
+  </TR>
+  <TR>
+    <TD>Dereference assignment</TD>
+    <TD><tt>*x = a</tt></TD>
+    <TD>unspecified</TD>
+  </TR>
+</table>
+
+<p>
+
+<hr>
+
+<H2><A NAME="concept:ConstantLvalueIterator"></A>
+Constant Lvalue Iterator
+</H2>
+
+A Constant Lvalue Iterator is an iterator that dereferences to produce a
+const reference to the pointed-to object, i.e., the associated
+<tt>reference</tt> type is <tt>const T&amp;</tt>. Changing the value
+of or destroying an iterator that models Constant Lvalue Iterator does
+not invalidate pointers and references previously obtained from that
+iterator.
+
+ 
+<h3>Refinement of</h3>
+
+<a href="#concept:Readable Iterator">Readable Iterator</a> 
+
+<h3>Associated Types</h3>
+
+<Table border>
+
+  <TR>
+    <TD>Value type</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::value_type</tt></TD>
+    <TD>
+    The type of the value obtained by dereferencing a Constant Lvalue Iterator.
+    </TD>
+  </tr>
+
+  <TR>
+    <TD>Reference type</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::reference</tt></TD>
+    <TD>
+     The return type of <tt>operator*()</tt>, which must be
+     <tt>const T&amp;</tt>.
+    </TD>
+  </tr>
+
+  <TR>
+    <TD>POinter type</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::pointer</tt></TD>
+    <TD>
+     The pointer to the value type, which must be <tt>const T*</tt>.
+    </TD>
+  </tr>
+
+  <TR>
+    <TD>Return Category</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::return_category</tt></TD>
+    <TD>
+    A type convertible to <tt>boost::constant_lvalue_iterator_tag</tt>
+    </TD>
+  </tr>
+
+</table>
+
+
+<h3>Valid expressions</h3>
+
+<Table border>
+<TR><TH>Name</TH><TH>Expression</TH><TH>Type requirements</TH><TH>Return type</TH></TR>
+<TR>
+ <TD>Dereference</TD>
+ <TD><tt>*x</tt></TD>
+ <TD>&nbsp;</TD>
+ <TD><tt>const T&amp;</tt></TD>
+</TR>
+<TR>
+ <TD>Member access</TD>
+ <TD><tt>x-&gt;m</tt></TD>
+ <TD><tt>T</tt> is a type with a member named <tt>m</tt>.</TD>
+ <TD>
+ &nbsp;
+ </TD>
+</tr>
+</table>
+
+
+<H2><A NAME="concept:MutableLvalueIterator"></A>
+Mutable Lvalue Iterator
+</H2>
+
+A Mutable Lvalue Iterator is an iterator that dereferences to produce a
+reference to the pointed-to object. The associated <tt>reference</tt>
+type is <tt>T&amp;</tt>.  Changing the value of or destroying an
+iterator that models Mutable Lvalue Iterator does not invalidate
+pointers and references previously obtained from that iterator.
+ 
+<h3>Refinement of</h3>
+
+<a href="#concept:Readable Iterator">Readable Iterator</a> and
+<a href="#concept:WritableIterator">Writable Iterator</a>.
+
+
+
+<h3>Associated Types</h3>
+
+<Table border>
+
+  <TR>
+    <TD>Value type</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::value_type</tt></TD>
+    <TD>
+    The type of the value obtained by dereferencing a Mutable Lvalue Iterator.
+    </TD>
+  </tr>
+
+  <TR>
+    <TD>Reference type</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::reference</tt></TD>
+    <TD>
+     The return type of <tt>operator*()</tt>, which is
+     <tt>T&amp;</tt>.
+    </TD>
+  </tr>
+
+  <TR>
+    <TD>Pointer type</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::pointer</tt></TD>
+    <TD>
+     The pointer to the value type, which is <tt>T*</tt>.
+    </TD>
+  </tr>
+
+  <TR>
+    <TD>Return Category</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::return_category</tt></TD>
+    <TD>
+    A type convertible to <tt>boost::mutable_lvalue_iterator_tag</tt>
+    </TD>
+  </tr>
+
+</table>
+
+
+<h3>Valid expressions</h3>
+
+<Table border>
+<TR><TH>Name</TH><TH>Expression</TH><TH>Type requirements</TH><TH>Return type</TH></TR>
+<TR>
+ <TD>Dereference</TD>
+ <TD><tt>*x</tt></TD>
+ <TD>&nbsp;</TD>
+ <TD> <tt>T&amp;</tt> </TD>
+</TR>
+<TR>
+ <TD>Member access</TD>
+ <TD><tt>x-&gt;m</tt></TD>
+ <TD><tt>T</tt> is a type with a member named <tt>m</tt>.</TD>
+ <TD>
+ &nbsp;
+ </TD>
+</tr>
+</table>
+
+<p>
+<hr>
+
+<H2><A NAME="concept:SinglePassIterator"></A>
+Single-Pass Iterator
+</H2>
+
+A Single-Pass Iterator is an iterator that can be incremented to
+traverse through a sequence of objects, but the sequence can only be
+traversed a single time.
+
+<h3>Associated types</h3>
+
+<Table border>
+  <TR>
+    <TD>Difference type</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::difference_type</tt></TD>
+    <TD>
+      A signed integral type used to represent the distance from one
+      iterator to another, or the number of elements in a range.
+    </TD>
+  </TR>
+
+  <TR>
+    <TD>Traversal Category</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::traversal_category</tt></TD>
+    <TD>
+    A type convertible to <tt>boost::single_pass_iterator_tag</tt>
+    </TD>
+  </tr>
+
+</table>
+
+<h3>Valid expressions</h3>
+
+<Table border>
+  <TR>
+    <TH>Name</TH><TH>Expression</TH><TH>Type requirements</TH>
+      <TH>Return type</TH>
+  </TR>
+  <TR>
+    <TD>Preincrement</TD>
+    <TD><tt>++i</tt></TD><TD>&nbsp;</TD><TD><tt>X&amp;</tt></TD>
+  </TR>
+  <TR>
+    <TD>Postincrement</TD>
+    <TD><tt>(void)i++</tt></TD><TD>&nbsp;</TD><TD>&nbsp;</TD>
+  </TR>
+</Table>
+
+<p>
+<hr>
+
+<H2><A NAME="concept:ForwardIterator"></A>
+Forward Iterator
+</H2>
+
+The Forward Iterator is an iterator that can be incremented. Also, it
+is permissible to make multiple passes through the sequence.
+
+<h3>Refinement of</h3>
+
+<a href="#concept:SinglePassIterator">Single-Pass Iterator</a>
+
+<h3>Associated types</h3>
+
+<Table border>
+  <TR>
+    <TD>Traversal Category</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::traversal_category</tt></TD>
+    <TD>
+    A type convertible to <tt>boost::forward_iterator_tag</tt>
+    </TD>
+  </tr>
+</Table>
+
+<p>
+<hr>
+
+<H2><A NAME="concept:BidirectionalIterator"></A>
+Bidirectional Iterator
+</H2>
+
+An iterator that can be incremented and decremented.
+
+<h3>Refinement of</h3>
+
+<a href="#concept:ForwardIterator">Forward Iterator</a>
+
+<h3>Associated types</h3>
+
+<Table border>
+  <TR>
+    <TD>Traversal Category</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::traversal_category</tt></TD>
+    <TD>
+    A type convertible to <tt>boost::bidirectional_iterator_tag</tt>
+    </TD>
+  </tr>
+</Table>
+
+<h3>Valid expressions</h3>
+
+<Table border>
+  <TR>
+  <TH>Name</TH><TH>Expression</TH><TH>Type requirements</TH>
+      <TH>Return type</TH>
+  </TR>
+  <TR><TD>Predecrement</TD>
+      <TD><tt>--i</tt></TD><TD>&nbsp;</TD><TD><tt>X&amp;</tt></TD>
+  </TR>
+  <TR><TD>Postdecrement</TD>
+      <TD><tt>i--</tt></TD><TD>&nbsp;</TD><TD><tt>X</tt></TD>
+  </tr>
+</table>
+
+<p>
+<hr>
+
+<H2><A NAME="concept:RandomAccessIterator"></A>
+Random Access Iterator
+</H2>
+
+An iterator that provides constant-time methods for moving forward and
+backward in arbitrary-sized steps
+
+<h3>Refinement of</h3>
+
+<a href="#concept:BidirectionalIterator">Bidirectional Iterator</a>
+
+<h3>Associated types</h3>
+
+<Table border>
+  <TR>
+    <TD>Traversal Category</TD>
+    <TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::traversal_category</tt></TD>
+    <TD>
+    A type convertible to <tt>boost::random_access_iterator_tag</tt>
+    </TD>
+  </tr>
+</Table>
+
+<h3>Valid expressions</h3>
+
+<Table border>
+<TR><TH>Name</TH><TH>Expression</TH><TH>Type requirements</TH>
+    <TH>Return type</TH>
+</TR>
+<TR><TD>Iterator addition</TD>
+    <TD><tt>i += n</tt></TD><TD>&nbsp;</TD><TD><tt>X&amp;</tt></TD>
+</TR>
+<TR><TD>Iterator addition</TD>
+    <TD><tt>i + n</tt> or <tt>n + i</tt></TD><TD>&nbsp;</TD><TD><tt>X</tt></TD>
+</TR>
+<TR><TD>Iterator subtraction</TD>
+   <TD><tt>i -= n</tt></TD><TD>&nbsp;</TD><TD><tt>X&amp;</tt></TD>
+</TR>
+<TR><TD>Iterator subtraction</TD>
+    <TD><tt>i - n</tt></TD><TD>&nbsp;</TD><TD><tt>X</tt></TD>
+</TR>
+<TR><TD>Difference</TD>
+    <TD><tt>i - j</tt></TD><TD>&nbsp;</TD><TD><tt><a href="./iterator_traits.htm">boost::iterator_traits</a>&lt;X&gt;::difference_type</tt></TD>
+</TR>
+<TR><TD>Element operator</TD>
+    <TD><tt>i[n]</tt></TD>
+    <TD><tt>X</tt> must be a model of
+     <a href="#concept:Readable Iterator">Readable Iterator</a>. </TD>
+    <TD>The same return type as <tt>*i</tt>.</TD>
+</TR>
+<TR><TD>Element assignment</TD>
+    <TD><tt>i[n] = t</tt></TD>
+    <TD><tt>X</tt> must be a model of
+      <a href="#concept:WritableIterator">Writable Iterator</a>.</TD>
+    <TD>unspecified</TD>
+</tr>
+</table>
+
+
+<hr>
+
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright &copy 2000</TD><TD>
+<A HREF="../../../../people/jeremy_siek.htm">Jeremy Siek</A>, Univ.of Notre Dame (<A HREF="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</A>)
+</TD></TR></TABLE>
+
+</body>
+</html>

development/libs/iterator/iterator_traits.htm

@@ -0,0 +1,137 @@
+<html>
+<!--
+  -- Copyright (c) Jeremy Siek 2000
+  --
+  -- 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 appears in all copies and
+  -- that both that copyright notice and this permission notice appear
+  -- in supporting documentation.  I make no representations about the
+  -- suitability of this software for any purpose.  It is provided "as is"
+  -- without express or implied warranty.
+  -->
+  <head>
+    <title>Boost Iterator Traits</title>
+  </head>
+
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
+	ALINK="#ff0000"> 
+<IMG SRC="../../../../c++boost.gif" 
+     ALT="C++ Boost" width="277" height="86"> 
+<BR Clear>
+
+    <h1>Boost Iterator Traits</h1>
+Header <tt><a href="../../boost/iterator_traits.hpp">boost/iterator_traits.hpp</a></tt>
+
+<p>
+The <tt>boost::iterator_traits</tt> class provides access to the
+associated types of iterators that model the Boost <a
+href="./iterator_concepts.htm">Iterator Concepts</a>, which are a
+replacement for the iterator requirements in the C++ standard.
+The main difference between <tt>std::iterator_traits</tt> and
+<tt>boost::iterator_traits</tt> is that the <tt>iterator_category</tt>
+type has been removed, and replaced with two new types:
+
+<ul>
+  <li><tt>traversal_category</tt>:&nbsp;&nbsp; Can the iterator go forward, backward, etc.?
+  <li><tt>return_category</tt>:&nbsp;&nbsp; Is the iterator read or write only?
+    Is the dereferenced type an lvalue?
+</ul>
+
+
+<p>
+An important feature of the <tt>boost::iterator_traits</tt> is that it
+is <b>backwards compatible</b>, i.e., it will automatically work for
+iterators for which there are valid definitions of
+<tt>std::iterator_traits</tt>. The old <tt>iterator_category</tt> is
+mapped to the appropriate traversal and return categories.
+
+<p>
+When creating a new iterator type that is meant to work with
+<tt>boost::iterator_traits</tt>, you can either create a
+specialization of <tt>boost::iterator_traits</tt> for your iterator
+type, or you can provide all the necessary associated types as nested
+typedefs.  In this case, your iterator class will need to inherit from
+<tt>new_iterator_base</tt> to let <tt>boost::iterator_traits</tt> know
+that it will be able to find typedefs for <tt>traversal_category</tt>
+and <tt>return_category</tt> in you iterator class.
+
+
+<pre>
+namespace boost {
+
+  <i>// Inherit from iterator_base if your iterator defines its own
+  // return_category and traversal_category. Otherwise, the "old style"
+  // iterator category will be mapped to the return_category and
+  // traversal_category.</i>
+  struct new_iterator_base { };
+
+  template &lt;typename Iterator&gt;
+  struct iterator_traits
+  {
+    if (Iterator inherits from new_iterator_base) {
+      typedef typename Iterator::value_type value_type;
+      typedef typename Iterator::reference reference;
+      typedef typename Iterator::pointer pointer;
+      typedef typename Iterator::difference_type difference_type;
+      typedef typename Iterator::return_category return_category;
+      typedef typename Iterator::traversal_category traversal_category;
+    } else {
+      typedef std::iterator_traits&lt;Iterator&gt; OldTraits;
+      typedef typename OldTraits::value_type value_type;
+      typedef typename OldTraits::reference reference;
+      typedef typename OldTraits::pointer pointer;
+      typedef typename OldTraits::difference_type difference_type;
+
+      typedef typename OldTraits::iterator_category Cat;
+
+      <i>// Determine the traversal_category based on the old iterator_category</i>
+      if (Cat inherits from std::random_access_iterator_tag)
+        typedef boost::random_access_iterator_tag traversal_category;
+      else if (Cat inherits from std::bidirectional_iterator_tag)
+        typedef boost::bidirectional_iterator_tag traversal_category;
+      else if (Cat inherits from std::forward_iterator_tag)
+        typedef boost::forward_iterator_tag traversal_category;
+      else 
+        typedef boost::single_pass_iterator_tag traversal_category;
+
+      <i>// Determine the return_category based on the old iterator_category and value_type</i>
+      if (Cat inherits from std::forward_iterator_tag)
+        if (is-const(T))
+          typedef boost::constant_lvalue_iterator_tag return_category;
+        else
+          typedef boost::mutable_lvalue_iterator_tag return_category;
+      else if (Cat inherits from std::input_iterator_tag)
+        typedef boost::readable_iterator_tag return_category;
+      else if (Cat inherits from std::output_iterator_tag)
+        typedef boost::writable_iterator_tag return_category;
+      else
+        typedef boost::error_iterator_tag return_category;
+    }
+  };
+
+  template &lt;typename T&gt;
+  struct iterator_traits&lt;T*&gt;
+  {
+    typedef T value_type;
+    typedef T&amp; reference;
+    typedef T* pointer;
+    typedef std::ptrdiff_t difference_type;
+    if (is-const(T))
+      typedef boost::constant_lvalue_iterator_tag return_category;
+    else
+      typedef boost::mutable_lvalue_iterator_tag return_category;
+    typedef boost::random_access_iterator_tag traversal_category;
+  };
+
+}
+</pre>
+
+    <hr>
+    <address><a href="mailto:jsiek@lsc.nd.edu">jeremy siek</a></address>
+<!-- Created: Sun Mar 18 14:06:57 EST 2001 -->
+<!-- hhmts start -->
+Last modified: Mon Mar 19 12:59:30 EST 2001
+<!-- hhmts end -->
+  </body>
+</html>

include/boost/function_output_iterator.hpp

@@ -0,0 +1,55 @@
+// (C) Copyright Jeremy Siek 2001. Permission to copy, use, modify,
+// sell and distribute this software is granted provided this
+// copyright notice appears in all copies. This software is provided
+// "as is" without express or implied warranty, and with no claim as
+// to its suitability for any purpose.
+
+// Revision History:
+
+// 27 Feb 2001   Jeremy Siek
+//      Initial checkin.
+
+#ifndef BOOST_FUNCTION_OUTPUT_ITERATOR_HPP
+#define BOOST_FUNCTION_OUTPUT_ITERATOR_HPP
+
+#include <iterator>
+
+namespace boost {
+
+  template <class UnaryFunction>
+  class function_output_iterator {
+    typedef function_output_iterator self;
+  public:
+    typedef std::output_iterator_tag iterator_category;
+    typedef void                value_type;
+    typedef void                difference_type;
+    typedef void                pointer;
+    typedef void                reference;
+
+    explicit function_output_iterator(const UnaryFunction& f = UnaryFunction())
+      : m_f(f) {}
+
+    struct output_proxy {
+      output_proxy(UnaryFunction& f) : m_f(f) { }
+      template <class T> output_proxy& operator=(const T& value) {
+        m_f(value); 
+        return *this; 
+      }
+      UnaryFunction& m_f;
+    };
+    output_proxy operator*() { return output_proxy(m_f); }
+    self& operator++() { return *this; } 
+    self& operator++(int) { return *this; }
+  private:
+    UnaryFunction m_f;
+  };
+
+  template <class UnaryFunction>
+  inline function_output_iterator<UnaryFunction>
+  make_function_output_iterator(const UnaryFunction& f = UnaryFunction()) {
+    return function_output_iterator<UnaryFunction>(f);
+  }
+
+} // namespace boost
+
+#endif // BOOST_FUNCTION_OUTPUT_ITERATOR_HPP

include/boost/iterator_adaptors.hpp

@@ -12,6 +12,8 @@
 //
 // Revision History:
 
+// 08 Mar 2001   Jeremy Siek
+//      Added support for optional named template parameters.
 // 19 Feb 2001   David Abrahams
 //      Rolled back reverse_iterator_pair_generator again, as it doesn't
 //      save typing on a conforming compiler.
@@ -104,6 +106,7 @@
 # include <boost/type_traits.hpp>
 # include <boost/detail/iterator.hpp>
 # include <boost/detail/select_type.hpp>
+# include <boost/detail/named_template_params.hpp>
 
 // I was having some problems with VC6. I couldn't tell whether our hack for
 // stock GCC was causing problems so I needed an easy way to turn it on and
@@ -220,6 +223,9 @@ struct default_iterator_policies
     void initialize(Base&)
         { }
 
+    // The "type<Reference>" parameter is a portable mechanism for
+    // the iterator_adaptor class to tell this member function what
+    // the Reference type is, which is needed for the return type.
     template <class Reference, class Base>
     Reference dereference(type<Reference>, const Base& x) const
         { return *x; }
@@ -429,8 +435,111 @@ namespace detail {
        
    };
 # endif
+
+  //===========================================================================
+  // Specify the defaults for iterator_adaptor's template parameters
+  
+  struct default_value_type {
+    template <class Base, class Traits>
+    struct bind {
+      typedef typename boost::detail::iterator_traits<Base>::value_type type;
+    };
+  };
+  struct default_difference_type {
+    template <class Base, class Traits>
+    struct bind {
+      typedef typename boost::detail::iterator_traits<Base>::difference_type type;
+    };
+  };
+  struct default_iterator_category {
+    template <class Base, class Traits>
+    struct bind {
+      typedef typename boost::detail::iterator_traits<Base>::iterator_category type;
+    };
+  };
+  struct default_pointer {
+    template <class Base, class Traits>
+    struct bind {
+      typedef typename Traits::value_type Value;
+      typedef typename boost::detail::iterator_defaults<Base,Value>::pointer 
+	type;
+    };
+  };
+  struct default_reference {
+    template <class Base, class Traits>
+    struct bind {
+      typedef typename Traits::value_type Value;
+      typedef typename boost::detail::iterator_defaults<Base,Value>::reference 
+	type;
+    };
+  };
+
+  //===========================================================================
+  // Support for named template parameters
+
+#if !defined(__BORLANDC__)
+  // Borland C++ thinks the nested recursive inheritance here is illegal.
+
+  template <class V = default_argument, 
+            class R = default_argument, 
+            class P = default_argument,
+            class C = default_argument,
+            class D = default_argument>
+  struct iter_traits_gen : public named_template_param_base {
+    template <class T>
+    struct value_type : public iter_traits_gen<T,R,P,C,D> { };
+    template <class T>
+    struct reference : public iter_traits_gen<V,T,P,C,D> { };
+    template <class T>
+    struct pointer : public iter_traits_gen<V,R,T,C,D> { };
+    template <class T>
+    struct iterator_category : public iter_traits_gen<V,R,P,T,D>{};
+    template <class T>
+    struct difference_type : public iter_traits_gen<V,R,P,C,T> { };
+
+    typedef boost::iterator<C, V, D, P, R> traits;
+  };
+#endif
+
+  BOOST_NAMED_TEMPLATE_PARAM(value_type);
+  BOOST_NAMED_TEMPLATE_PARAM(reference);
+  BOOST_NAMED_TEMPLATE_PARAM(pointer);
+  BOOST_NAMED_TEMPLATE_PARAM(iterator_category);
+  BOOST_NAMED_TEMPLATE_PARAM(difference_type);
+
+  template <class Base, class Value, class Reference, class Pointer,
+            class Category, class Distance>
+  class iterator_adaptor_traits_gen
+  {
+    typedef boost::iterator<Category, Value, Distance, Pointer, Reference>
+      Traits0;
+
+    typedef typename get_value_type<Base, 
+        typename boost::remove_const<Value>::type, Traits0
+        >::type value_type;
+    typedef typename get_difference_type<Base, Distance, Traits0>::type
+      difference_type;
+    typedef typename get_iterator_category<Base, Category, Traits0>::type
+      iterator_category;
+
+    typedef boost::iterator<iterator_category, value_type, difference_type,
+      Pointer, Reference> Traits1;
+    
+    typedef typename get_pointer<Base, Pointer, Traits1>::type pointer;
+    typedef typename get_reference<Base, Reference, Traits1>::type reference;
+  public:
+    typedef boost::iterator<iterator_category, value_type, difference_type,
+      pointer, reference> type;
+  };
+  
 } // namespace detail
 
+
+#if !defined(__BORLANDC__)
+struct iterator_traits_generator
+  : public detail::iter_traits_gen<> { };
+#endif
+
 // This macro definition is only temporary in this file
 # if !defined(BOOST_MSVC)
 #  define BOOST_ARG_DEPENDENT_TYPENAME typename
@@ -469,29 +578,32 @@ template <class T> struct undefined;
 //   Distance - the difference_type of the resulting iterator. If not
 //      supplied, iterator_traits<Base>::difference_type is used.
 template <class Base, class Policies, 
-    class Value = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<Base>::value_type,
-    class Reference = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<Base,Value>::reference,
-    class Pointer = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<Base,Value>::pointer,
-    class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<Base>::iterator_category,
-    class Distance = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<Base>::difference_type
+    class Value = detail::default_argument,
+    class Reference = BOOST_ARG_DEPENDENT_TYPENAME detail::choose_default_argument<Value>::type,
+    class Pointer = BOOST_ARG_DEPENDENT_TYPENAME detail::choose_default_argument<Reference>::type,
+    class Category = BOOST_ARG_DEPENDENT_TYPENAME detail::choose_default_argument<Pointer>::type,
+    class Distance = BOOST_ARG_DEPENDENT_TYPENAME detail::choose_default_argument<Category>::type
          >
 struct iterator_adaptor :
 #ifdef BOOST_RELOPS_AMBIGUITY_BUG
     iterator_comparisons<
           iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance>,
-#endif
-    boost::iterator<Category,Value,Distance,Pointer,Reference>
-#ifdef BOOST_RELOPS_AMBIGUITY_BUG
->
+    typename detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category, Distance>::type
+ >
+#else
+    detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category,Distance>::type
 #endif
 {
     typedef iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance> self;
  public:
-    typedef Distance difference_type;
-    typedef typename boost::remove_const<Value>::type value_type;
-    typedef Pointer pointer;
-    typedef Reference reference;
-    typedef Category iterator_category;
+    typedef typename detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category,Distance>::type Traits;
+
+    typedef typename Traits::difference_type difference_type;
+    typedef typename Traits::value_type value_type;
+    typedef typename Traits::pointer pointer;
+    typedef typename Traits::reference reference;
+    typedef typename Traits::iterator_category iterator_category;
+
     typedef Base base_type;
     typedef Policies policies_type;
 
@@ -503,14 +615,18 @@ struct iterator_adaptor :
     // Iterators should satisfy one of the known categories
     BOOST_STATIC_ASSERT(is_input_or_output_iter);
 
-    // Iterators >= ForwardIterator must produce real references.
+    // Iterators >= ForwardIterator must produce real references
+    // as required by the C++ standard requirements in Table 74.
     BOOST_STATIC_CONSTANT(bool, forward_iter_with_real_reference =
            (!boost::is_convertible<iterator_category*,std::forward_iterator_tag*>::value
            || boost::is_same<reference,value_type&>::value
            || boost::is_same<reference,const value_type&>::value));
     
+#if !defined(BOOST_MSVC)
+    // This check gives incorrect results in iter_traits_gen_test.cpp
     BOOST_STATIC_ASSERT(forward_iter_with_real_reference);
-    
+#endif
+
  public:
     iterator_adaptor() { }
 
@@ -545,9 +661,9 @@ struct iterator_adaptor :
 # pragma warning( disable : 4284 )
 #endif
 
-    typename boost::detail::operator_arrow_result_generator<Category,value_type,Pointer>::type
+    typename boost::detail::operator_arrow_result_generator<iterator_category,value_type,pointer>::type
     operator->() const
-        { return detail::operator_arrow(*this, Category()); }
+        { return detail::operator_arrow(*this, iterator_category()); }
 
 #ifdef _MSC_VER
 # pragma warning(pop)
@@ -590,7 +706,7 @@ struct iterator_adaptor :
 
     // Moved from global scope to avoid ambiguity with the operator-() which
     // subtracts iterators from one another.
-    self operator-(Distance x) const
+    self operator-(difference_type x) const
         { self result(*this); return result -= x; }
 private:
     compressed_pair<Base,Policies> m_iter_p;
@@ -626,11 +742,14 @@ operator+(
 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
     class Reference1, class Reference2, class Pointer1, class Pointer2, class Category,
     class Distance>
-Distance operator-(
+typename iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>::difference_type
+operator-(
     const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
     const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
 {
-    return x.policies().distance(type<Distance>(), y.iter(), x.iter());
+  typedef typename iterator_adaptor<Iterator1,Policies,Value1,Reference1,
+    Pointer1,Category,Distance>::difference_type difference_type;
+  return x.policies().distance(type<difference_type>(), y.iter(), x.iter());
 }
 
 #ifndef BOOST_RELOPS_AMBIGUITY_BUG
@@ -967,14 +1086,19 @@ public:
         { return x == y; }
 
  private:
-    void satisfy_predicate(Iterator& iter)
-    {
-        while (m_end != iter && !m_predicate(*iter))
-            ++iter;
-    }
+    void satisfy_predicate(Iterator& iter);
     Predicate m_predicate;
     Iterator m_end;
 };
+template <class Predicate, class Iterator>
+void filter_iterator_policies<Predicate,Iterator>
+::satisfy_predicate(Iterator& iter)
+{
+    while (m_end != iter && !m_predicate(*iter))
+        ++iter;
+}
+
+
 
 namespace detail {
   // A type generator returning Base if T is derived from Base, and T otherwise.
@@ -1005,6 +1129,7 @@ namespace detail {
 # else
       // is_convertible doesn't work with MWERKS
       typedef typename iterator_traits<Iterator>::iterator_category input_category;
+  public:
       typedef typename if_true<(
           boost::is_same<input_category,std::random_access_iterator_tag>::value
           || boost::is_same<input_category,std::bidirectional_iterator_tag>::value