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, 119and accepted into the first C++ technical report; see 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* |indirect|_ (PDF__): an iterator over the objects *pointed-to* by the 150 elements of some sequence. 151 152* |permutation|_ (PDF__): an iterator over the elements of some random-access 153 sequence, rearranged according to some sequence of integer indices. 154 155* |reverse|_ (PDF__): an iterator which traverses the elements of some 156 bidirectional sequence in reverse. Corrects many of the 157 shortcomings of C++98's ``std::reverse_iterator``. 158 159* |shared|_: an iterator over elements of a container whose 160 lifetime is maintained by a |shared_ptr|_ stored in the iterator. 161 162* |transform|_ (PDF__): an iterator over elements which are the result of 163 applying some functional transformation to the elements of an 164 underlying sequence. This component also replaces the old 165 ``projection_iterator_adaptor``. 166 167* |zip|_ (PDF__): an iterator over tuples of the elements at corresponding 168 positions of heterogeneous underlying iterators. 169 170.. |counting| replace:: ``counting_iterator`` 171.. _counting: counting_iterator.html 172__ counting_iterator.pdf 173 174.. |filter| replace:: ``filter_iterator`` 175.. _filter: filter_iterator.html 176__ filter_iterator.pdf 177 178.. |function_input| replace:: ``function_input_iterator`` 179.. _function_input: function_input_iterator.html 180__ function_input_iterator.pdf 181 182.. |function_output| replace:: ``function_output_iterator`` 183.. _function_output: function_output_iterator.html 184__ function_output_iterator.pdf 185 186.. |indirect| replace:: ``indirect_iterator`` 187.. _indirect: indirect_iterator.html 188__ indirect_iterator.pdf 189 190.. |permutation| replace:: ``permutation_iterator`` 191.. _permutation: permutation_iterator.html 192__ permutation_iterator.pdf 193 194.. |reverse| replace:: ``reverse_iterator`` 195.. _reverse: reverse_iterator.html 196__ reverse_iterator.pdf 197 198.. |shared| replace:: ``shared_container_iterator`` 199.. _shared: ../../utility/shared_container_iterator.html 200 201.. |transform| replace:: ``transform_iterator`` 202.. _transform: transform_iterator.html 203__ transform_iterator.pdf 204 205.. |zip| replace:: ``zip_iterator`` 206.. _zip: zip_iterator.html 207__ zip_iterator.pdf 208 209.. |shared_ptr| replace:: ``shared_ptr`` 210.. _shared_ptr: ../../smart_ptr/shared_ptr.htm 211 212==================== 213 Iterator Utilities 214==================== 215 216Traits 217------ 218 219* |pointee|_ (PDF__): Provides the capability to deduce the referent types 220 of pointers, smart pointers and iterators in generic code. Used 221 in |indirect|. 222 223* |iterator_traits|_ (PDF__): Provides MPL_\ -compatible metafunctions which 224 retrieve an iterator's traits. Also corrects for the deficiencies 225 of broken implementations of ``std::iterator_traits``. 226 227.. * |interoperable|_ (PDF__): Provides an MPL_\ -compatible metafunction for 228 testing iterator interoperability 229 230.. |pointee| replace:: ``pointee.hpp`` 231.. _pointee: pointee.html 232__ pointee.pdf 233 234.. |iterator_traits| replace:: ``iterator_traits.hpp`` 235.. _iterator_traits: iterator_traits.html 236__ iterator_traits.pdf 237 238.. |interoperable| replace:: ``interoperable.hpp`` 239.. _interoperable: interoperable.html 240.. comment! __ interoperable.pdf 241 242.. _MPL: ../../mpl/doc/index.html 243 244Testing and Concept Checking 245---------------------------- 246 247* |iterator_concepts|_ (PDF__): Concept checking classes for the new iterator concepts. 248 249* |iterator_archetypes|_ (PDF__): Concept archetype classes for the new iterators concepts. 250 251.. |iterator_concepts| replace:: ``iterator_concepts.hpp`` 252.. _iterator_concepts: iterator_concepts.html 253__ iterator_concepts.pdf 254 255.. |iterator_archetypes| replace:: ``iterator_archetypes.hpp`` 256.. _iterator_archetypes: iterator_archetypes.html 257__ iterator_archetypes.pdf 258 259======================================================= 260 Upgrading from the old Boost Iterator Adaptor Library 261======================================================= 262 263.. _Upgrading: 264 265If you have been using the old Boost Iterator Adaptor library to 266implement iterators, you probably wrote a ``Policies`` class which 267captures the core operations of your iterator. In the new library 268design, you'll move those same core operations into the body of the 269iterator class itself. If you were writing a family of iterators, 270you probably wrote a `type generator`_ to build the 271``iterator_adaptor`` specialization you needed; in the new library 272design you don't need a type generator (though may want to keep it 273around as a compatibility aid for older code) because, due to the 274use of the Curiously Recurring Template Pattern (CRTP) [Cop95]_, 275you can now define the iterator class yourself and acquire 276functionality through inheritance from ``iterator_facade`` or 277``iterator_adaptor``. As a result, you also get much finer control 278over how your iterator works: you can add additional constructors, 279or even override the iterator functionality provided by the 280library. 281 282.. _`type generator`: http://www.boost.org/more/generic_programming.html#type_generator 283 284If you're looking for the old ``projection_iterator`` component, 285its functionality has been merged into ``transform_iterator``: as 286long as the function object's ``result_type`` (or the ``Reference`` 287template argument, if explicitly specified) is a true reference 288type, ``transform_iterator`` will behave like 289``projection_iterator`` used to. 290 291========= 292 History 293========= 294 295In 2000 Dave Abrahams was writing an iterator for a container of 296pointers, which would access the pointed-to elements when 297dereferenced. Naturally, being a library writer, he decided to 298generalize the idea and the Boost Iterator Adaptor library was born. 299Dave was inspired by some writings of Andrei Alexandrescu and chose a 300policy based design (though he probably didn't capture Andrei's idea 301very well - there was only one policy class for all the iterator's 302orthogonal properties). Soon Jeremy Siek realized he would need the 303library and they worked together to produce a "Boostified" version, 304which was reviewed and accepted into the library. They wrote a paper 305and made several important revisions of the code. 306 307Eventually, several shortcomings of the older library began to make 308the need for a rewrite apparent. Dave and Jeremy started working 309at the Santa Cruz C++ committee meeting in 2002, and had quickly 310generated a working prototype. At the urging of Mat Marcus, they 311decided to use the GenVoca/CRTP pattern approach, and moved the 312policies into the iterator class itself. Thomas Witt expressed 313interest and became the voice of strict compile-time checking for 314the project, adding uses of the SFINAE technique to eliminate false 315converting constructors and operators from the overload set. He 316also recognized the need for a separate ``iterator_facade``, and 317factored it out of ``iterator_adaptor``. Finally, after a 318near-complete rewrite of the prototype, they came up with the 319library you see today. 320 321.. [Cop95] [Coplien, 1995] Coplien, J., Curiously Recurring Template 322 Patterns, C++ Report, February 1995, pp. 24-27. 323 324.. 325 LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue 326 LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter 327 LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR 328 LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue 329 LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp 330 LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct 331 LocalWords: TraversalTag typename lvalues DWA Hmm JGS 332