Squashed 'third_party/boostorg/iterator/' content from commit b2adecb
Change-Id: I284a73816f9cc846742923879275b84c6e0c915c
git-subtree-dir: third_party/boostorg/iterator
git-subtree-split: b2adecb951af025698618f19a3c838bd314966dc
diff --git a/doc/quickbook/iterator.qbk b/doc/quickbook/iterator.qbk
new file mode 100644
index 0000000..6a20e33
--- /dev/null
+++ b/doc/quickbook/iterator.qbk
@@ -0,0 +1,308 @@
+
+[library Boost.Iterator
+ [/ version 1.0.1]
+ [quickbook 1.6]
+ [authors [Abrahams, David], [Siek, Jeremy], [Witt, Thomas]]
+ [copyright 2003 2005 David Abrahams Jeremy Siek Thomas Witt]
+ [category iterator]
+ [id iterator]
+ [dirname iterator]
+ [purpose
+ ]
+ [license
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ <ulink url="http://www.boost.org/LICENSE_1_0.txt">
+ http://www.boost.org/LICENSE_1_0.txt
+ </ulink>)
+ ]
+]
+
+[/ QuickBook Document version 1.0 ]
+
+[/ Images ]
+
+[def _note_ [$images/note.png]]
+[def _alert_ [$images/caution.png]]
+[def _detail_ [$images/note.png]]
+[def _tip_ [$images/tip.png]]
+
+[/ Links ]
+
+[def _iterator_ [@../../../iterator/doc/index.html Boost.Iterator]]
+[def _concept_check_ [@../../../concept_check/index.html Boost.ConceptCheck]]
+
+[template sub[x]'''<subscript>'''[x]'''</subscript>''']
+
+[section:intro Introduction]
+
+[def _concepts_ [@http://www.boost.org/more/generic_programming.html#concept concepts]]
+
+The Boost Iterator Library contains two parts. The first
+is a system of _concepts_ which extend the C++ standard
+iterator requirements. The second is a framework of
+components for building iterators based on these
+extended concepts and includes several useful iterator
+adaptors. The extended iterator concepts have been
+carefully designed so that old-style iterators
+can fit in the new concepts and so that new-style
+iterators will be compatible with old-style algorithms,
+though algorithms may need to be updated if they want to
+take full advantage of the new-style iterator
+capabilities. Several components of this library have
+been accepted into the C++ standard technical report.
+The components of the Boost Iterator Library replace the
+older Boost Iterator Adaptor Library.
+
+
+[h2 New-Style Iterators]
+
+[def _N1185_ [@http://www.gotw.ca/publications/N1185.pdf N1185]]
+[def _N1211_ [@http://www.gotw.ca/publications/N1211.pdf N1211]]
+[def _GOTW_50_ [@http://www.gotw.ca/gotw/050.htm Guru of the Week]]
+
+The iterator categories defined in C++98 are extremely limiting
+because they bind together two orthogonal concepts: traversal and
+element access. For example, because a random access iterator is
+required to return a reference (and not a proxy) when dereferenced,
+it is impossible to capture the capabilities of
+`vector<bool>::iterator` using the C++98 categories. This is the
+infamous "`vector<bool>` is not a container, and its iterators
+aren't random access iterators", debacle about which Herb Sutter
+wrote two papers for the standards comittee (_N1185_ and _N1211_),
+and a _GOTW_50_. New-style iterators go well beyond
+patching up `vector<bool>`, though: there are lots of other
+iterators already in use which can't be adequately represented by
+the existing concepts. For details about the new iterator
+concepts, see our [@../new-iter-concepts.html Standard Proposal for New-Style Iterators].
+
+[h2 Iterator Facade and Adaptor]
+
+[/
+[def _facade_ [link iterator.generic.facade facade]]
+[def _adaptor_ [link iterator.generic.adaptor adaptor]]
+]
+[def _facade_ [@../iterator_facade.html facade]]
+[def _adaptor_ [@../iterator_adaptor.html adaptor]]
+
+Writing standard-conforming iterators is tricky, but the need comes
+up often. In order to ease the implementation of new iterators,
+the Boost.Iterator library provides the _facade_ class template,
+which implements many useful defaults and compile-time checks
+designed to help the iterator author ensure that his iterator is
+correct.
+
+It is also common to define a new iterator that is similar to some
+underlying iterator or iterator-like type, but that modifies some
+aspect of the underlying type's behavior. For that purpose, the
+library supplies the _adaptor_ class template, which is specially
+designed to take advantage of as much of the underlying type's
+behavior as possible.
+
+Both _facade_ and _adaptor_ as well as many of the [link iterator.specialized specialized
+adaptors] mentioned below have been proposed for standardization
+([@../facade-and-adaptor.html Standard Proposal For Iterator Facade and Adaptor]).
+
+[h2 Specialized Adaptors]
+
+The iterator library supplies a useful suite of standard-conforming
+iterator templates based on the Boost [link
+iterator.intro.iterator_facade_and_adaptor iterator facade and adaptor]
+templates.
+
+[def _counting_ [link iterator.specialized.counting `counting_iterator`]]
+[def _filter_ [link iterator.specialized.filter `filter_iterator`]]
+[def _function_input_ [@../function_input_iterator.html `function_input_iterator`]]
+[def _function_output_ [link iterator.specialized.function_output `function_output_iterator`]]
+[def _generator_ [@../generator_iterator.htm `generator_iterator`]]
+[def _indirect_ [link iterator.specialized.indirect `indirect_iterator`]]
+[def _permutation_ [link iterator.specialized.permutation `permutation_iterator`]]
+[def _reverse_ [link iterator.specialized.reverse `reverse_iterator`]]
+[def _shared_ [link iterator.specialized.shared_container `shared_container_iterator`]]
+[def _transform_ [link iterator.specialized.transform `transform_iterator`]]
+[def _zip_ [link iterator.specialized.zip `zip_iterator`]]
+
+[def _shared_ptr_ [@../../smart_ptr/shared_ptr.htm `shared_ptr`]]
+
+* _counting_: an iterator over a sequence of consecutive values.
+ Implements a "lazy sequence"
+
+* _filter_: an iterator over the subset of elements of some
+ sequence which satisfy a given predicate
+
+* _function_input_: an input iterator wrapping a generator (nullary
+ function object); each time the iterator is dereferenced, the function object
+ is called to get the value to return.
+
+* _function_output_: an output iterator wrapping a unary function
+ object; each time an element is written into the dereferenced
+ iterator, it is passed as a parameter to the function object.
+
+* _generator_: an input iterator wrapping a generator (nullary
+ function object); each time the iterator is dereferenced, the function object
+ is called to get the value to return. An outdated analogue of _function_input_.
+
+* _indirect_: an iterator over the objects *pointed-to* by the
+ elements of some sequence.
+
+* _permutation_: an iterator over the elements of some random-access
+ sequence, rearranged according to some sequence of integer indices.
+
+* _reverse_: an iterator which traverses the elements of some
+ bidirectional sequence in reverse. Corrects many of the
+ shortcomings of C++98's `std::reverse_iterator`.
+
+* _shared_: an iterator over elements of a container whose
+ lifetime is maintained by a _shared_ptr_ stored in the iterator.
+
+* _transform_: an iterator over elements which are the result of
+ applying some functional transformation to the elements of an
+ underlying sequence. This component also replaces the old
+ `projection_iterator_adaptor`.
+
+* _zip_: an iterator over tuples of the elements at corresponding
+ positions of heterogeneous underlying iterators.
+
+[h2 Iterator Utilities]
+
+[h3 Traits]
+
+[def _pointee_ [link iterator.utilities.traits `pointee.hpp`]]
+[def _iterator_traits_ [link iterator.utilities.iterator_traits `iterator_traits.hpp`]]
+[def _interoperable_ [@../interoperable.html `interoperable.hpp`]]
+[def _MPL_ [@../../mpl/doc/index.html [*MPL]]]
+
+* _pointee_: Provides the capability to deduce the referent types
+ of pointers, smart pointers and iterators in generic code. Used
+ in _indirect_.
+
+* _iterator_traits_: Provides _MPL_ compatible metafunctions which
+ retrieve an iterator's traits. Also corrects for the deficiencies
+ of broken implementations of `std::iterator_traits`.
+
+[/
+* _interoperable_: Provides an _MPL_ compatible metafunction for
+ testing iterator interoperability
+]
+
+[h3 Testing and Concept Checking]
+
+[def _iterator_concepts_ [link iterator.concepts `iterator_concepts.hpp`]]
+[def _iterator_archetypes_ [link iterator.utilities.archetypes `iterator_archetypes.hpp`]]
+
+* _iterator_concepts_: Concept checking classes for the new iterator concepts.
+
+* _iterator_archetypes_: Concept archetype classes for the new iterators concepts.
+
+[h2 Iterator Algorithms]
+
+The library provides a number of generic algorithms for use with iterators. These
+algorithms take advantage of the new concepts defined by the library to provide
+better performance and functionality.
+
+[def _advance_ [link iterator.algorithms.advance `advance.hpp`]]
+[def _distance_ [link iterator.algorithms.distance `distance.hpp`]]
+[def _next_prior_ [link iterator.algorithms.next_prior `next_prior.hpp`]]
+
+* _advance_: Provides `advance()` function for advancing an iterator a given number
+ of positions forward or backward.
+
+* _distance_: Provides `distance()` function for computing distance between two
+ iterators.
+
+* _next_prior_: Provides `next()` and `prior()` functions for obtaining
+ next and prior iterators to a given iterator. The functions are also compatible
+ with non-iterator types.
+
+[endsect]
+
+[include concepts.qbk]
+
+[section:generic Generic Iterators]
+
+[include facade.qbk]
+
+[include adaptor.qbk]
+
+[endsect]
+
+[include specialized_adaptors.qbk]
+
+[section:utilities Utilities]
+
+[include archetypes.qbk]
+
+[include concept_checking.qbk]
+
+[include iterator_traits.qbk]
+
+[include type_traits.qbk]
+
+[endsect]
+
+[include algorithms.qbk]
+
+[section:upgrading Upgrading from the old Boost Iterator Adaptor Library]
+
+[def _type_generator_ [@http://www.boost.org/more/generic_programming.html#type_generator type generator]]
+
+If you have been using the old Boost Iterator Adaptor library to
+implement iterators, you probably wrote a `Policies` class which
+captures the core operations of your iterator. In the new library
+design, you'll move those same core operations into the body of the
+iterator class itself. If you were writing a family of iterators,
+you probably wrote a _type_generator_ to build the
+`iterator_adaptor` specialization you needed; in the new library
+design you don't need a type generator (though may want to keep it
+around as a compatibility aid for older code) because, due to the
+use of the Curiously Recurring Template Pattern (CRTP) [Cop95]_,
+you can now define the iterator class yourself and acquire
+functionality through inheritance from `iterator_facade` or
+`iterator_adaptor`. As a result, you also get much finer control
+over how your iterator works: you can add additional constructors,
+or even override the iterator functionality provided by the
+library.
+
+
+If you're looking for the old `projection_iterator` component,
+its functionality has been merged into _transform_iterator_: as
+long as the function object's `result_type` (or the `Reference`
+template argument, if explicitly specified) is a true reference
+type, _transform_iterator_ will behave like
+`projection_iterator` used to.
+
+[endsect]
+
+[section:history History]
+
+In 2000 Dave Abrahams was writing an iterator for a container of
+pointers, which would access the pointed-to elements when
+dereferenced. Naturally, being a library writer, he decided to
+generalize the idea and the Boost Iterator Adaptor library was born.
+Dave was inspired by some writings of Andrei Alexandrescu and chose a
+policy based design (though he probably didn't capture Andrei's idea
+very well - there was only one policy class for all the iterator's
+orthogonal properties). Soon Jeremy Siek realized he would need the
+library and they worked together to produce a "Boostified" version,
+which was reviewed and accepted into the library. They wrote a paper
+and made several important revisions of the code.
+
+Eventually, several shortcomings of the older library began to make
+the need for a rewrite apparent. Dave and Jeremy started working
+at the Santa Cruz C++ committee meeting in 2002, and had quickly
+generated a working prototype. At the urging of Mat Marcus, they
+decided to use the GenVoca/CRTP pattern approach, and moved the
+policies into the iterator class itself. Thomas Witt expressed
+interest and became the voice of strict compile-time checking for
+the project, adding uses of the SFINAE technique to eliminate false
+converting constructors and operators from the overload set. He
+also recognized the need for a separate `iterator_facade`, and
+factored it out of `iterator_adaptor`. Finally, after a
+near-complete rewrite of the prototype, they came up with the
+library you see today.
+
+[:\[Coplien, 1995\] Coplien, J., Curiously Recurring Template
+ Patterns, C++ Report, February 1995, pp. 24-27.]
+
+[endsect]
+