ceph/src/boost/libs/iterator/doc/quickbook/iterator.qbk

   1
   2 [library Boost.Iterator
   3     [/ version 1.0.1]
   4     [quickbook 1.6]
   5     [authors [Abrahams, David], [Siek, Jeremy], [Witt, Thomas]]
   6     [copyright 2003 2005 David Abrahams Jeremy Siek Thomas Witt]
   7     [category iterator]
   8     [id iterator]
   9     [dirname iterator]
  10     [purpose
  11     ]
  12     [license
  13         Distributed under the Boost Software License, Version 1.0.
  14         (See accompanying file LICENSE_1_0.txt or copy at
  15         <ulink url="http://www.boost.org/LICENSE_1_0.txt">
  16             http://www.boost.org/LICENSE_1_0.txt
  17         </ulink>)
  18     ]
  19 ]
  20
  21 [/ QuickBook Document version 1.0 ]
  22
  23 [/  Images   ]
  24
  25 [def _note_               [$images/note.png]]
  26 [def _alert_              [$images/caution.png]]
  27 [def _detail_             [$images/note.png]]
  28 [def _tip_                [$images/tip.png]]
  29
  30 [/  Links   ]
  31
  32 [def _iterator_           [@../../libs/iterator/doc/index.html Boost.Iterator]]
  33
  34 [section:intro Introduction]
  35
  36 [def _concepts_ [@http://www.boost.org/more/generic_programming.html#concept concepts]]
  37
  38 The Boost Iterator Library contains two parts. The first
  39 is a system of _concepts_ which extend the C++ standard
  40 iterator requirements. The second is a framework of
  41 components for building iterators based on these
  42 extended concepts and includes several useful iterator
  43 adaptors. The extended iterator concepts have been
  44 carefully designed so that old-style iterators
  45 can fit in the new concepts and so that new-style
  46 iterators will be compatible with old-style algorithms,
  47 though algorithms may need to be updated if they want to
  48 take full advantage of the new-style iterator
  49 capabilities.  Several components of this library have
  50 been accepted into the C++ standard technical report.
  51 The components of the Boost Iterator Library replace the
  52 older Boost Iterator Adaptor Library.
  53
  54
  55 [h2 New-Style Iterators]
  56
  57 [def _N1185_      [@http://www.gotw.ca/publications/N1185.pdf N1185]]
  58 [def _N1211_      [@http://www.gotw.ca/publications/N1211.pdf N1211]]
  59 [def _GOTW_50_    [@http://www.gotw.ca/gotw/050.htm Guru of the Week]]
  60
  61 The iterator categories defined in C++98 are extremely limiting
  62 because they bind together two orthogonal concepts: traversal and
  63 element access.  For example, because a random access iterator is
  64 required to return a reference (and not a proxy) when dereferenced,
  65 it is impossible to capture the capabilities of
  66 `vector<bool>::iterator` using the C++98 categories.  This is the
  67 infamous "`vector<bool>` is not a container, and its iterators
  68 aren't random access iterators", debacle about which Herb Sutter
  69 wrote two papers for the standards comittee (_N1185_ and _N1211_),
  70 and a _GOTW_50_.  New-style iterators go well beyond
  71 patching up `vector<bool>`, though: there are lots of other
  72 iterators already in use which can't be adequately represented by
  73 the existing concepts.  For details about the new iterator
  74 concepts, see our [@./new-iter-concepts.html Standard Proposal for New-Style Iterators].
  75
  76 [h2 Iterator Facade and Adaptor]
  77
  78 [def _facade_ [@./iterator_facade.html facade]]
  79 [def _adaptor_ [@./iterator_adaptor.html adaptor]]
  80
  81 Writing standard-conforming iterators is tricky, but the need comes
  82 up often.  In order to ease the implementation of new iterators,
  83 the Boost.Iterator library provides the _facade_ class template,
  84 which implements many useful defaults and compile-time checks
  85 designed to help the iterator author ensure that his iterator is
  86 correct.
  87
  88 It is also common to define a new iterator that is similar to some
  89 underlying iterator or iterator-like type, but that modifies some
  90 aspect of the underlying type's behavior.  For that purpose, the
  91 library supplies the _adaptor_ class template, which is specially
  92 designed to take advantage of as much of the underlying type's
  93 behavior as possible.
  94
  95 Both _facade_ and _adaptor_ as well as many of the `specialized
  96 adaptors`_ mentioned below have been proposed for standardization
  97 ([@./facade-and-adaptor.html Standard Proposal For Iterator Facade and Adaptor]).
  98
  99 [h2 Specialized Adaptors]
 100
 101 The iterator library supplies a useful suite of standard-conforming
 102 iterator templates based on the Boost [link
 103 iterator.intro.iterator_facade_and_adaptor iterator facade and adaptor]
 104 templates.
 105
 106 [def _counting_    [@./counting_iterator.html         `counting_iterator`]]
 107 [def _filter_      [@./filter_iterator.html           `filter_iterator`]]
 108 [def _function_    [@./function_output_iterator.html  `function_output_iterator`]]
 109 [def _indirect_    [@./indirect_iterator.html         `indirect_iterator`]]
 110 [def _permutation_ [@./permutation_iterator.html      `permutation_iterator`]]
 111 [def _reverse_     [@./reverse_iterator.html          `reverse_iterator`]]
 112 [def _shared_      [@./shared_container_iterator.html `shared_container_iterator`]]
 113 [def _transform_   [@./transform_iterator.html        `transform_iterator`]]
 114 [def _zip_         [@./zip_iterator.html              `zip_iterator`]]
 115
 116 [def _shared_ptr_  [@../../smart_ptr/shared_ptr.htm `shared_ptr`]]
 117
 118 * _counting_: an iterator over a sequence of consecutive values.
 119   Implements a "lazy sequence"
 120
 121 * _filter_: an iterator over the subset of elements of some
 122   sequence which satisfy a given predicate
 123
 124 * _function_: an output iterator wrapping a unary function
 125   object; each time an element is written into the dereferenced
 126   iterator, it is passed as a parameter to the function object.
 127
 128 * _indirect_: an iterator over the objects *pointed-to* by the
 129   elements of some sequence.
 130
 131 * _permutation_: an iterator over the elements of some random-access
 132   sequence, rearranged according to some sequence of integer indices.
 133
 134 * _reverse_: an iterator which traverses the elements of some
 135   bidirectional sequence in reverse.  Corrects many of the
 136   shortcomings of C++98's ``std::reverse_iterator``.
 137
 138 * _shared_: an iterator over elements of a container whose
 139   lifetime is maintained by a _shared_ptr_ stored in the iterator.
 140
 141 * _transform_: an iterator over elements which are the result of
 142   applying some functional transformation to the elements of an
 143   underlying sequence.  This component also replaces the old
 144   ``projection_iterator_adaptor``.
 145
 146 * _zip_: an iterator over tuples of the elements at corresponding
 147   positions of heterogeneous underlying iterators.
 148
 149 [h2 Iterator Utilities]
 150
 151 [h3 Traits]
 152
 153 [def _pointee_          [@./pointee.html         `pointee.hpp`]]
 154 [def _iterator_traits_  [@./iterator_traits.html `iterator_traits.hpp`]]
 155 [def _interoperable_    [@./interoperable.html   `interoperable.hpp`]]
 156 [def _MPL_              [@../../mpl/doc/index.html   [*MPL]]]
 157
 158 * _pointee_: Provides the capability to deduce the referent types
 159   of pointers, smart pointers and iterators in generic code.  Used
 160   in _indirect_.
 161
 162 * _iterator_traits_: Provides _MPL_ compatible metafunctions which
 163   retrieve an iterator's traits.  Also corrects for the deficiencies
 164   of broken implementations of `std::iterator_traits`.
 165
 166 [\ * |interoperable|_ (PDF__): Provides an _MPL_ compatible metafunction for
 167      testing iterator interoperability
 168 ]
 169
 170 [h3 Testing and Concept Checking]
 171
 172 [def _iterator_concepts_  [@./iterator_concepts.html `iterator_concepts.hpp`]]
 173 [def _iterator_archetypes_  [@./iterator_archetypes.html `iterator_archetypes.hpp`]]
 174
 175 * _iterator_concepts_: Concept checking classes for the new iterator concepts.
 176
 177 * _iterator_archetypes_: Concept archetype classes for the new iterators concepts.
 178
 179 [endsect]
 180
 181 [include concepts.qbk]
 182
 183 [section:generic Generic Iterators]
 184
 185 [include facade.qbk]
 186
 187 [include adaptor.qbk]
 188
 189 [endsect]
 190
 191 [include specialized_adaptors.qbk]
 192
 193 [section:utilities Utilities]
 194
 195 [include archetypes.qbk]
 196
 197 [include concept_checking.qbk]
 198
 199 [include traits.qbk]
 200
 201 [include utilities.qbk]
 202
 203 [endsect]
 204
 205 [section:upgrading Upgrading from the old Boost Iterator Adaptor Library]
 206
 207 [def _type_generator_ [@http://www.boost.org/more/generic_programming.html#type_generator type generator]]
 208
 209 If you have been using the old Boost Iterator Adaptor library to
 210 implement iterators, you probably wrote a `Policies` class which
 211 captures the core operations of your iterator.  In the new library
 212 design, you'll move those same core operations into the body of the
 213 iterator class itself.  If you were writing a family of iterators,
 214 you probably wrote a _type_generator_ to build the
 215 `iterator_adaptor` specialization you needed; in the new library
 216 design you don't need a type generator (though may want to keep it
 217 around as a compatibility aid for older code) because, due to the
 218 use of the Curiously Recurring Template Pattern (CRTP) [Cop95]_,
 219 you can now define the iterator class yourself and acquire
 220 functionality through inheritance from `iterator_facade` or
 221 `iterator_adaptor`.  As a result, you also get much finer control
 222 over how your iterator works: you can add additional constructors,
 223 or even override the iterator functionality provided by the
 224 library.
 225
 226
 227 If you're looking for the old `projection_iterator` component,
 228 its functionality has been merged into _transform_iterator_: as
 229 long as the function object's `result_type` (or the `Reference`
 230 template argument, if explicitly specified) is a true reference
 231 type, _transform_iterator_ will behave like
 232 `projection_iterator` used to.
 233
 234 [endsect]
 235
 236 [section:history History]
 237
 238 In 2000 Dave Abrahams was writing an iterator for a container of
 239 pointers, which would access the pointed-to elements when
 240 dereferenced.  Naturally, being a library writer, he decided to
 241 generalize the idea and the Boost Iterator Adaptor library was born.
 242 Dave was inspired by some writings of Andrei Alexandrescu and chose a
 243 policy based design (though he probably didn't capture Andrei's idea
 244 very well - there was only one policy class for all the iterator's
 245 orthogonal properties).  Soon Jeremy Siek realized he would need the
 246 library and they worked together to produce a "Boostified" version,
 247 which was reviewed and accepted into the library.  They wrote a paper
 248 and made several important revisions of the code.
 249
 250 Eventually, several shortcomings of the older library began to make
 251 the need for a rewrite apparent.  Dave and Jeremy started working
 252 at the Santa Cruz C++ committee meeting in 2002, and had quickly
 253 generated a working prototype.  At the urging of Mat Marcus, they
 254 decided to use the GenVoca/CRTP pattern approach, and moved the
 255 policies into the iterator class itself.  Thomas Witt expressed
 256 interest and became the voice of strict compile-time checking for
 257 the project, adding uses of the SFINAE technique to eliminate false
 258 converting constructors and operators from the overload set.  He
 259 also recognized the need for a separate `iterator_facade`, and
 260 factored it out of `iterator_adaptor`.  Finally, after a
 261 near-complete rewrite of the prototype, they came up with the
 262 library you see today.
 263
 264 [:\[Coplien, 1995\] Coplien, J., Curiously Recurring Template
 265    Patterns, C++ Report, February 1995, pp. 24-27.]
 266
 267 [endsect]
 268
 269