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