1.. Distributed under the Boost 2.. Software License, Version 1.0. (See accompanying 3.. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 4 5+++++++++++++++++++++++++++++++++++++++++++++++++ 6 The Boost.Iterator Library |(logo)|__ 7+++++++++++++++++++++++++++++++++++++++++++++++++ 8 9.. |(logo)| image:: ../../../boost.png 10 :alt: Boost 11 12__ ../../../index.htm 13 14 15------------------------------------- 16 17 18:Authors: David Abrahams, Jeremy Siek, Thomas Witt 19:Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@styleadvisor.com 20:organizations: `Boost Consulting`_, Indiana University `Open Systems 21 Lab`_, `Zephyr Associates, Inc.`_ 22:date: $Date$ 23 24:copyright: Copyright David Abrahams, Jeremy Siek, Thomas Witt 2003. 25 26.. _`Boost Consulting`: http://www.boost-consulting.com 27.. _`Open Systems Lab`: http://www.osl.iu.edu 28.. _`Zephyr Associates, Inc.`: http://www.styleadvisor.com 29 30:Abstract: The Boost Iterator Library contains two parts. The first 31 is a system of concepts_ which extend the C++ standard 32 iterator requirements. The second is a framework of 33 components for building iterators based on these 34 extended concepts and includes several useful iterator 35 adaptors. The extended iterator concepts have been 36 carefully designed so that old-style iterators 37 can fit in the new concepts and so that new-style 38 iterators will be compatible with old-style algorithms, 39 though algorithms may need to be updated if they want to 40 take full advantage of the new-style iterator 41 capabilities. Several components of this library have 42 been accepted into the C++ standard technical report. 43 The components of the Boost Iterator Library replace the 44 older Boost Iterator Adaptor Library. 45 46.. _concepts: http://www.boost.org/more/generic_programming.html#concept 47 48.. contents:: **Table of Contents** 49 50 51------------------------------------- 52 53 54===================== 55 New-Style Iterators 56===================== 57 58The iterator categories defined in C++98 are extremely limiting 59because they bind together two orthogonal concepts: traversal and 60element access. For example, because a random access iterator is 61required to return a reference (and not a proxy) when dereferenced, 62it is impossible to capture the capabilities of 63``vector<bool>::iterator`` using the C++98 categories. This is the 64infamous "``vector<bool>`` is not a container, and its iterators 65aren't random access iterators", debacle about which Herb Sutter 66wrote two papers for the standards comittee (n1185_ and n1211_), 67and a `Guru of the Week`__. New-style iterators go well beyond 68patching up ``vector<bool>``, though: there are lots of other 69iterators already in use which can't be adequately represented by 70the existing concepts. For details about the new iterator 71concepts, see our 72 73.. _n1185: http://www.gotw.ca/publications/N1185.pdf 74.. _n1211: http://www.gotw.ca/publications/N1211.pdf 75__ http://www.gotw.ca/gotw/050.htm 76 77 78 `Standard Proposal For New-Style Iterators`__ (PDF__) 79 80__ new-iter-concepts.html 81__ new-iter-concepts.pdf 82 83============================= 84 Iterator Facade and Adaptor 85============================= 86 87Writing standard-conforming iterators is tricky, but the need comes 88up often. In order to ease the implementation of new iterators, 89the Boost.Iterator library provides the |facade| class template, 90which implements many useful defaults and compile-time checks 91designed to help the iterator author ensure that his iterator is 92correct. 93 94It is also common to define a new iterator that is similar to some 95underlying iterator or iterator-like type, but that modifies some 96aspect of the underlying type's behavior. For that purpose, the 97library supplies the |adaptor| class template, which is specially 98designed to take advantage of as much of the underlying type's 99behavior as possible. 100 101The documentation for these two classes can be found at the following 102web pages: 103 104* |facade|_ (PDF__) 105 106* |adaptor|_ (PDF__) 107 108 109.. |facade| replace:: ``iterator_facade`` 110.. _facade: iterator_facade.html 111__ iterator_facade.pdf 112 113.. |adaptor| replace:: ``iterator_adaptor`` 114.. _adaptor: iterator_adaptor.html 115__ iterator_adaptor.pdf 116 117Both |facade| and |adaptor| as well as many of the `specialized 118adaptors`_ mentioned below have been proposed for standardization; 119see our 120 121 `Standard Proposal For Iterator Facade and Adaptor`__ (PDF__) 122 123for more details. 124 125__ facade-and-adaptor.html 126__ facade-and-adaptor.pdf 127 128====================== 129 Specialized Adaptors 130====================== 131 132The iterator library supplies a useful suite of standard-conforming 133iterator templates based on the Boost `iterator facade and adaptor`_. 134 135* |counting|_ (PDF__): an iterator over a sequence of consecutive values. 136 Implements a "lazy sequence" 137 138* |filter|_ (PDF__): an iterator over the subset of elements of some 139 sequence which satisfy a given predicate 140 141* |function_input|_ (PDF__): an input iterator wrapping a generator (nullary 142 function object); each time the iterator is dereferenced, the function object 143 is called to get the value to return. 144 145* |function_output|_ (PDF__): an output iterator wrapping a unary function 146 object; each time an element is written into the dereferenced 147 iterator, it is passed as a parameter to the function object. 148 149* |generator|_: an input iterator wrapping a generator (nullary 150 function object); each time the iterator is dereferenced, the function object 151 is called to get the value to return. This is an outdated analogue of |function_input|_. 152 153* |indirect|_ (PDF__): an iterator over the objects *pointed-to* by the 154 elements of some sequence. 155 156* |permutation|_ (PDF__): an iterator over the elements of some random-access 157 sequence, rearranged according to some sequence of integer indices. 158 159* |reverse|_ (PDF__): an iterator which traverses the elements of some 160 bidirectional sequence in reverse. Corrects many of the 161 shortcomings of C++98's ``std::reverse_iterator``. 162 163* |shared|_: an iterator over elements of a container whose 164 lifetime is maintained by a |shared_ptr|_ stored in the iterator. 165 166* |transform|_ (PDF__): an iterator over elements which are the result of 167 applying some functional transformation to the elements of an 168 underlying sequence. This component also replaces the old 169 ``projection_iterator_adaptor``. 170 171* |zip|_ (PDF__): an iterator over tuples of the elements at corresponding 172 positions of heterogeneous underlying iterators. 173 174.. |counting| replace:: ``counting_iterator`` 175.. _counting: counting_iterator.html 176__ counting_iterator.pdf 177 178.. |filter| replace:: ``filter_iterator`` 179.. _filter: filter_iterator.html 180__ filter_iterator.pdf 181 182.. |function_input| replace:: ``function_input_iterator`` 183.. _function_input: function_input_iterator.html 184__ function_input_iterator.pdf 185 186.. |function_output| replace:: ``function_output_iterator`` 187.. _function_output: function_output_iterator.html 188__ function_output_iterator.pdf 189 190.. |generator| replace:: ``generator_iterator`` 191.. _generator: generator_iterator.htm 192 193.. |indirect| replace:: ``indirect_iterator`` 194.. _indirect: indirect_iterator.html 195__ indirect_iterator.pdf 196 197.. |permutation| replace:: ``permutation_iterator`` 198.. _permutation: permutation_iterator.html 199__ permutation_iterator.pdf 200 201.. |reverse| replace:: ``reverse_iterator`` 202.. _reverse: reverse_iterator.html 203__ reverse_iterator.pdf 204 205.. |shared| replace:: ``shared_container_iterator`` 206.. _shared: ../../utility/shared_container_iterator.html 207 208.. |transform| replace:: ``transform_iterator`` 209.. _transform: transform_iterator.html 210__ transform_iterator.pdf 211 212.. |zip| replace:: ``zip_iterator`` 213.. _zip: zip_iterator.html 214__ zip_iterator.pdf 215 216.. |shared_ptr| replace:: ``shared_ptr`` 217.. _shared_ptr: ../../smart_ptr/shared_ptr.htm 218 219==================== 220 Iterator Utilities 221==================== 222 223Operations 224---------- 225 226The standard library does not handle new-style iterators properly, 227because it knows nothing about the iterator traversal concepts. 228The Boost.Iterator library provides implementations that fully understand 229the new concepts for the two basic operations: 230 231- |advance|_ 232- |distance|_ 233 234.. |advance| replace:: ``advance`` 235.. _advance: advance.html 236 237.. |distance| replace:: ``distance`` 238.. _distance: distance.html 239 240Traits 241------ 242 243* |pointee|_ (PDF__): Provides the capability to deduce the referent types 244 of pointers, smart pointers and iterators in generic code. Used 245 in |indirect|. 246 247* |iterator_traits|_ (PDF__): Provides MPL_\ -compatible metafunctions which 248 retrieve an iterator's traits. Also corrects for the deficiencies 249 of broken implementations of ``std::iterator_traits``. 250 251.. * |interoperable|_ (PDF__): Provides an MPL_\ -compatible metafunction for 252 testing iterator interoperability 253 254.. |pointee| replace:: ``pointee.hpp`` 255.. _pointee: pointee.html 256__ pointee.pdf 257 258.. |iterator_traits| replace:: ``iterator_traits.hpp`` 259.. _iterator_traits: iterator_traits.html 260__ iterator_traits.pdf 261 262.. |interoperable| replace:: ``interoperable.hpp`` 263.. _interoperable: interoperable.html 264.. comment! __ interoperable.pdf 265 266.. _MPL: ../../mpl/doc/index.html 267 268Testing and Concept Checking 269---------------------------- 270 271* |iterator_concepts|_ (PDF__): Concept checking classes for the new iterator concepts. 272 273* |iterator_archetypes|_ (PDF__): Concept archetype classes for the new iterators concepts. 274 275.. |iterator_concepts| replace:: ``iterator_concepts.hpp`` 276.. _iterator_concepts: iterator_concepts.html 277__ iterator_concepts.pdf 278 279.. |iterator_archetypes| replace:: ``iterator_archetypes.hpp`` 280.. _iterator_archetypes: iterator_archetypes.html 281__ iterator_archetypes.pdf 282 283======================================================= 284 Upgrading from the old Boost Iterator Adaptor Library 285======================================================= 286 287.. _Upgrading: 288 289If you have been using the old Boost Iterator Adaptor library to 290implement iterators, you probably wrote a ``Policies`` class which 291captures the core operations of your iterator. In the new library 292design, you'll move those same core operations into the body of the 293iterator class itself. If you were writing a family of iterators, 294you probably wrote a `type generator`_ to build the 295``iterator_adaptor`` specialization you needed; in the new library 296design you don't need a type generator (though may want to keep it 297around as a compatibility aid for older code) because, due to the 298use of the Curiously Recurring Template Pattern (CRTP) [Cop95]_, 299you can now define the iterator class yourself and acquire 300functionality through inheritance from ``iterator_facade`` or 301``iterator_adaptor``. As a result, you also get much finer control 302over how your iterator works: you can add additional constructors, 303or even override the iterator functionality provided by the 304library. 305 306.. _`type generator`: http://www.boost.org/more/generic_programming.html#type_generator 307 308If you're looking for the old ``projection_iterator`` component, 309its functionality has been merged into ``transform_iterator``: as 310long as the function object's ``result_type`` (or the ``Reference`` 311template argument, if explicitly specified) is a true reference 312type, ``transform_iterator`` will behave like 313``projection_iterator`` used to. 314 315========= 316 History 317========= 318 319In 2000 Dave Abrahams was writing an iterator for a container of 320pointers, which would access the pointed-to elements when 321dereferenced. Naturally, being a library writer, he decided to 322generalize the idea and the Boost Iterator Adaptor library was born. 323Dave was inspired by some writings of Andrei Alexandrescu and chose a 324policy based design (though he probably didn't capture Andrei's idea 325very well - there was only one policy class for all the iterator's 326orthogonal properties). Soon Jeremy Siek realized he would need the 327library and they worked together to produce a "Boostified" version, 328which was reviewed and accepted into the library. They wrote a paper 329and made several important revisions of the code. 330 331Eventually, several shortcomings of the older library began to make 332the need for a rewrite apparent. Dave and Jeremy started working 333at the Santa Cruz C++ committee meeting in 2002, and had quickly 334generated a working prototype. At the urging of Mat Marcus, they 335decided to use the GenVoca/CRTP pattern approach, and moved the 336policies into the iterator class itself. Thomas Witt expressed 337interest and became the voice of strict compile-time checking for 338the project, adding uses of the SFINAE technique to eliminate false 339converting constructors and operators from the overload set. He 340also recognized the need for a separate ``iterator_facade``, and 341factored it out of ``iterator_adaptor``. Finally, after a 342near-complete rewrite of the prototype, they came up with the 343library you see today. 344 345.. [Cop95] [Coplien, 1995] Coplien, J., Curiously Recurring Template 346 Patterns, C++ Report, February 1995, pp. 24-27. 347 348.. 349 LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue 350 LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter 351 LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR 352 LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue 353 LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp 354 LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct 355 LocalWords: TraversalTag typename lvalues DWA Hmm JGS 356
