]>
Commit | Line | Data |
---|---|---|
1 | <?xml version="1.0" encoding="utf-8" ?> | |
2 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> | |
3 | <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> | |
4 | <head> | |
5 | <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> | |
6 | <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> | |
7 | <title>The Boost.Iterator Library Boost</title> | |
8 | <link rel="stylesheet" href="../../../rst.css" type="text/css" /> | |
9 | </head> | |
10 | <body> | |
11 | <div class="document" id="the-boost-iterator-library-logo"> | |
12 | <h1 class="title">The Boost.Iterator Library <a class="reference external" href="../../../index.htm"><img alt="Boost" src="../../../boost.png" /></a></h1> | |
13 | ||
14 | <!-- Distributed under the Boost --> | |
15 | <!-- Software License, Version 1.0. (See accompanying --> | |
16 | <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> | |
17 | <hr class="docutils" /> | |
18 | <table class="docutils field-list" frame="void" rules="none"> | |
19 | <col class="field-name" /> | |
20 | <col class="field-body" /> | |
21 | <tbody valign="top"> | |
22 | <tr class="field"><th class="field-name">Authors:</th><td class="field-body">David Abrahams, Jeremy Siek, Thomas Witt</td> | |
23 | </tr> | |
24 | <tr class="field"><th class="field-name">Contact:</th><td class="field-body"><a class="reference external" href="mailto:dave@boost-consulting.com">dave@boost-consulting.com</a>, <a class="reference external" href="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>, <a class="reference external" href="mailto:witt@styleadvisor.com">witt@styleadvisor.com</a></td> | |
25 | </tr> | |
26 | <tr class="field"><th class="field-name">organizations:</th><td class="field-body"><a class="reference external" href="http://www.boost-consulting.com">Boost Consulting</a>, Indiana University <a class="reference external" href="http://www.osl.iu.edu">Open Systems | |
27 | Lab</a>, <a class="reference external" href="http://www.styleadvisor.com">Zephyr Associates, Inc.</a></td> | |
28 | </tr> | |
29 | <tr class="field"><th class="field-name">date:</th><td class="field-body">$Date$</td> | |
30 | </tr> | |
31 | <tr class="field"><th class="field-name">copyright:</th><td class="field-body">Copyright David Abrahams, Jeremy Siek, Thomas Witt 2003.</td> | |
32 | </tr> | |
33 | </tbody> | |
34 | </table> | |
35 | <table class="docutils field-list" frame="void" rules="none"> | |
36 | <col class="field-name" /> | |
37 | <col class="field-body" /> | |
38 | <tbody valign="top"> | |
39 | <tr class="field"><th class="field-name">Abstract:</th><td class="field-body">The Boost Iterator Library contains two parts. The first | |
40 | is a system of <a class="reference external" href="http://www.boost.org/more/generic_programming.html#concept">concepts</a> which extend the C++ standard | |
41 | iterator requirements. The second is a framework of | |
42 | components for building iterators based on these | |
43 | extended concepts and includes several useful iterator | |
44 | adaptors. The extended iterator concepts have been | |
45 | carefully designed so that old-style iterators | |
46 | can fit in the new concepts and so that new-style | |
47 | iterators will be compatible with old-style algorithms, | |
48 | though algorithms may need to be updated if they want to | |
49 | take full advantage of the new-style iterator | |
50 | capabilities. Several components of this library have | |
51 | been accepted into the C++ standard technical report. | |
52 | The components of the Boost Iterator Library replace the | |
53 | older Boost Iterator Adaptor Library.</td> | |
54 | </tr> | |
55 | </tbody> | |
56 | </table> | |
57 | <div class="contents topic" id="table-of-contents"> | |
58 | <p class="topic-title first"><strong>Table of Contents</strong></p> | |
59 | <ul class="simple"> | |
60 | <li><a class="reference internal" href="#new-style-iterators" id="id23">New-Style Iterators</a></li> | |
61 | <li><a class="reference internal" href="#iterator-facade-and-adaptor" id="id24">Iterator Facade and Adaptor</a></li> | |
62 | <li><a class="reference internal" href="#specialized-adaptors" id="id25">Specialized Adaptors</a></li> | |
63 | <li><a class="reference internal" href="#iterator-utilities" id="id26">Iterator Utilities</a><ul> | |
64 | <li><a class="reference internal" href="#traits" id="id27">Traits</a></li> | |
65 | <li><a class="reference internal" href="#testing-and-concept-checking" id="id28">Testing and Concept Checking</a></li> | |
66 | </ul> | |
67 | </li> | |
68 | <li><a class="reference internal" href="#upgrading-from-the-old-boost-iterator-adaptor-library" id="id29">Upgrading from the old Boost Iterator Adaptor Library</a></li> | |
69 | <li><a class="reference internal" href="#history" id="id30">History</a></li> | |
70 | </ul> | |
71 | </div> | |
72 | <hr class="docutils" /> | |
73 | <div class="section" id="new-style-iterators"> | |
74 | <h1><a class="toc-backref" href="#id23">New-Style Iterators</a></h1> | |
75 | <p>The iterator categories defined in C++98 are extremely limiting | |
76 | because they bind together two orthogonal concepts: traversal and | |
77 | element access. For example, because a random access iterator is | |
78 | required to return a reference (and not a proxy) when dereferenced, | |
79 | it is impossible to capture the capabilities of | |
80 | <tt class="docutils literal"><span class="pre">vector<bool>::iterator</span></tt> using the C++98 categories. This is the | |
81 | infamous "<tt class="docutils literal"><span class="pre">vector<bool></span></tt> is not a container, and its iterators | |
82 | aren't random access iterators", debacle about which Herb Sutter | |
83 | wrote two papers for the standards comittee (<a class="reference external" href="http://www.gotw.ca/publications/N1185.pdf">n1185</a> and <a class="reference external" href="http://www.gotw.ca/publications/N1211.pdf">n1211</a>), | |
84 | and a <a class="reference external" href="http://www.gotw.ca/gotw/050.htm">Guru of the Week</a>. New-style iterators go well beyond | |
85 | patching up <tt class="docutils literal"><span class="pre">vector<bool></span></tt>, though: there are lots of other | |
86 | iterators already in use which can't be adequately represented by | |
87 | the existing concepts. For details about the new iterator | |
88 | concepts, see our</p> | |
89 | <blockquote> | |
90 | <a class="reference external" href="new-iter-concepts.html">Standard Proposal For New-Style Iterators</a> (<a class="reference external" href="new-iter-concepts.pdf">PDF</a>)</blockquote> | |
91 | </div> | |
92 | <div class="section" id="iterator-facade-and-adaptor"> | |
93 | <h1><a class="toc-backref" href="#id24">Iterator Facade and Adaptor</a></h1> | |
94 | <p>Writing standard-conforming iterators is tricky, but the need comes | |
95 | up often. In order to ease the implementation of new iterators, | |
96 | the Boost.Iterator library provides the <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> class template, | |
97 | which implements many useful defaults and compile-time checks | |
98 | designed to help the iterator author ensure that his iterator is | |
99 | correct.</p> | |
100 | <p>It is also common to define a new iterator that is similar to some | |
101 | underlying iterator or iterator-like type, but that modifies some | |
102 | aspect of the underlying type's behavior. For that purpose, the | |
103 | library supplies the <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> class template, which is specially | |
104 | designed to take advantage of as much of the underlying type's | |
105 | behavior as possible.</p> | |
106 | <p>The documentation for these two classes can be found at the following | |
107 | web pages:</p> | |
108 | <ul class="simple"> | |
109 | <li><a class="reference external" href="iterator_facade.html"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt></a> (<a class="reference external" href="iterator_facade.pdf">PDF</a>)</li> | |
110 | <li><a class="reference external" href="iterator_adaptor.html"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt></a> (<a class="reference external" href="iterator_adaptor.pdf">PDF</a>)</li> | |
111 | </ul> | |
112 | <p>Both <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> and <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> as well as many of the <a class="reference internal" href="#specialized-adaptors">specialized | |
113 | adaptors</a> mentioned below have been proposed for standardization, | |
114 | and accepted into the first C++ technical report; see our</p> | |
115 | <blockquote> | |
116 | <a class="reference external" href="facade-and-adaptor.html">Standard Proposal For Iterator Facade and Adaptor</a> (<a class="reference external" href="facade-and-adaptor.pdf">PDF</a>)</blockquote> | |
117 | <p>for more details.</p> | |
118 | </div> | |
119 | <div class="section" id="specialized-adaptors"> | |
120 | <h1><a class="toc-backref" href="#id25">Specialized Adaptors</a></h1> | |
121 | <p>The iterator library supplies a useful suite of standard-conforming | |
122 | iterator templates based on the Boost <a class="reference internal" href="#iterator-facade-and-adaptor">iterator facade and adaptor</a>.</p> | |
123 | <ul class="simple"> | |
124 | <li><a class="reference external" href="counting_iterator.html"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt></a> (<a class="reference external" href="counting_iterator.pdf">PDF</a>): an iterator over a sequence of consecutive values. | |
125 | Implements a "lazy sequence"</li> | |
126 | <li><a class="reference external" href="filter_iterator.html"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt></a> (<a class="reference external" href="filter_iterator.pdf">PDF</a>): an iterator over the subset of elements of some | |
127 | sequence which satisfy a given predicate</li> | |
128 | <li><a class="reference external" href="function_input_iterator.html"><tt class="docutils literal"><span class="pre">function_input_iterator</span></tt></a> (<a class="reference external" href="function_input_iterator.pdf">PDF</a>): an input iterator wrapping a generator (nullary | |
129 | function object); each time the iterator is dereferenced, the function object | |
130 | is called to get the value to return.</li> | |
131 | <li><a class="reference external" href="function_output_iterator.html"><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt></a> (<a class="reference external" href="function_output_iterator.pdf">PDF</a>): an output iterator wrapping a unary function | |
132 | object; each time an element is written into the dereferenced | |
133 | iterator, it is passed as a parameter to the function object.</li> | |
134 | <li><a class="reference external" href="indirect_iterator.html"><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt></a> (<a class="reference external" href="indirect_iterator.pdf">PDF</a>): an iterator over the objects <em>pointed-to</em> by the | |
135 | elements of some sequence.</li> | |
136 | <li><a class="reference external" href="permutation_iterator.html"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt></a> (<a class="reference external" href="permutation_iterator.pdf">PDF</a>): an iterator over the elements of some random-access | |
137 | sequence, rearranged according to some sequence of integer indices.</li> | |
138 | <li><a class="reference external" href="reverse_iterator.html"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt></a> (<a class="reference external" href="reverse_iterator.pdf">PDF</a>): an iterator which traverses the elements of some | |
139 | bidirectional sequence in reverse. Corrects many of the | |
140 | shortcomings of C++98's <tt class="docutils literal"><span class="pre">std::reverse_iterator</span></tt>.</li> | |
141 | <li><a class="reference external" href="../../utility/shared_container_iterator.html"><tt class="docutils literal"><span class="pre">shared_container_iterator</span></tt></a>: an iterator over elements of a container whose | |
142 | lifetime is maintained by a <a class="reference external" href="../../smart_ptr/shared_ptr.htm"><tt class="docutils literal"><span class="pre">shared_ptr</span></tt></a> stored in the iterator.</li> | |
143 | <li><a class="reference external" href="transform_iterator.html"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt></a> (<a class="reference external" href="transform_iterator.pdf">PDF</a>): an iterator over elements which are the result of | |
144 | applying some functional transformation to the elements of an | |
145 | underlying sequence. This component also replaces the old | |
146 | <tt class="docutils literal"><span class="pre">projection_iterator_adaptor</span></tt>.</li> | |
147 | <li><a class="reference external" href="zip_iterator.html"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt></a> (<a class="reference external" href="zip_iterator.pdf">PDF</a>): an iterator over tuples of the elements at corresponding | |
148 | positions of heterogeneous underlying iterators.</li> | |
149 | </ul> | |
150 | </div> | |
151 | <div class="section" id="iterator-utilities"> | |
152 | <h1><a class="toc-backref" href="#id26">Iterator Utilities</a></h1> | |
153 | <div class="section" id="traits"> | |
154 | <h2><a class="toc-backref" href="#id27">Traits</a></h2> | |
155 | <ul class="simple"> | |
156 | <li><a class="reference external" href="pointee.html"><tt class="docutils literal"><span class="pre">pointee.hpp</span></tt></a> (<a class="reference external" href="pointee.pdf">PDF</a>): Provides the capability to deduce the referent types | |
157 | of pointers, smart pointers and iterators in generic code. Used | |
158 | in <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt>.</li> | |
159 | <li><a class="reference external" href="iterator_traits.html"><tt class="docutils literal"><span class="pre">iterator_traits.hpp</span></tt></a> (<a class="reference external" href="iterator_traits.pdf">PDF</a>): Provides <a class="reference external" href="../../mpl/doc/index.html">MPL</a>-compatible metafunctions which | |
160 | retrieve an iterator's traits. Also corrects for the deficiencies | |
161 | of broken implementations of <tt class="docutils literal"><span class="pre">std::iterator_traits</span></tt>.</li> | |
162 | </ul> | |
163 | <!-- * |interoperable|_ (PDF__): Provides an MPL_\ -compatible metafunction for | |
164 | testing iterator interoperability --> | |
165 | <!-- comment! __ interoperable.pdf --> | |
166 | </div> | |
167 | <div class="section" id="testing-and-concept-checking"> | |
168 | <h2><a class="toc-backref" href="#id28">Testing and Concept Checking</a></h2> | |
169 | <ul class="simple"> | |
170 | <li><a class="reference external" href="iterator_concepts.html"><tt class="docutils literal"><span class="pre">iterator_concepts.hpp</span></tt></a> (<a class="reference external" href="iterator_concepts.pdf">PDF</a>): Concept checking classes for the new iterator concepts.</li> | |
171 | <li><a class="reference external" href="iterator_archetypes.html"><tt class="docutils literal"><span class="pre">iterator_archetypes.hpp</span></tt></a> (<a class="reference external" href="iterator_archetypes.pdf">PDF</a>): Concept archetype classes for the new iterators concepts.</li> | |
172 | </ul> | |
173 | </div> | |
174 | </div> | |
175 | <div class="section" id="upgrading-from-the-old-boost-iterator-adaptor-library"> | |
176 | <h1><a class="toc-backref" href="#id29">Upgrading from the old Boost Iterator Adaptor Library</a></h1> | |
177 | <p id="upgrading">If you have been using the old Boost Iterator Adaptor library to | |
178 | implement iterators, you probably wrote a <tt class="docutils literal"><span class="pre">Policies</span></tt> class which | |
179 | captures the core operations of your iterator. In the new library | |
180 | design, you'll move those same core operations into the body of the | |
181 | iterator class itself. If you were writing a family of iterators, | |
182 | you probably wrote a <a class="reference external" href="http://www.boost.org/more/generic_programming.html#type_generator">type generator</a> to build the | |
183 | <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> specialization you needed; in the new library | |
184 | design you don't need a type generator (though may want to keep it | |
185 | around as a compatibility aid for older code) because, due to the | |
186 | use of the Curiously Recurring Template Pattern (CRTP) <a class="citation-reference" href="#cop95" id="id22">[Cop95]</a>, | |
187 | you can now define the iterator class yourself and acquire | |
188 | functionality through inheritance from <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> or | |
189 | <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>. As a result, you also get much finer control | |
190 | over how your iterator works: you can add additional constructors, | |
191 | or even override the iterator functionality provided by the | |
192 | library.</p> | |
193 | <p>If you're looking for the old <tt class="docutils literal"><span class="pre">projection_iterator</span></tt> component, | |
194 | its functionality has been merged into <tt class="docutils literal"><span class="pre">transform_iterator</span></tt>: as | |
195 | long as the function object's <tt class="docutils literal"><span class="pre">result_type</span></tt> (or the <tt class="docutils literal"><span class="pre">Reference</span></tt> | |
196 | template argument, if explicitly specified) is a true reference | |
197 | type, <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> will behave like | |
198 | <tt class="docutils literal"><span class="pre">projection_iterator</span></tt> used to.</p> | |
199 | </div> | |
200 | <div class="section" id="history"> | |
201 | <h1><a class="toc-backref" href="#id30">History</a></h1> | |
202 | <p>In 2000 Dave Abrahams was writing an iterator for a container of | |
203 | pointers, which would access the pointed-to elements when | |
204 | dereferenced. Naturally, being a library writer, he decided to | |
205 | generalize the idea and the Boost Iterator Adaptor library was born. | |
206 | Dave was inspired by some writings of Andrei Alexandrescu and chose a | |
207 | policy based design (though he probably didn't capture Andrei's idea | |
208 | very well - there was only one policy class for all the iterator's | |
209 | orthogonal properties). Soon Jeremy Siek realized he would need the | |
210 | library and they worked together to produce a "Boostified" version, | |
211 | which was reviewed and accepted into the library. They wrote a paper | |
212 | and made several important revisions of the code.</p> | |
213 | <p>Eventually, several shortcomings of the older library began to make | |
214 | the need for a rewrite apparent. Dave and Jeremy started working | |
215 | at the Santa Cruz C++ committee meeting in 2002, and had quickly | |
216 | generated a working prototype. At the urging of Mat Marcus, they | |
217 | decided to use the GenVoca/CRTP pattern approach, and moved the | |
218 | policies into the iterator class itself. Thomas Witt expressed | |
219 | interest and became the voice of strict compile-time checking for | |
220 | the project, adding uses of the SFINAE technique to eliminate false | |
221 | converting constructors and operators from the overload set. He | |
222 | also recognized the need for a separate <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>, and | |
223 | factored it out of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>. Finally, after a | |
224 | near-complete rewrite of the prototype, they came up with the | |
225 | library you see today.</p> | |
226 | <table class="docutils citation" frame="void" id="cop95" rules="none"> | |
227 | <colgroup><col class="label" /><col /></colgroup> | |
228 | <tbody valign="top"> | |
229 | <tr><td class="label"><a class="fn-backref" href="#id22">[Cop95]</a></td><td>[Coplien, 1995] Coplien, J., Curiously Recurring Template | |
230 | Patterns, C++ Report, February 1995, pp. 24-27.</td></tr> | |
231 | </tbody> | |
232 | </table> | |
233 | <!-- LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue | |
234 | LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter | |
235 | LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR | |
236 | LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue | |
237 | LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp | |
238 | LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct | |
239 | LocalWords: TraversalTag typename lvalues DWA Hmm JGS --> | |
240 | </div> | |
241 | </div> | |
242 | <div class="footer"> | |
243 | <hr class="footer" /> | |
244 | <a class="reference external" href="index.rst">View document source</a>. | |
245 | Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. | |
246 | ||
247 | </div> | |
248 | </body> | |
249 | </html> |