[ceph.git] / ceph / src / boost / libs / multi_array / doc / iterator_categories.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><html><head><!-- saved from url=(0022)http://internet.e-mail --><title>Improved Iterator Categories and Requirements</title>
<meta content="text/html; charset=windows-1252" http-equiv="Content-Type">
<meta content="Microsoft FrontPage 5.0" name="GENERATOR"></head>
<body bgcolor="#ffffff">
<p align="right">
<table border="0">
  <tbody>
  <tr>
    <td width="125">
      <p align="right">Document number: </p></td>
    <td width="190">
      <p>J16/01-0011 = WG21 N1297 </p></td></tr>
  <tr>
    <td width="125">
      <p align="right">Date: </p></td>
    <td width="190">
      <p>March 21, 2001 </p></td></tr>
  <tr>
    <td width="125">
      <p align="right">Author: </p></td>
    <td width="190">
      <p>Jeremy Siek, <br>University of Notre Dame </p></td></tr>
  <tr>
    <td width="125">
      <p></p></td>
    <td width="190">
      <p><a href="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</a> 
  </p></td></tr></tbody></table></p>
<h1>
<center>Improved Iterator Categories and Requirements</center></h1>
<h2>Introduction</h2>The standard iterator categories and requirements are 
flawed because they use a single hierarchy of requirements to address two 
orthogonal issues: <b><i>iterator traversal</i></b> and <b><i>dereference return 
type</i></b>. The current iterator requirement hierarchy is mainly geared 
towards iterator traversal (hence the category names), while requirements that 
address dereference return type sneak in at various places. The following table 
gives a summary of the current dereference return type requirements in the 
iterator categories. 
<p>
</p><center>
<a name="table:1">
  <b>Table 1.</b> Summary of current dereference return type 
  requirements.</a><table border="1">
  <tbody>
  <tr>
    <td>Output Iterator</td>
    <td><tt>*i = a</tt> </td></tr>
  <tr>
    <td>Input Iterator</td>
    <td><tt>*i</tt> is convertible to <tt>T</tt></td></tr>
  <tr>
    <td>Forward Iterator</td>
    <td><tt>*i</tt> is <tt>T&amp;</tt> (or <tt>const T&amp;</tt> once <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#200">issue 
      200</a> is resolved)</td></tr>
  <tr>
    <td>Random Access Iterator</td>
    <td><tt>i[n]</tt> is convertible to <tt>T</tt> (which is odd because the 
      operational semantics say <tt>i[n]</tt> is equivalent to <tt>*(i + n)</tt> 
      which would have a return type of <tt>T&amp;</tt>) </td></tr></tbody></table></center>
<h2>Examples of useful iterators that do not ``fit''</h2>
<p>Because of the mixing of iterator traversal and dereference return type, many 
useful iterators can not be appropriately categorized. For example, 
<tt>vector&lt;bool&gt;::iterator</tt> is almost a random access iterator, but 
the return type is not <tt>bool&amp;</tt> (see <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#96">issue 
96</a> and Herb Sutter's paper J16/99-0008 = WG21 N1185). Therefore, the 
iterators only meet the requirements of input iterator and output iterator. This 
is so nonintuitive that at least one implementation erroneously assigns 
<tt>random_access_iterator_tag</tt> as its <tt>iterator_category</tt>. Also, 
<tt>vector&lt;bool&gt;</tt> is not the only example of useful iterators that do 
not return true references: there is the often cited example of disk-based 
collections. 
</p><p>Another example is a counting iterator, an iterator the returns a sequence of 
integers when incremented and dereferenced (see <a href="http://www.boost.org/libs/iterator/doc/counting_iterator.html"><tt>boost::counting_iterator</tt></a>). 
There are two ways to implement this iterator, 1) make the <tt>reference</tt> 
type be a true reference (a reference to an integer data member of the counting 
iterator) or 2) make the <tt>reference</tt> type be the same as the 
<tt>value_type</tt>. Option 1) runs into the problems discussed in <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#198">Issue 
198</a>, the reference will not be valid after the iterator is destroyed. Option 
2) is therefore a better choice, but then we have a counting iterator that 
cannot be a random access iterator. 
</p><p>Yet another example is a transform iterator, an iterator adaptor that applies 
a unary function object to the dereference value of the wrapped iterator (see <a href="http://www.boost.org/libs/iterator/doc/transform_iterator.html"><tt>boost::transform_iterator</tt></a>). 
For unary functions such as <tt>std::times</tt> the return type of 
<tt>operator*</tt> clearly needs to be the <tt>result_type</tt> of the function 
object, which is typically not a reference. However, with the current iterator 
requirements, if you wrap <tt>int*</tt> with a transform iterator, you do not 
get a random access iterator as expected, but an input iterator. 
</p><p>A fourth example is found in the vertex and edge iterators of the <a href="http://www.boost.org/libs/graph/doc/table_of_contents.html">Boost Graph 
Library</a>. These iterators return vertex and edge descriptors, which are 
lightweight handles created on-the-fly. They must be returned by-value. As a 
result, their current standard iterator category is 
<tt>std::input_iterator_tag</tt>, which means that, strictly speaking, you could 
not use these iterators with algorithms like <tt>std::min_element()</tt>. As a 
temporary solution, we introduced the concept <a href="http://www.boost.org/libs/utility/MultiPassInputIterator.html">Multi-Pass 
Input Iterator</a> to describe the vertex and edge descriptors, but as the 
design notes for concept suggest, a better solution is needed. 
</p><p>In short, there are many useful iterators that do not fit into the current 
standard iterator categories. As a result, the following bad things happen: 
</p><ul>
  <li>Iterators are often miss-categorized. 
  </li><li>Algorithm requirements are more strict than necessary, because they can 
  not separate out the need for random-access from the need for a true reference 
  return type. </li></ul>
<h2>Proposal for new iterator categories and requirements</h2>The iterator 
requirements should be separated into two hierarchies. 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_SwappableIterator">Swappable 
  Iterator</a>  
  </li><li><a href="#concept_ConstantLvalueIterator">Constant 
  Lvalue Iterator</a>  
  </li><li><a href="#concept_MutableLvalueIterator">Mutable 
  Lvalue Iterator</a> </li></ul>The other set of concepts handles iterator 
traversal: 
<ul>
  <li><a href="#concept_ForwardTraversalIterator">Forward 
  Traversal Iterator</a>  
  </li><li><a href="#concept_BidirectionalTraversalIterator">Bidirectional 
  Traversal Iterator</a>  
  </li><li><a href="#concept_RandomAccessTraversalIterator">Random 
  Access Traversal Iterator</a> </li></ul>The current Input Iterator and Output 
Iterator requirements will continue to be used as is. Note that Input Iterator 
implies Readable Iterator and Output Iterator implies Writable Iterator. 
<p>Note: we considered defining a Single-Pass Iterator, which could be combined 
with Readable or Writable Iterator to replace the Input and Output Iterator 
requirements. We rejected this idea because there are several differences 
between Input and Output Iterators that make it hard to merge them: Input 
Iterator requires Equality Comparable while Output Iterator does not and Input 
Iterator requires Assignable while Output Iterator does not. 
</p><h3>New categories and traits classes</h3>Each of the new iterator requirements 
will need a category tag. <pre>namespace std {

  // Return Type Categories
  struct readable_iterator_tag { };
  struct writable_iterator_tag { };
  struct swappable_iterator_tag { };
  struct mutable_lvalue_iterator_tag : virtual public writable_iterator_tag,
    virtual public readable_iterator_tag { };
  struct constant_lvalue_iterator_tag : public readable_iterator_tag { };

  // Traversal Categories
  struct forward_traversal_tag { };
  struct bidirectional_traversal_tag : public forward_traversal_tag { };
  struct random_access_traversal_tag : public bidirectional_traversal_tag { };

}
</pre>And there will need to be a way to access these category tags using a 
traits mechanism. Adding new typedefs to <tt>std::iterator_traits</tt> is not an 
acceptable solution because that would break every existing iterator. Instead, 
we propose two new traits classes. It is important that these traits classes are 
<b>backward compatible</b>, that is, they should work with any iterator for 
which there is a valid definition of <tt>std::iterator_traits</tt>. This can be 
accomplished by making the default behavior of the traits classes map the 
<tt>iterator_category</tt> of the iterator to the appropriate return or 
traversal category. For new iterators, either specializations of these traits 
classes can be defined, or the iterator can provide nested typedefs, and inherit 
from <tt>new_iterator_base</tt> (which is just a signal to the traits class that 
it is a new iterator). As with <tt>std::iterator_traits</tt>, specializations 
for <tt>T*</tt> are provided. <pre>namespace std {

  struct new_iterator_base { };

  template &lt;typename Iterator&gt;
  struct return_category
  {
    <b><i>// Pseudo-code</i></b>
    if (Iterator inherits from new_iterator_base) {
      typedef typename Iterator::return_category type;
    } else {
      typedef std::iterator_traits&lt;Iterator&gt; OldTraits;
      typedef typename OldTraits::iterator_category Cat;
      if (Cat inherits from std::forward_iterator_tag)
	if (is-const(T))
	  typedef boost::constant_lvalue_iterator_tag type;
	else
	  typedef boost::mutable_lvalue_iterator_tag type;
      else if (Cat inherits from std::input_iterator_tag)
	typedef boost::readable_iterator_tag type;
      else if (Cat inherits from std::output_iterator_tag)
	typedef boost::writable_iterator_tag type;
    }
  };

  template &lt;typename T&gt;
  struct return_category&lt;T*&gt;
  {
    <b><i>// Pseudo-code</i></b>
    if (is-const(T))
      typedef boost::constant_lvalue_iterator_tag type;
    else
      typedef boost::mutable_lvalue_iterator_tag type;
  };

  template &lt;typename Iterator&gt;
  struct traversal_category
  {
    <b><i>// Pseudo-code</i></b>
    if (Iterator inherits from new_iterator_base) {
      typedef typename Iterator::traversal_category type;
    } else {
      typedef std::iterator_traits&lt;Iterator&gt; OldTraits;
      typedef typename OldTraits::iterator_category Cat;

      if (Cat inherits from std::random_access_iterator_tag)
	typedef boost::random_access_traversal_tag type;
      else if (Cat inherits from std::bidirectional_iterator_tag)
	typedef boost::bidirectional_traversal_tag type;
      else if (Cat inherits from std::forward_iterator_tag)
	typedef boost::forward_traversal_tag type;
    }
  };

  template &lt;typename T&gt;
  struct traversal_category&lt;T*&gt;
  {
    typedef boost::random_access_traversal_tag type;
  };

}
</pre>
<h2>Impact on the Standard Algorithms</h2>Many of the standard algorithms place 
more requirements than necessary on their iterator parameters due to the 
coarseness of the current iterator categories. By using the new iterator 
categories a better fit can be achieved, thereby increasing the reusability of 
the algorithms. These changes will not affect user-code, though they will 
require changes by standard implementers: dispatching should be based on the new 
categories, and in places return values may need to be handled more carefully. 
In particular, uses of <tt>std::swap()</tt> will need to be replaced with 
<tt>std::iter_swap()</tt>, and <tt>std::iter_swap()</tt> will need to call 
<tt>std::swap()</tt>. 
<p>
</p><center>
<a name="table:2">
  <b>Table 2.</b> Requirement changes for standard 
  algorithms.</a><table border="1">
  <tbody>
  <tr>
    <th>Algorithm</th>
    <th>Requirement Change</th></tr>
  <tr>
    <td>find_end</td>
    <td rowspan="12">Forward Iterator<br>-&gt; Forward Traversal Iterator and 
      Readable Iterator </td></tr>
  <tr>
    <td>find_first_of</td></tr>
  <tr>
    <td>adjacent_find</td></tr>
  <tr>
    <td>search</td></tr>
  <tr>
    <td>search_n</td></tr>
  <tr>
    <td>rotate_copy</td></tr>
  <tr>
    <td>lower_bound</td></tr>
  <tr>
    <td>upper_bound</td></tr>
  <tr>
    <td>equal_range</td></tr>
  <tr>
    <td>binary_search</td></tr>
  <tr>
    <td>min_element</td></tr>
  <tr>
    <td>max_element</td></tr>
  <tr>
    <td>iter_swap</td>
    <td>Forward Iterator<br>-&gt; Swappable Iterator </td></tr>
  <tr>
    <td>fill</td>
    <td rowspan="2">Forward Iterator<br>-&gt; Forward Traversal Iterator and 
      Writable Iterator </td></tr>
  <tr>
    <td>generate</td></tr>
  <tr>
    <td>swap_ranges</td>
    <td rowspan="2">Forward Iterator<br>-&gt; Forward Traversal Iterator and 
      Swappable Iterator </td></tr>
  <tr>
    <td>rotate</td></tr>
  <tr>
    <td>replace</td>
    <td rowspan="5">Forward Iterator<br>-&gt; Forward Traversal Iterator 
      and<br>Readable Iterator and Writable Iterator </td>
  </tr><tr>
    <td>replace_if</td></tr>
  <tr>
    <td>remove</td></tr>
  <tr>
    <td>remove_if</td></tr>
  <tr>
    <td>unique</td></tr>
  <tr>
    <td>reverse</td>
    <td rowspan="2">Bidirectional Iterator<br>-&gt; Bidirectional Traversal 
      Iterator and Swappable Iterator </td></tr>
  <tr>
    <td>partition</td></tr>
  <tr>
    <td>copy_backwards</td>
    <td>Bidirectional Iterator<br>-&gt; Bidirectional Traversal Iterator and 
      Readable Iterator<br>Bidirectional Iterator<br>-&gt; Bidirectional 
      Traversal Iterator and Writable Iterator </td></tr>
  <tr>
    <td>next_permutation</td>
    <td rowspan="2">Bidirectional Iterator<br>-&gt; Bidirectional Traversal 
      Iterator and <br>Swappable Iterator and Readable Iterator </td>
  </tr><tr>
    <td>prev_permutation</td></tr>
  <tr>
    <td>stable_partition</td>
    <td rowspan="2">Bidirectional Iterator<br>-&gt; Bidirectional Traversal 
      Iterator and <br>Readable Iterator and Writable Iterator </td>
  </tr><tr>
    <td>inplace_merge</td></tr>
  <tr>
    <td>reverse_copy</td>
    <td>Bidirectional Iterator<br>-&gt; Bidirectional Traversal Iterator and 
      Readable Iterator </td></tr>
  <tr>
    <td>random_shuffle</td>
    <td rowspan="9">Random Access Iterator<br>-&gt; Random Access Traversal 
      Iterator and Swappable Iterator </td></tr>
  <tr>
    <td>sort</td></tr>
  <tr>
    <td>stable_sort</td></tr>
  <tr>
    <td>partial_sort</td></tr>
  <tr>
    <td>nth_element</td></tr>
  <tr>
    <td>push_heap</td></tr>
  <tr>
    <td>pop_heap</td></tr>
  <tr>
    <td>make_heap</td></tr>
  <tr>
    <td>sort_heap</td></tr></tbody></table></center>
<h2>The New Iterator Requirements</h2>
<h3>Notation</h3>
<table>
  <tbody>
  <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>, i.e., 
      <tt>std::iterator_traits&lt;X&gt;::value_type</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></tbody></table>
<p>
</p><hr>
<!--------------------------------------------------------------------------->
<h3><a name="concept_ReadableIterator"></a>Readable Iterator </h3>A Readable 
Iterator is an iterator that dereferences to produce an rvalue that is 
convertible to the <tt>value_type</tt> of the iterator. 
<h3>Associated Types</h3>
<table border="1">
  <tbody>
  <tr>
    <td>Value type</td>
    <td><tt>std::iterator_traits&lt;X&gt;::value_type</tt></td>
    <td>The type of the objects pointed to by the iterator.</td></tr>
  <tr>
    <td>Reference type</td>
    <td><tt>std::iterator_traits&lt;X&gt;::reference</tt></td>
    <td>The return type of dereferencing the iterator. This type must be 
      convertible to <tt>T</tt>. </td></tr>
  <tr>
    <td>Return Category</td>
    <td><tt>std::return_category&lt;X&gt;::type</tt></td>
    <td>A type convertible to <tt>std::readable_iterator_tag</tt> 
  </td></tr></tbody></table>
<h3>Refinement of</h3><a href="http://www.boost.org/libs/utility/CopyConstructible.html">Copy 
Constructible</a> 
<h3>Valid expressions</h3>
<table border="1">
  <tbody>
  <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>
Commit	Line	Data
7c673cae FG	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><html><head><!-- saved from url=(0022)http://internet.e-mail --><title>Improved Iterator Categories and Requirements</title>
	2	<meta content="text/html; charset=windows-1252" http-equiv="Content-Type">
	3	<meta content="Microsoft FrontPage 5.0" name="GENERATOR"></head>
	4	<body bgcolor="#ffffff">
	5	<p align="right">
	6	<table border="0">
	7	<tbody>
	8	<tr>
	9	<td width="125">
	10	<p align="right">Document number: </p></td>
	11	<td width="190">
	12	<p>J16/01-0011 = WG21 N1297 </p></td></tr>
	13	<tr>
	14	<td width="125">
	15	<p align="right">Date: </p></td>
	16	<td width="190">
	17	<p>March 21, 2001 </p></td></tr>
	18	<tr>
	19	<td width="125">
	20	<p align="right">Author: </p></td>
	21	<td width="190">
	22	<p>Jeremy Siek, <br>University of Notre Dame </p></td></tr>
	23	<tr>
	24	<td width="125">
	25	<p></p></td>
	26	<td width="190">
	27	<p><a href="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</a>
	28	</p></td></tr></tbody></table></p>
	29	<h1>
	30	<center>Improved Iterator Categories and Requirements</center></h1>
	31	<h2>Introduction</h2>The standard iterator categories and requirements are
	32	flawed because they use a single hierarchy of requirements to address two
	33	orthogonal issues: <b><i>iterator traversal</i></b> and <b><i>dereference return
	34	type</i></b>. The current iterator requirement hierarchy is mainly geared
	35	towards iterator traversal (hence the category names), while requirements that
	36	address dereference return type sneak in at various places. The following table
	37	gives a summary of the current dereference return type requirements in the
	38	iterator categories.
	39	<p>
	40	</p><center>
	41	<a name="table:1">
	42	<b>Table 1.</b> Summary of current dereference return type
	43	requirements.</a><table border="1">
	44	<tbody>
	45	<tr>
	46	<td>Output Iterator</td>
	47	<td><tt>*i = a</tt> </td></tr>
	48	<tr>
	49	<td>Input Iterator</td>
	50	<td><tt>*i</tt> is convertible to <tt>T</tt></td></tr>
	51	<tr>
	52	<td>Forward Iterator</td>
	53	<td><tt>*i</tt> is <tt>T&</tt> (or <tt>const T&</tt> once <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#200">issue
	54	200</a> is resolved)</td></tr>
	55	<tr>
	56	<td>Random Access Iterator</td>
	57	<td><tt>i[n]</tt> is convertible to <tt>T</tt> (which is odd because the
	58	operational semantics say <tt>i[n]</tt> is equivalent to <tt>*(i + n)</tt>
	59	which would have a return type of <tt>T&</tt>) </td></tr></tbody></table></center>
	60	<h2>Examples of useful iterators that do not ``fit''</h2>
	61	<p>Because of the mixing of iterator traversal and dereference return type, many
	62	useful iterators can not be appropriately categorized. For example,
	63	<tt>vector<bool>::iterator</tt> is almost a random access iterator, but
	64	the return type is not <tt>bool&</tt> (see <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#96">issue
65	96</a> and Herb Sutter's paper J16/99-0008 = WG21 N1185). Therefore, the
66	iterators only meet the requirements of input iterator and output iterator. This
67	is so nonintuitive that at least one implementation erroneously assigns
68	<tt>random_access_iterator_tag</tt> as its <tt>iterator_category</tt>. Also,
69	<tt>vector<bool></tt> is not the only example of useful iterators that do
70	not return true references: there is the often cited example of disk-based
71	collections.
72	</p><p>Another example is a counting iterator, an iterator the returns a sequence of
73	integers when incremented and dereferenced (see <a href="http://www.boost.org/libs/iterator/doc/counting_iterator.html"><tt>boost::counting_iterator</tt></a>).
74	There are two ways to implement this iterator, 1) make the <tt>reference</tt>
75	type be a true reference (a reference to an integer data member of the counting
76	iterator) or 2) make the <tt>reference</tt> type be the same as the
77	<tt>value_type</tt>. Option 1) runs into the problems discussed in <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#198">Issue
78	198</a>, the reference will not be valid after the iterator is destroyed. Option
79	2) is therefore a better choice, but then we have a counting iterator that
80	cannot be a random access iterator.
81	</p><p>Yet another example is a transform iterator, an iterator adaptor that applies
82	a unary function object to the dereference value of the wrapped iterator (see <a href="http://www.boost.org/libs/iterator/doc/transform_iterator.html"><tt>boost::transform_iterator</tt></a>).
83	For unary functions such as <tt>std::times</tt> the return type of
84	<tt>operator*</tt> clearly needs to be the <tt>result_type</tt> of the function
85	object, which is typically not a reference. However, with the current iterator
86	requirements, if you wrap <tt>int*</tt> with a transform iterator, you do not
87	get a random access iterator as expected, but an input iterator.
88	</p><p>A fourth example is found in the vertex and edge iterators of the <a href="http://www.boost.org/libs/graph/doc/table_of_contents.html">Boost Graph
89	Library</a>. These iterators return vertex and edge descriptors, which are
90	lightweight handles created on-the-fly. They must be returned by-value. As a
91	result, their current standard iterator category is
92	<tt>std::input_iterator_tag</tt>, which means that, strictly speaking, you could
93	not use these iterators with algorithms like <tt>std::min_element()</tt>. As a
94	temporary solution, we introduced the concept <a href="http://www.boost.org/libs/utility/MultiPassInputIterator.html">Multi-Pass
95	Input Iterator</a> to describe the vertex and edge descriptors, but as the
96	design notes for concept suggest, a better solution is needed.
97	</p><p>In short, there are many useful iterators that do not fit into the current
98	standard iterator categories. As a result, the following bad things happen:
99	</p><ul>
100	<li>Iterators are often miss-categorized.
101	</li><li>Algorithm requirements are more strict than necessary, because they can
102	not separate out the need for random-access from the need for a true reference
103	return type. </li></ul>
104	<h2>Proposal for new iterator categories and requirements</h2>The iterator
105	requirements should be separated into two hierarchies. One set of concepts
106	handles the return type semantics:
107	<ul>
108	<li><a href="#concept_ReadableIterator">Readable
109	Iterator</a>
110	</li><li><a href="#concept_WritableIterator">Writable
111	Iterator</a>
112	</li><li><a href="#concept_SwappableIterator">Swappable
113	Iterator</a>
114	</li><li><a href="#concept_ConstantLvalueIterator">Constant
115	Lvalue Iterator</a>
116	</li><li><a href="#concept_MutableLvalueIterator">Mutable
117	Lvalue Iterator</a> </li></ul>The other set of concepts handles iterator
118	traversal:
119	<ul>
120	<li><a href="#concept_ForwardTraversalIterator">Forward
121	Traversal Iterator</a>
122	</li><li><a href="#concept_BidirectionalTraversalIterator">Bidirectional
123	Traversal Iterator</a>
124	</li><li><a href="#concept_RandomAccessTraversalIterator">Random
125	Access Traversal Iterator</a> </li></ul>The current Input Iterator and Output
126	Iterator requirements will continue to be used as is. Note that Input Iterator
127	implies Readable Iterator and Output Iterator implies Writable Iterator.
128	<p>Note: we considered defining a Single-Pass Iterator, which could be combined
129	with Readable or Writable Iterator to replace the Input and Output Iterator
130	requirements. We rejected this idea because there are several differences
131	between Input and Output Iterators that make it hard to merge them: Input
132	Iterator requires Equality Comparable while Output Iterator does not and Input
133	Iterator requires Assignable while Output Iterator does not.
134	</p><h3>New categories and traits classes</h3>Each of the new iterator requirements
135	will need a category tag. <pre>namespace std {
136
137	// Return Type Categories
138	struct readable_iterator_tag { };
139	struct writable_iterator_tag { };
140	struct swappable_iterator_tag { };
141	struct mutable_lvalue_iterator_tag : virtual public writable_iterator_tag,
142	virtual public readable_iterator_tag { };
143	struct constant_lvalue_iterator_tag : public readable_iterator_tag { };
144
145	// Traversal Categories
146	struct forward_traversal_tag { };
147	struct bidirectional_traversal_tag : public forward_traversal_tag { };
148	struct random_access_traversal_tag : public bidirectional_traversal_tag { };
149
150	}
151	</pre>And there will need to be a way to access these category tags using a
152	traits mechanism. Adding new typedefs to <tt>std::iterator_traits</tt> is not an
153	acceptable solution because that would break every existing iterator. Instead,
154	we propose two new traits classes. It is important that these traits classes are
155	<b>backward compatible</b>, that is, they should work with any iterator for
156	which there is a valid definition of <tt>std::iterator_traits</tt>. This can be
157	accomplished by making the default behavior of the traits classes map the
158	<tt>iterator_category</tt> of the iterator to the appropriate return or
159	traversal category. For new iterators, either specializations of these traits
160	classes can be defined, or the iterator can provide nested typedefs, and inherit
161	from <tt>new_iterator_base</tt> (which is just a signal to the traits class that
162	it is a new iterator). As with <tt>std::iterator_traits</tt>, specializations
163	for <tt>T*</tt> are provided. <pre>namespace std {
164
165	struct new_iterator_base { };
166
167	template <typename Iterator>
168	struct return_category
169	{
170	<b><i>// Pseudo-code</i></b>
171	if (Iterator inherits from new_iterator_base) {
172	typedef typename Iterator::return_category type;
173	} else {
174	typedef std::iterator_traits<Iterator> OldTraits;
175	typedef typename OldTraits::iterator_category Cat;
176	if (Cat inherits from std::forward_iterator_tag)
177	if (is-const(T))
178	typedef boost::constant_lvalue_iterator_tag type;
179	else
180	typedef boost::mutable_lvalue_iterator_tag type;
181	else if (Cat inherits from std::input_iterator_tag)
182	typedef boost::readable_iterator_tag type;
183	else if (Cat inherits from std::output_iterator_tag)
184	typedef boost::writable_iterator_tag type;
185	}
186	};
187
188	template <typename T>
189	struct return_category<T*>
190	{
191	<b><i>// Pseudo-code</i></b>
192	if (is-const(T))
193	typedef boost::constant_lvalue_iterator_tag type;
194	else
195	typedef boost::mutable_lvalue_iterator_tag type;
196	};
197
198	template <typename Iterator>
199	struct traversal_category
200	{
201	<b><i>// Pseudo-code</i></b>
202	if (Iterator inherits from new_iterator_base) {
203	typedef typename Iterator::traversal_category type;
204	} else {
205	typedef std::iterator_traits<Iterator> OldTraits;
206	typedef typename OldTraits::iterator_category Cat;
207
208	if (Cat inherits from std::random_access_iterator_tag)
209	typedef boost::random_access_traversal_tag type;
210	else if (Cat inherits from std::bidirectional_iterator_tag)
211	typedef boost::bidirectional_traversal_tag type;
212	else if (Cat inherits from std::forward_iterator_tag)
213	typedef boost::forward_traversal_tag type;
214	}
215	};
216
217	template <typename T>
218	struct traversal_category<T*>
219	{
220	typedef boost::random_access_traversal_tag type;
221	};
222
223	}
224	</pre>
225	<h2>Impact on the Standard Algorithms</h2>Many of the standard algorithms place
226	more requirements than necessary on their iterator parameters due to the
227	coarseness of the current iterator categories. By using the new iterator
228	categories a better fit can be achieved, thereby increasing the reusability of
229	the algorithms. These changes will not affect user-code, though they will
230	require changes by standard implementers: dispatching should be based on the new
231	categories, and in places return values may need to be handled more carefully.
232	In particular, uses of <tt>std::swap()</tt> will need to be replaced with
233	<tt>std::iter_swap()</tt>, and <tt>std::iter_swap()</tt> will need to call
234	<tt>std::swap()</tt>.
235	<p>
236	</p><center>
237	<a name="table:2">
238	<b>Table 2.</b> Requirement changes for standard
239	algorithms.</a><table border="1">
240	<tbody>
241	<tr>
242	<th>Algorithm</th>
243	<th>Requirement Change</th></tr>
244	<tr>
245	<td>find_end</td>
246	<td rowspan="12">Forward Iterator<br>-> Forward Traversal Iterator and
247	Readable Iterator </td></tr>
248	<tr>
249	<td>find_first_of</td></tr>
250	<tr>
251	<td>adjacent_find</td></tr>
252	<tr>
253	<td>search</td></tr>
254	<tr>
255	<td>search_n</td></tr>
256	<tr>
257	<td>rotate_copy</td></tr>
258	<tr>
259	<td>lower_bound</td></tr>
260	<tr>
261	<td>upper_bound</td></tr>
262	<tr>
263	<td>equal_range</td></tr>
264	<tr>
265	<td>binary_search</td></tr>
266	<tr>
267	<td>min_element</td></tr>
268	<tr>
269	<td>max_element</td></tr>
270	<tr>
271	<td>iter_swap</td>
272	<td>Forward Iterator<br>-> Swappable Iterator </td></tr>
273	<tr>
274	<td>fill</td>
275	<td rowspan="2">Forward Iterator<br>-> Forward Traversal Iterator and
276	Writable Iterator </td></tr>
277	<tr>
278	<td>generate</td></tr>
279	<tr>
280	<td>swap_ranges</td>
281	<td rowspan="2">Forward Iterator<br>-> Forward Traversal Iterator and
282	Swappable Iterator </td></tr>
283	<tr>
284	<td>rotate</td></tr>
285	<tr>
286	<td>replace</td>
287	<td rowspan="5">Forward Iterator<br>-> Forward Traversal Iterator
288	and<br>Readable Iterator and Writable Iterator </td>
289	</tr><tr>
290	<td>replace_if</td></tr>
291	<tr>
292	<td>remove</td></tr>
293	<tr>
294	<td>remove_if</td></tr>
295	<tr>
296	<td>unique</td></tr>
297	<tr>
298	<td>reverse</td>
299	<td rowspan="2">Bidirectional Iterator<br>-> Bidirectional Traversal
300	Iterator and Swappable Iterator </td></tr>
301	<tr>
302	<td>partition</td></tr>
303	<tr>
304	<td>copy_backwards</td>
305	<td>Bidirectional Iterator<br>-> Bidirectional Traversal Iterator and
306	Readable Iterator<br>Bidirectional Iterator<br>-> Bidirectional
307	Traversal Iterator and Writable Iterator </td></tr>
308	<tr>
309	<td>next_permutation</td>
310	<td rowspan="2">Bidirectional Iterator<br>-> Bidirectional Traversal
311	Iterator and <br>Swappable Iterator and Readable Iterator </td>
312	</tr><tr>
313	<td>prev_permutation</td></tr>
314	<tr>
315	<td>stable_partition</td>
316	<td rowspan="2">Bidirectional Iterator<br>-> Bidirectional Traversal
317	Iterator and <br>Readable Iterator and Writable Iterator </td>
318	</tr><tr>
319	<td>inplace_merge</td></tr>
320	<tr>
321	<td>reverse_copy</td>
322	<td>Bidirectional Iterator<br>-> Bidirectional Traversal Iterator and
323	Readable Iterator </td></tr>
324	<tr>
325	<td>random_shuffle</td>
326	<td rowspan="9">Random Access Iterator<br>-> Random Access Traversal
327	Iterator and Swappable Iterator </td></tr>
328	<tr>
329	<td>sort</td></tr>
330	<tr>
331	<td>stable_sort</td></tr>
332	<tr>
333	<td>partial_sort</td></tr>
334	<tr>
335	<td>nth_element</td></tr>
336	<tr>
337	<td>push_heap</td></tr>
338	<tr>
339	<td>pop_heap</td></tr>
340	<tr>
341	<td>make_heap</td></tr>
342	<tr>
343	<td>sort_heap</td></tr></tbody></table></center>
344	<h2>The New Iterator Requirements</h2>
345	<h3>Notation</h3>
346	<table>
347	<tbody>
348	<tr>
349	<td><tt>X</tt></td>
350	<td>The iterator type.</td></tr>
351	<tr>
352	<td><tt>T</tt></td>
353	<td>The value type of <tt>X</tt>, i.e.,
354	<tt>std::iterator_traits<X>::value_type</tt>.</td></tr>
355	<tr>
356	<td><tt>x</tt>, <tt>y</tt></td>
357	<td>An object of type <tt>X</tt>.</td></tr>
358	<tr>
359	<td><tt>t</tt></td>
360	<td>An object of type <tt>T</tt>.</td></tr></tbody></table>
361	<p>
362	</p><hr>
363	<!--------------------------------------------------------------------------->
364	<h3><a name="concept_ReadableIterator"></a>Readable Iterator </h3>A Readable
365	Iterator is an iterator that dereferences to produce an rvalue that is
366	convertible to the <tt>value_type</tt> of the iterator.
367	<h3>Associated Types</h3>
368	<table border="1">
369	<tbody>
370	<tr>
371	<td>Value type</td>
372	<td><tt>std::iterator_traits<X>::value_type</tt></td>
373	<td>The type of the objects pointed to by the iterator.</td></tr>
374	<tr>
375	<td>Reference type</td>
376	<td><tt>std::iterator_traits<X>::reference</tt></td>
377	<td>The return type of dereferencing the iterator. This type must be
378	convertible to <tt>T</tt>. </td></tr>
379	<tr>
380	<td>Return Category</td>
381	<td><tt>std::return_category<X>::type</tt></td>
382	<td>A type convertible to <tt>std::readable_iterator_tag</tt>
383	</td></tr></tbody></table>
384	<h3>Refinement of</h3><a href="http://www.boost.org/libs/utility/CopyConstructible.html">Copy
385	Constructible</a>
386	<h3>Valid expressions</h3>
387	<table border="1">
388	<tbody>
389	<tr>
390	<th>Name</th>
391	<th>Expression</th>
392	<th>Type requirements</th>
393	<th>Return type</th></tr>
394	<tr>
395	<td>Dereference</td>
396	<td><tt>*x</tt></td>
397