Boost logo

Boost-Commit :

Date view Thread view Subject view Author view

From: dgregor_at_[hidden]
Date: 2008-08-16 11:49:29

Author: dgregor
Date: 2008-08-16 11:49:29 EDT (Sat, 16 Aug 2008)
New Revision: 48175
URL: http://svn.boost.org/trac/boost/changeset/48175

Log:
Rename iterator concepts proposal file, since we'll probably have a separate proposal for th rest of the iterators chapter
Added:
   sandbox/committee/concepts/stdlib/clib-iterconcepts.tex
      - copied unchanged from r48174, /sandbox/committee/concepts/stdlib/clib-iterators.tex
Removed:
   sandbox/committee/concepts/stdlib/clib-iterators.tex
Text files modified:
   sandbox/committee/concepts/stdlib/Makefile | 3 +--
   1 files changed, 1 insertions(+), 2 deletions(-)

Modified: sandbox/committee/concepts/stdlib/Makefile
==============================================================================
--- sandbox/committee/concepts/stdlib/Makefile (original)
+++ sandbox/committee/concepts/stdlib/Makefile 2008-08-16 11:49:29 EDT (Sat, 16 Aug 2008)
@@ -64,7 +64,7 @@
 # Default rule
 #
 NAMES = clib-intro clib-concepts clib-utilities clib-containers \
- clib-iterators clib-algorithms clib-numerics
+ clib-iterconcepts clib-algorithms clib-numerics
 
 OTHER_TEX = macros.tex
 

Deleted: sandbox/committee/concepts/stdlib/clib-iterators.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-iterators.tex 2008-08-16 11:49:29 EDT (Sat, 16 Aug 2008)
+++ (empty file)
@@ -1,1504 +0,0 @@
-\documentclass[american,twoside]{book}
-\usepackage{refbib}
-\usepackage{pdfsync}
-\input{macros}
-
-%%--------------------------------------------------
-%% PDF
-
-\usepackage[pdftex,
- pdftitle={Iterator Concepts for the C++0x Standard Library},
- pdfsubject={C++ International Standard Proposal},
- pdfcreator={Douglas Gregor},
- bookmarks=true,
- bookmarksnumbered=true,
- pdfpagelabels=true,
- pdfpagemode=UseOutlines,
- pdfstartview=FitH,
- linktocpage=true,
- colorlinks=true,
- linkcolor=blue,
- plainpages=false
- ]{hyperref}
-
-%%--------------------------------------------------
-%% Set section numbering limit, toc limit
-\setcounter{secnumdepth}{5}
-\setcounter{tocdepth}{3}
-
-%%--------------------------------------------------
-%% Parameters that govern document appearance
-\setlength{\oddsidemargin}{0pt}
-\setlength{\evensidemargin}{0pt}
-\setlength{\textwidth}{6.6in}
-
-\newcommand{\resetcolor}{\textcolor{addclr}{}}
-
-%%--------------------------------------------------
-%% Handle special hyphenation rules
-\hyphenation{tem-plate ex-am-ple in-put-it-er-a-tor}
-
-% Do not put blank pages after chapters that end on odd-numbered pages.
-\def\cleardoublepage{\clearpage\if_at_twoside%
- \ifodd\c_at_page\else\hbox{}\thispagestyle{empty}\newpage%
- \if_at_twocolumn\hbox{}\newpage\fi\fi\fi}
-
-\begin{document}
-\raggedbottom
-
-\begin{titlepage}
-\begin{center}
-\huge
-Iterator Concepts for the C++0x Standard Library\\
-(Revision 4)
-\vspace{0.5in}
-
-\normalsize
-Douglas Gregor, Jeremy Siek and Andrew Lumsdaine \\
-\href{mailto:dgregor_at_[hidden]}{dgregor_at_[hidden]}, \href{mailto:jeremy.siek_at_[hidden]}{jeremy.siek_at_[hidden]}, \href{mailto:lums_at_[hidden]}{lums_at_[hidden]}
-\end{center}
-
-\vspace{1in}
-\par\noindent Document number: DRAFT \vspace{-6pt}
-\par\noindent Revises document number: N2695=08-0205 \vspace{-6pt}
-\par\noindent Date: \today\vspace{-6pt}
-\par\noindent Project: Programming Language \Cpp{}, Library Working Group\vspace{-6pt}
-\par\noindent Reply-to: Douglas Gregor $<$\href{mailto:dgregor_at_[hidden]}{dgregor_at_[hidden]}$>$\vspace{-6pt}
-
-\section*{Introduction}
-This document proposes new iterator concepts in the \Cpp0x Standard
-Library. It describes a new header \tcode{<iterator_concepts>} that
-contains these concepts, along with concept maps and
-\tcode{iterator_traits} specializations that provide backward
-compatibility for existing iterators and generic algorithms.
-
-Within the proposed wording, text that has been added
-\textcolor{addclr}{will be presented in blue} \addedConcepts{and
-underlined when possible}. Text that has been removed will be
-presented \textcolor{remclr}{in red},\removedConcepts{with
-strike-through when possible}.
-
-\editorial{Purely editorial comments will be written in a separate,
- shaded box. These comments are not intended to be included in the
- working paper.}
-
-\paragraph*{About the new iterator concept taxonomy}
-At the Library Working Group's request, we sought to determine whether
-we could eliminate the mutable iterator concepts from the iterator
-taxonomy. The observation made in Sophia-Antipolis was that the
-mutable iterator concepts were used very rarely, and in those places
-where they were used, we were able to discern simpler
-requirements. As a result of this investigation, we have eliminated
-the mutable iterator concepts and designed an improved iterator
-taxonomy that better describes the various kinds of iterators usable
-with the C++0x standard library.
-
-The fundamental problem with the mutable iterator concepts is that
-they were initially ill-defined within C++98/03, mentioned only
-casually as iterators for which one could write a value to the result
-of dereferencing an iterator. This requirement was taken to mean a
-\tcode{CopyAssignable} requirement (which works reasonably well for
-C++98/03 forward iterators and above), but that fails in two important
-ways for C++0x:
-
-\begin{itemize}
-\item We can now construct sequences with types that are
- move-assignable but not copy-assignable. If we merely change the
- mutable iterator requirement to \tcode{MoveAssignable}, our
- definition of mutable iterator has changed from C++98/03. Besides,
- even this is incorrect: one can mutate values that aren't even
- move-assignable, e.g., by swapping values or acting on lvalues.
-
-\item As part of improving the iterator concepts, we have intended to
- better support proxy iterators (like the infamous
- \tcode{vector<bool>} iterator, although there exist many more
- important examples of such iterators) throughout the C++0x standard
- library. The simple notion of a copy-assignable value type does not
- match with a proxy reference that supports writing.
-\end{itemize}
-
-Thus, the most important realization is that there are multiple forms
-of mutability used within the C++0x standard library, and that these
-mutations involve both the value type of the iterator (e.g., the type
-actually stored in the container the iterator references) and the
-reference type of the iterator (which may be an lvalue reference,
-rvalue reference, or a proxy class). The new iterator taxonomy
-captures these forms of mutability through two iterator concepts:
-\tcode{OutputIterator} and \tcode{ShuffleIterator}.
-
-The \tcode{OutputIterator} concept (\ref{output.iterators}) is a
-faithful representation of a C++98/03 output iterator. Output
-iterators are an odd kind of iterator, because it does not make sense
-to say that a type \tcode{X} is an output iterator. Rather, one must
-say that \tcode{X} is an output iterator \textit{for a value type
- \tcode{T}}. Moreover, a given type \tcode{X} can be an output
-iterator for a whole family of types, e.g., all types that can be
-printed, and can permit specific parameter-passing conventions. For
-example, \tcode{X} could support writing only rvalues of type
-\tcode{T}, or both lvalues and rvalues of type \tcode{T}. Thus, the
-\tcode{OutputIterator} concept is a two-parameter concept, one
-parameter for \tcode{X} and another for \tcode{T} (called
-\tcode{Value}). This is not new; however, the updated iterator
-taxonomy encodes the parameter-passing convention into the
-\tcode{Value} template parameter, so that the user of the output
-iterator can distinguish between writing lvalues and writing
-rvalues. For example, the \tcode{copy} algorithm provides the
-\tcode{reference} type of the input iterator as the output type of the
-output iterator:
-
-\begin{codeblock}
-template<InputIterator InIter,
- OutputIterator<auto, InIter::reference> OutIter>
- inline OutIter
- copy(InIter first, InIter last, OutIter result)
- {
- for (; first != last; ++result, ++first)
- *result = *first;
- return result;
- }
-\end{codeblock}
-
-With this scheme, a typical input iterator that returns an lvalue
-reference will pass that lvalue reference on to the output iterator
-(as in C++98/03). More interesting, however, is when the input
-iterator is actually a \tcode{move_iterator}, whose reference type is
-an rvalue reference. In this case, we're writing rvalue-references to
-the output iterator, and therefore moving values from the input to the
-output sequence. The use of the \tcode{reference} type as the output
-type for the output iterator also copes with the transfer of values
-via proxies.
-
-We have already noted that a single type \tcode{X} can be an output
-iterator for multiple, different value types. However, further study
-of the standard library algorithms illustrates that a type parameter
-might meet the \tcode{OutputIterator} requirements in multiple ways
-\textit{within a single algorithm}. For example, in the
-\tcode{replace_copy} algorithm the \tcode{OutIter} parameter acts as
-an output iterator for both the input iterator's reference type
-(allowing moves rather than copies) and the type of the replacement
-value:
-
-\begin{codeblock}
-template<InputIterator InIter, typename OutIter, typename _Tp>
- requires OutputIterator<OutIter, InIter::reference>
- && OutputIterator<OutIter, const _Tp&>
- && HasEqualTo<InIter::value_type, _Tp>
- OutIter
- replace_copy(InIter first, InIter last,
- OutIter result,
- const _Tp& old_value, const _Tp& new_value)
- {
- for ( ; first != last; ++first, ++result)
- if (*first == old_value)
- *result = new_value;
- else
- *result = *first;
- return result;
- }
-\end{codeblock}
-
-
-This formulation of \tcode{replace_copy} uncovered an interesting
-issue. Since both of the \tcode{OutputIterator} requirements have
-different argument types, each contains dereference
-(\tcode{operator*}) and increment (\tcode{operator+})
-operators. Through concept maps, it is conceivable (however unlikely)
-that these operators could be different for one requirement than the
-other, and therefore each use of \tcode{*} or \tcode{++} that applies
-to an instance of the \tcode{OutIter} type within \tcode{replace_copy}
-returns an ambiguity. The ambiguity is a result of incomplete concept
-analysis, and was solved by refactoring the requirements of
-\tcode{OutputIterator} into two concepts: \tcode{Iterator<X>}, which
-provides the syntax of \tcode{operator*} and \tcode{operator++} (and
-is also refined by the \tcode{InputIterator<X>} concept), and the
-\tcode{OutputIterator<X, Value>} concept, which adds assignability
-requirements from \tcode{Value} to the reference type of the output
-iterator. Thus, the requirements on \tcode{replace_copy} now say that
-there is only one \tcode{operator*}, but the reference type that it
-returns can be used in multiple, different ways. Moreover, we now have
-an actual root to our iterator hierarchy, the \tcode{Iterator<X>}
-concept, which provides only increment and dereference---the basics of
-moving through a sequence of values---but does not provide any read or
-write capabilities.
-
-The \tcode{ShuffleIterator} concept (\ref{shuffle.iterators}) is a new
-kind of iterator that captures the requirements needed to shuffle
-values within a sequence using moves and
-swaps. \tcode{ShuffleIterator} allows one to
-move-construct or move-assign from an element in the sequence into a
-variable of the iterator's value type. This permits, for example, the
-pivot element in a quicksort to be extracted from the sequence and
-placed into a variable. Additionally, values can be move-assigned from a
-variable of the iterator's value type (e.g., moving the pivot back
-from the temporary into the sorted sequence at the right time). This
-concept is the proxy-aware conceptualization of the
-Swappable+MoveConstructible+MoveAssignable set of concepts from the
-reflector discussion starting with c++std-lib-21212. The
-\tcode{ShuffleIterator} concept is used sparingly, in those cases
-where the sequence cannot be efficiently reordered within simple swap
-operations.
-
-Changes to the iterator taxonomy should not be taken lightly; even the
-apparently simple iterators in C++98/03 turned out to be surprisingly
-complicated, and have resulted in numerous defect reports and several
-attempts at revisions. C++0x iterators are decidedly more complex, due
-to the introduction of rvalue references and the desire to provide
-support for proxy iterators throughout the standard library. To verify
-the iterator concepts presented in this document, we have fully
-implemented these concepts in ConceptGCC, applied them to nearly every
-algorithm in the standard library, and tested the result against the
-full libstdc++ test suite to ensure backward compatibility with
-existing iterators. Indeed, many of the observations that drove this
-refactoring came from implementation experience: the \tcode{operator*}
-ambiguity, for example, was initially detected by ConceptGCC.
-
-\paragraph*{Changes from N2695}
-\begin{itemize}
-\item Replaced the \tcode{HasStdMove} concept (and its uses) with
- \tcode{RvalueOf}, which is now part of the foundational concepts.
-\item In the \tcode{ShuffleIterator} concept, the
- \tcode{HasConstructor} requirement on the \tcode{value_type} has
- been replaced with the equivalent \tcode{Constructible} requirement;
- the explicit \tcode{NothrowDestructible} requirement has
- subsequently been removed.
-\item Added move-constructibility of the value type into the
- \tcode{ShuffleIterator} concept.
-\item We permit the \tcode{iterator_traits} typedefs for output
- iterators to be \tcode{void}. This behavior is permitted by
- \Cpp{}03, and was previously thought to cause problems with the
- backward-compatibility concept maps for output iterators (which
- relied on non-\tcode{void} typedefs even for output
- iterators). However, we determined that the concepts mechanism can
- deduce these types for output iterators, therefore ignoring the
- types specified in \tcode{iterator_traits} and allowing us to
- re-instate this user leeway. In [iterator.backward]p2, we clarify
- that we perform this deduction for output iterators.
-\end{itemize}
-
-
-\end{titlepage}
-
-\section*{Proposed Wording}
-
-%% --------------------------------------------------
-%% Headers and footers
-\pagestyle{fancy}
-\fancyhead[LE,RO]{\textbf{\rightmark}}
-\fancyhead[RE]{\textbf{\leftmark\hspace{1em}\thepage}}
-\fancyhead[LO]{\textbf{\thepage\hspace{1em}\leftmark}}
-\fancyfoot[C]{Draft}
-
-\fancypagestyle{plain}{
-\renewcommand{\headrulewidth}{0in}
-\fancyhead[LE,RO]{}
-\fancyhead[RE,LO]{}
-\fancyfoot{}
-}
-
-\renewcommand{\sectionmark}[1]{\markright{\thesection\hspace{1em}#1}}
-\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
-
-\setcounter{chapter}{23}
-\rSec0[iterators]{Iterators library}
-
-\begin{paras}
-
-\setcounter{Paras}{1}
-
-\textcolor{black}{\pnum}
-The following subclauses describe
-iterator \changedConcepts{requirements}{concepts}, and
-components for
-iterator primitives,
-predefined iterators,
-and stream iterators,
-as summarized in Table~\ref{tab:iterators.lib.summary}.
-
-\begin{libsumtab}{Iterators library summary}{tab:iterators.lib.summary}
-\ref{iterator.concepts} \changedConcepts{Requirements}{Concepts} & \addedConcepts{\tt <iterator_concepts>} \\ \rowsep
-\ref{depr.lib.iterator.primitives} Iterator primitives & \tcode{<iterator>} \\
-\ref{predef.iterators} Predefined iterators & \\
-\ref{stream.iterators} Stream iterators & \\
-\end{libsumtab}
-
-\editorial{The following section has been renamed from ``Iterator requirements'' to ``Iterator concepts''.}
-\rSec1[iterator.concepts]{Iterator concepts}
-
-\pnum
-\addedConcepts{The \mbox{\tcode{<iterator_concepts>}} header describes requirements on iterators.}
-
-\color{addclr}
-\synopsis{Header \tcode{<iterator_concepts>}\ synopsis}
-\begin{codeblock}
-namespace std {
- concept Iterator<typename X> @\textit{see below}@;
-
- // \ref{input.iterators}, input iterators:
- concept InputIterator<typename X> @\textit{see below}@;
-
- // \ref{output.iterators}, output iterators:
- auto concept OutputIterator<typename X, typename Value> @\textit{see below}@;
-
- // \ref{forward.iterators}, forward iterators:
- concept ForwardIterator<typename X> @\textit{see below}@;
-
- @\textcolor{addclr}{}@// \ref{bidirectional.iterators}, bidirectional iterators:
- concept BidirectionalIterator<typename X> @\textit{see below}@;
-
- // \ref{random.access.iterators}, random access iterators:
- concept RandomAccessIterator<typename X> @\textit{see below}@;
- template<ObjectType T> concept_map RandomAccessIterator<T*> @\textit{see below}@;
- template<ObjectType T> concept_map RandomAccessIterator<const T*> @\textit{see below}@;
-
- @\addedConcepts{// \mbox{\ref{shuffle.iterators}}, shuffle iterators:}@
- auto concept ShuffleIterator<typename X> @\textit{see below}@;
-}
-\end{codeblock}
-\color{black}
-
-\pnum
-\index{requirements!iterator}%
-Iterators are a generalization of pointers that allow a \Cpp\ program to work with different data structures
-(containers) in a uniform manner.
-To be able to construct template algorithms that work correctly and
-efficiently on different types of data structures, the library formalizes not just the interfaces but also the
-semantics and complexity assumptions of iterators.
-\addedConcepts{All iterators meet the requirements of the
- \mbox{\tcode{Iterator}} concept.}
-All input iterators
-\tcode{i}\
-support the expression
-\tcode{*i},
-resulting in a value of some class, enumeration, or built-in type
-\tcode{T},
-called the
-\techterm{value type}\
-of the iterator.
-All output iterators support the expression
-\tcode{*i = o}\
-where
-\tcode{o}\
-is a value of some type that is in the set of types that are
-\techterm{writable}\
-to the particular iterator type of
-\tcode{i}.
-All iterators
-\tcode{i}\
-for which the expression
-\tcode{(*i).m}\
-is well-defined, support the expression
-\tcode{i->m}\
-with the same semantics as
-\tcode{(*i).m}.
-For every iterator type
-\tcode{X}\
-for which
-equality is defined, there is a corresponding signed integral type called the
-\techterm{difference type}\
-of the iterator.
-
-\pnum
-Since iterators are an abstraction of pointers, their semantics is
-a generalization of most of the semantics of pointers in \Cpp.
-This ensures that every
-function template
-that takes iterators
-works as well with regular pointers.
-This International Standard defines
-\changedConcepts{five categories of iterators}{several iterator concepts}, according to the operations
-defined on them:
-\techterm{input iterators},
-\techterm{output iterators},
-\techterm{forward iterators},
-\techterm{bidirectional iterators}, \removedConcepts{and}
-\techterm{random access iterators}\addedConcepts{,}
-\addedConcepts{and shuffle iterators},
-as shown in Table~\ref{tab:iterators.relations}.
-
-\begin{floattable}{Relations among iterator \changedConcepts{categories}{concepts}}{tab:iterators.relations}
-{ccccc}
-\topline
-\textbf{Random Access} & $\rightarrow$ \textbf{Bidirectional} &
-$\rightarrow$ \textbf{Forward} & $\rightarrow$ \textbf{Input} & \addedConcepts{\mbox{$\rightarrow$} \mbox{\textbf{Iterator}}} \\
- & & & \addedConcepts{\mbox{$\uparrow$}} & \addedConcepts{\mbox{$\uparrow$}} \\
- & & & \addedConcepts{\mbox{\textbf{Shuffle}}} & \addedConcepts{\mbox{$\rightarrow$}} \textbf{Output} \\
-\end{floattable}
-
-\pnum
-Forward iterators satisfy all the requirements of the input
-\removedConcepts{and output} iterators and can be used whenever
-\changedConcepts{either kind}{an input iterator} is specified.
-Bidirectional iterators also satisfy all the requirements of the
-forward iterators and can be used whenever a forward iterator is specified.
-Random access iterators also satisfy all the requirements of bidirectional
-iterators and can be used whenever a bidirectional iterator is specified.
-
-\pnum
-\changedConcepts{
-Besides its category, a forward, bidirectional, or random access iterator
-can also be
-mutable
-or
-constant
-depending on
-whether the result of the expression
-*i
-behaves as a reference or as a reference to a constant.
-Constant iterators do not satisfy the requirements for output iterators,
-and the result of the expression
-*i
-(for constant iterator
-i)
-cannot be used in an expression where an lvalue is required.}{
-Iterators that meet the requirements of the
-\mbox{\tcode{OutputIterator}} concept are called mutable
-iterators. Non-mutable iterators are referred to as constant
-iterators.}
-
-\pnum
-\resetcolor{}Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element
-of the array, so \textcolor{black}{}for any iterator type there is an iterator value that points past the last element of a
-corresponding container.
-These values are called
-\techterm{past-the-end}\
-values.
-Values of an iterator
-\tcode{i}\
-for which the expression
-\tcode{*i}\
-is defined are called
-\techterm{dereferenceable}.
-The library never assumes that past-the-end values are dereferenceable.
-Iterators can also have singular values that are not associated with any
-container.
-\enterexample\
-After the declaration of an uninitialized pointer
-\tcode{x}\
-(as with
-\tcode{int* x;}),
-\tcode{x}\
-must always be assumed to have a singular value of a pointer.
-\exitexample\
-Results of most expressions are undefined for singular values;
-the only exceptions are destroying an iterator that holds a singular value
-and the assignment of a non-singular value to
-an iterator that holds a singular value.
-In this case the singular
-value is overwritten the same way as any other value.
-Dereferenceable
-values are always non-singular.
-
-\pnum
-An iterator
-\tcode{j}\
-is called
-\techterm{reachable}\
-from an iterator
-\tcode{i}\
-if and only if there is a finite sequence of applications of
-the expression
-\tcode{++i}\
-that makes
-\tcode{i == j}.
-If
-\tcode{j}\
-is reachable from
-\tcode{i},
-they refer to the same container.
-
-\pnum
-Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges.
-A
-\techterm{range}\
-is a pair of iterators that designate the beginning and end of the computation.
-A range \range{i}{i}\
-is an empty range;
-in general, a range \range{i}{j}\
-refers to the elements in the data structure starting with the one
-pointed to by
-\tcode{i}\
-and up to but not including the one pointed to by
-\tcode{j}.
-Range \range{i}{j}\
-is valid if and only if
-\tcode{j}\
-is reachable from
-\tcode{i}.
-The result of the application of functions in the library to invalid ranges is
-undefined.
-
-\pnum
-All the \changedConcepts{categories of iterators}{iterator concepts} require only those functions that are realizable \removedConcepts{for a given category} in
-constant time (amortized).
-\removedConcepts{Therefore, requirement tables for the iterators do not have a complexity column.}
-
-\pnum
-Destruction of an iterator may invalidate pointers and references
-previously obtained from that iterator.
-
-\pnum
-An
-\techterm{invalid}\
-iterator is an iterator that may be singular.%
-\footnote{This definition applies to pointers, since pointers are iterators.
-The effect of dereferencing an iterator that has been invalidated
-is undefined.
-}
-
-\pnum
-\removedConcepts{
-In the following sections,
-a
-and
-b
-denote values of type
-const X,
-n
-denotes a value of the difference type
-Distance,
-u,
-tmp,
-and
-m
-denote identifiers,
-r
-denotes a value of
-X\&,
-t
-denotes a value of value type
-T,
-o
-denotes a value of some type that is writable to the output iterator.}
-
-\color{ccadd}
-\begin{codeblock}
-concept Iterator<typename X> : Semiregular<X> {
- MoveConstructible reference = typename X::reference;
- MoveConstructible postincrement_result;
-
- requires HasDereference<postincrement_result>;
-
- reference operator*(X&&);
- X& operator++(X&);
- postincrement_result operator++(X&, int);
-}
-\end{codeblock}
-\color{black}
-
-\pnum
-\addedConcepts{The \mbox{\tcode{Iterator}} concept forms the basis of the
- iterator concept taxonomy, and every iterator meets the requirements
- of the \mbox{\tcode{Iterator}} concept. This concept specifies
- operations for dereferencing and incrementing the iterator, but
- provides no way to manipulate values. Most
- algorithms will require addition operations to read
- (\mbox{\ref{input.iterators}}) or write
- (\mbox{\ref{output.iterators}}) values, or to provide a richer set
- of iterator movements (\mbox{\ref{forward.iterators}},
- \mbox{\ref{bidirectional.iterators}},
- \mbox{\ref{random.access.iterators}}).}
-
-\editorial{Of particular interest in this concept is the dereference
- operator, which accepts an rvalue reference to an iterator. This
- permits non-\tcode{const} lvalues and rvalues of iterators to be
- dereferenced, but it represents a minor break from C++98/03 where
- one could dereference a const iterator (not an iterator-to-const;
- those are unaffected). We expect the impact to be minimal, given
- that one cannot increment const iterators, and if there were an
- algorithm that dereferences a const iterator, it could just make a
- non-const copy of the iterator to dereference. We have verified this
- change with ConceptGCC and found no ill effects.}
-
-\begin{itemdecl}
-postincrement_result operator++(X& r, int);
-\end{itemdecl}
-
-\pnum
-\effects\
-equivalent to \mbox{\tcode{\{ X tmp = r; ++r; return tmp; \}}}.
-
-\rSec2[input.iterators]{Input iterators}
-
-\pnum
-A class or a built-in type
-\tcode{X}\
-satisfies the requirements of an input iterator for the value type
-\tcode{T}\
-if \changedConcepts{the following expressions are valid,
-where
-U
-is the type of any specified member of type
-T,
-as shown in Table~95.}{it meets the syntactic and semantic
-requirements of the }\addedConcepts{\tt InputIterator}\addedConcepts{ concept.}
-
-\color{addclr}
-\begin{codeblock}
-concept InputIterator<typename X> : Iterator<X>, EqualityComparable<X> {
- ObjectType value_type = typename X::value_type;
- MoveConstructible pointer = typename X::pointer;
-
- SignedIntegralLike difference_type = typename X::difference_type;
-
- requires IntegralType<difference_type>
- && Convertible<reference, const value_type &>;
- @\textcolor{addclr}{}@&& Convertible<pointer, const value_type*>;
-
- requires Convertible<HasDereference<postincrement_result>::result_type, const value_type&>;
-
- pointer operator->(const X&);
-}
-\end{codeblock}
-\color{black}
-
-\pnum
-\changedConcepts{In Table~95}{In the }\addedConcepts{\tt
- InputIterator}\addedConcepts{ concept}, the term
-\techterm{the domain of \tcode{==}}\
-is used in the ordinary mathematical sense to denote
-the set of values over which
-\tcode{==}\ is (required to be) defined.
-This set can change over time.
-Each algorithm places additional requirements on the domain of
-\tcode{==}\ for the iterator values it uses.
-These requirements can be inferred from the uses that algorithm
-makes of \tcode{==}\ and \tcode{!=}.
-\enterexample
-the call \tcode{find(a,b,x)}\
-is defined only if the value of \tcode{a}\
-has the property \textit{p}\
-defined as follows:
-\tcode{b}\ has property \textit{p}\
-and a value \tcode{i}\
-has property \textit{p}\
-if
-\tcode{(*i==x)}\
-or if
-\tcode{(*i!=x}\
-and
-\tcode{++i}\
-has property
-\tcode{p}).
-\exitexample\
-
-\eremove{Remove Table 96: Input iterator requirements}
-
-\pnum
-\enternote\
-For input iterators,
-\tcode{a == b}\
-does not imply
-\tcode{++a == ++b}.
-(Equality does not guarantee the substitution property or referential transparency.)
-Algorithms on input iterators should never attempt to pass through the same iterator twice.
-\resetcolor{}They should be
-\techterm{single pass}\
-algorithms.
-\removedConcepts{Value type T is not required to be an Assignable type (23.1).}\
-These algorithms can be used with istreams as the source of the input data through the
-\tcode{istream_iterator}\
-class.
-\exitnote\
-
-\color{addclr}
-\begin{itemdecl}
-reference operator*(X&& @\farg{a}@); // inherited from Iterator<X>
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\requires}
-\mbox{\tcode{\farg{a}}}
-is dereferenceable.}
-
-\pnum
-\addedConcepts{\mbox{\returns}
-the value referenced by the iterator}
-
-\pnum
-\addedConcepts{\mbox{\notes}
-If \mbox{\tcode{b}} is a value of type \mbox{\tcode{X}},
-\mbox{\tcode{a == b}} and
-\mbox{\tcode{(a, b)}} is in the domain of \mbox{\tcode{==}}
-then \mbox{\tcode{*a}} is equivalent to \mbox{\tcode{*b}}.}
-
-\begin{itemdecl}
-pointer operator->(const X& a);
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\returns}
- a pointer to the value referenced by
- the iterator}
-
-\begin{itemdecl}
-bool operator==(const X& a, const X& b); // inherited from EqualityComparable<X>
-\end{itemdecl}
-
-\pnum
-\addedConcepts{If two iterators \mbox{\tcode{a}} and \mbox{\tcode{b}}
- of the same type are equal, then either \mbox{\tcode{a}} and
- \mbox{\tcode{b}}
-are both dereferenceable
-or else neither is dereferenceable.}
-
-\begin{itemdecl}
-X& operator++(X& r);
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\precondition}
-\mbox{\tcode{r}} is dereferenceable}
-
-\pnum
-\addedConcepts{\mbox{\postcondition}
-\mbox{\tcode{r}} is dereferenceable or \mbox{\tcode{r}} is
-past-the-end. Any copies
-of the previous value of \mbox{\tcode{r}} are no longer required either to be
-dereferenceable or in the domain of \mbox{\tcode{==}}.}
-\end{paras}
-
-\rSec2[output.iterators]{Output iterators}
-
-\pnum
-A class or a built-in type
-\tcode{X}\
-satisfies the requirements of an output iterator
-if
-\changedConcepts{X
-is a CopyConstructible (20.1.3)
-and Assignable type (23.1) and also
-the following expressions are
-valid, as shown in Table~96}{meets the syntactic and semantic requirements of the \mbox{\tcode{OutputIterator}} concept.}
-
-\eremove{Remove Table 97: Output iterator requirements}
-
-\pnum
-\enternote\
-The only valid use of an
-\tcode{operator*}\
-is on the left side of the assignment statement.
-\textit{Assignment through the same value of the iterator happens only once.}\
-Algorithms on output iterators should never attempt to pass through the same iterator twice.
-They should be
-\techterm{single pass}\
-algorithms.
-Equality and inequality might not be defined.
-Algorithms that take output iterators can be used with ostreams as the destination
-for placing data through the
-\tcode{ostream_iterator}\
-class as well as with insert iterators and insert pointers.
-\exitnote\
-
-\pnum
-The \tcode{OutputIterator} concept describes an output iterator that
-may permit output of many different value types.
-
-\color{addclr}
-\begin{itemdecl}
-auto concept OutputIterator<typename X, typename Value> {
- requires Iterator<X>;
-
- typename reference = Iterator<X>::reference;
- typename postincrement_result = Iterator<X>::postincrement_result;
- requires SameType<reference, Iterator<X>::reference>
- && SameType<postincrement_result, Iterator<X>::postincrement_result>
- && Convertible<postincrement_result, const X&>
- && HasAssign<reference, Value>
- && HasAssign<HasDereference<postincrement_result>::result_type, Value>;
-}
-\end{itemdecl}
-\color{black}
-
-\pnum
-\addedConcepts{\enternote\ Any iterator that meets the additional requirements
- specified by \mbox{\tcode{OutputIterator}} for a given
- \mbox{\tcode{Value}} type is considered an output iterator. \exitnote}
-
-\color{addclr}
-\begin{itemdecl}
-X& operator++(X& r); // from Iterator<X>
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\postcondition}
-\mbox{\tcode{\&\farg{r} == \&++\farg{r}}}}
-
-\color{black}
-
-\rSec2[forward.iterators]{Forward iterators}
-
-\pnum
-A class or a built-in type
-\tcode{X}\
-satisfies the requirements of a forward iterator if
-\changedConcepts{the following expressions are
-valid, as shown in Table~97.}{it meets the syntactic and semantic
-requirements of the ForwardIterator concept.}
-
-\eremove{Remove Table 98: Forward iterator requirements.}
-
-\color{addclr}
-\begin{itemdecl}
-concept ForwardIterator<typename X> : InputIterator<X>, Regular<X> {
- requires Convertible<postincrement_result, const X&>;
-
- axiom MultiPass(X a, X b) {
- if (a == b) *a == *b;
- if (a == b) ++a == ++b;
- }
-}
-\end{itemdecl}
-\color{black}
-
-\editorial{The \tcode{ForwardIterator} concept here provides weaker
- requirements on the \tcode{reference} and \tcode{pointer} types than
- the associated requirements table in C++03, because these types do
- not need to be true references or pointers to
- \tcode{value_type}. This change weakens the concept, meaning that
- C++03 iterators (which meet the stronger requirements) still meet
- these requirements, but algorithms that relied on these stricter
- requirements will no longer work just with the iterator
- requirements: they will need to specify true references or pointers
- as additional requirements. By weakening the requirements, however,
- we permit proxy iterators to model the forward, bidirectional, and
- random access iterator concepts.}
-
-\begin{itemdecl}
-X::X(); // inherited from Regular<X>
-\end{itemdecl}
-
-\begin{itemdescr}
- \pnum \addedConcepts{\mbox{\reallynote} the constructed object might have
- a singular value.}
-\end{itemdescr}
-
-\textcolor{black}{}\pnum
-\enternote\
-The \changedConcepts{condition}{axiom} that
-\tcode{a == b}\
-implies
-\tcode{++a == ++b}\
-(which is not true for input and output iterators)
-and the removal of the restrictions on the number of the assignments through the iterator
-(which applies to output iterators)
-allows the use of multi-pass one-directional algorithms with forward iterators.
-\exitnote\
-
-\begin{itemdecl}
-X& operator++(X& r); // inherited from InputIterator<X>
-\end{itemdecl}
-
-\begin{itemdescr}
-\pnum
-\addedConcepts{\mbox{\postcondition} \mbox{\tcode{\&r == \&++r}}.}
-\end{itemdescr}
-
-\rSec2[bidirectional.iterators]{Bidirectional iterators}
-
-\pnum
-A class or a built-in type
-\tcode{X}\
-satisfies the requirements of a bidirectional iterator if
-\changedConcepts{,
-in addition to satisfying the requirements for forward iterators,
-the following expressions are valid as shown in
-Table~98.}{it meets the
-syntactic and semantic requirements of the
-BidirectionalIterator concept.}
-
-\eremove{Remove Table 99: Bidirectional iterator requirements.}
-
-\color{addclr}
-\begin{itemdecl}
-concept BidirectionalIterator<typename X> : ForwardIterator<X> {
- MoveConstructible postdecrement_result;
- requires HasDereference<postdecrement_result>
- && Convertible<HasDereference<postdecrement_result>::result_type, const value_type&>
- && Convertible<postdecrement_result, const X&>;
-
- X& operator--(X&);
- postdecrement_result operator--(X&, int);
-
- axiom BackwardTraversal(X a, X b) {
- --(++a) == a;
- if (--a == --b) a == b;
- }
-}
-\end{itemdecl}
-\color{black}
-
-\pnum
-\enternote\
-Bidirectional iterators allow algorithms to move iterators backward as well as forward.
-\exitnote\
-
-\color{addclr}
-\begin{itemdecl}
-X& operator--(X& r);
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\precondition}
-there exists \mbox{\tcode{s}} such that \mbox{\tcode{r == ++s}}.}
-
-\pnum
-\addedConcepts{\mbox{\postcondition}
-\mbox{\tcode{r}} is dereferenceable.}
-\addedConcepts{\mbox{\tcode{\&r == \&{-}{-}r}}.}
-
-\begin{itemdecl}
-postdecrement_result operator--(X& r, int);
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\effects}
-equivalent to}
-\begin{codeblock}
-{ X tmp = r;
---r;
-return tmp; }
-\end{codeblock}
-\color{black}
-
-\rSec2[random.access.iterators]{Random access iterators}
-
-\pnum
-A class or a built-in type
-\tcode{X}\
-satisfies the requirements of a random access iterator if
-\changedConcepts{,
-in addition to satisfying the requirements for bidirectional iterators,
-the following expressions are valid as shown in Table~99.}
-{it meets the syntactic and semantic requirements of the
-\mbox{\tcode{RandomAccessIterator}} concept.}
-
-\color{addclr}
-\begin{itemdecl}
-concept RandomAccessIterator<typename X> : BidirectionalIterator<X>, LessThanComparable<X> {
- X& operator+=(X&, difference_type);
- X operator+ (const X& x, difference_type n) { X tmp(x); x += n; return x; }
- X operator+ (difference_type n, const X& x) { X tmp(x); x += n; return x; }
- X& operator-=(X&, difference_type);
- X operator- (const X& x, difference_type n) { X tmp(x); x -= n; return x; }
-
- difference_type operator-(const X&, const X&);
- reference operator[](const X& x, difference_type n) { return *(x + n); }
-}
-\end{itemdecl}
-\color{black}
-
-\eremove{Remove Table 100: Random access iterator requirements.}
-
-\color{addclr}
-\begin{itemdecl}
-X& operator+=(X& r, difference_type n);
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\effects}
-equivalent to}
-\begin{codeblock}
-{ difference_type m = n;
- if (m >= 0) while (m--) ++r;
- else while (m++) --r;
- return r; }
-\end{codeblock}
-
-\begin{itemdecl}
-X operator+(const X& a, difference_type n);
-X operator+(difference_type n, const X& a);
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\effects}
-equivalent to}
-\begin{codeblock}
-{ X tmp = a;
-return tmp += n; }
-\end{codeblock}
-
-\pnum
-\addedConcepts{\mbox{\postcondition}
-\mbox{\tcode{a + n == n + a}}}
-
-\begin{itemdecl}
-@\textcolor{addclr}{X}@& operator-=(X& r, difference_type n);
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\returns}
-\mbox{\tcode{r += -n}}}
-
-\begin{itemdecl}
-X operator-(const X& a, difference_type n);
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\effects}
-equivalent to}
-\begin{codeblock}
-{ X tmp = a;
- return tmp -= n; }
-\end{codeblock}
-
-\begin{itemdecl}
-difference_type operator-(const X& a, const X& b);
-\end{itemdecl}
-
-\pnum
-\addedConcepts{\mbox{\precondition}
-there exists a value \mbox{\tcode{n}} of \mbox{\tcode{difference_type}}
- such that \mbox{\tcode{a + n == b}}.}
-
-\pnum
-\addedConcepts{\mbox{\effects}
-\mbox{\tcode{b == a + (b - a)}}}
-
-\pnum
-\addedConcepts{\mbox{\returns}
-\mbox{\tcode{(a < b) ? distance(a,b) : -distance(b,a)}}}
-
-\pnum
-\addedConcepts{Pointers are random access iterators with the following
-concept map}
-
-\begin{codeblock}
-namespace std {
- template<ObjectType T> concept_map RandomAccessIterator<T*> {
- typedef T value_type;
- typedef ptrdiff_t difference_type;
- typedef T& reference;
- typedef T* pointer;
- }
-}
-\end{codeblock}
-
-\addedConcepts{and pointers to const are random access iterators}
-
-\begin{codeblock}
-namespace std {
- template<ObjectType T> concept_map RandomAccessIterator<const T*> {
- typedef T value_type;
- typedef ptrdiff_t difference_type;
- typedef const T& reference;
- typedef const T* pointer;
- }
-}
-\end{codeblock}
-
-\pnum
-\addedConcepts{\mbox{\enternote}
-If there is an additional pointer type
-\mbox{\tcode{\,\xname{far}}}
-such that the difference of two
-\mbox{\tcode{\,\xname{far}}}
-is of type
-\mbox{\tcode{long}},
-an implementation may define}
-
-\color{addclr}
-\begin{codeblock}
- template <ObjectType T> concept_map RandomAccessIterator<T @\xname{far}@*> {
- typedef long difference_type;
- typedef T value_type;
- typedef T @\xname{far}@* pointer;
- typedef T @\xname{far}@& reference;
- }
-
- template <ObjectType T> concept_map RandomAccessIterator<const T @\xname{far}@*> {
- typedef long difference_type;
- typedef T value_type;
- typedef const T @\xname{far}@* pointer;
- typedef const T @\xname{far}@& reference;
- }
-\end{codeblock}
-\textcolor{addclr}{\exitnote}
-\color{black}
-
-\rSec2[shuffle.iterators]{Shuffle iterators}
-\pnum
-\addedConcepts{A class or built-in type \mbox{\tcode{X}} satisfies the
- requirements of a shuffle iterator if it meets the syntactic and
- semantic requirements of the \mbox{\tcode{ShuffleIterator}} concept.}
-
-\color{ccadd}
-\begin{codeblock}
-auto concept ShuffleIterator<typename X> {
- requires InputIterator<X>
- && OutputIterator<X, RvalueOf<InputIterator<X>::value_type>::type>
- && OutputIterator<X, RvalueOf<InputIterator<X>::reference>::type>
- && Constructible<InputIterator<X>::value_type,
- RvalueOf<InputIterator<X>::reference>::type>
- && MoveConstructible<InputIterator<X>::value_type>
- && HasAssign<InputIterator<X>::value_type,
- RvalueOf<InputIterator<X>::reference>::type>
- && HasSwap<InputIterator<X>::reference, InputIterator<X>::reference>;
-}
-\end{codeblock}
-\color{black}
-
-\pnum
-\addedConcepts{A shuffle iterator is a form of input and output iterator
- that allows values to be moved into or out of a sequence, along with
- permitting efficient swapping of values within the sequence. Shuffle
- iterators are typically used in algorithms that need to rearrange
- the elements within a sequence in a way that cannot be performed
- efficiently with swaps alone.}
-
-\pnum
-\addedConcepts{\enternote\ Any iterator that meets the additional requirements
- specified by \mbox{\tcode{ShuffleIterator}} is considered a shuffle
- iterator. \exitnote}
-
-\appendix
-\setcounter{chapter}{3}
-\normannex{depr}{Compatibility features}
-\begin{paras}
-
-\setcounter{section}{9}
-\rSec1[depr.lib.iterator.primitives]{Iterator primitives}
-
-\textcolor{black}{\pnum}
-To simplify the \changedConcepts{task of defining iterators}{use of
- iterators and provide backward compatibility with previous C++
- Standard Libraries}, the library provides
-several classes and functions.
-
-\pnum
-\addedConcepts{The \mbox{\tcode{iterator_traits}} and supporting
- facilities described
-in this section are deprecated. \mbox{\enternote} the iterator
-concepts (\mbox{\ref{iterator.concepts}}) provide the equivalent
-functionality using the concept mechanism. \mbox{\exitnote}}
-
-\end{paras}
-
-\rSec2[iterator.traits]{Iterator traits}
-
-\pnum
-\changedConcepts{
-To implement algorithms only in terms of iterators, it is often necessary to
-determine the value and
-difference types that correspond to a particular iterator type.
-Accordingly, it is required that if}
-{Iterator traits provide an auxiliary mechanism for
-accessing the associated types of an iterator. If}
-\tcode{Iterator}\
-is the type of an iterator,
-the types
-
-\begin{codeblock}
-iterator_traits<Iterator>::difference_type
-iterator_traits<Iterator>::value_type
-iterator_traits<Iterator>::iterator_category
-\end{codeblock}
-
-\addedConcepts{shall} be defined as the iterator's difference type, value type and iterator
-category \addedConcepts{(24.3.3)}, respectively.
-In addition, the types
-
-\begin{codeblock}
-iterator_traits<Iterator>::reference
-iterator_traits<Iterator>::pointer
-\end{codeblock}
-
-shall be defined as the iterator's reference and pointer types, that is, for an
-iterator object \tcode{a}, the same type as the type of \tcode{*a} and \tcode{a->},
-respectively. In the case of an output iterator, the types
-
-\begin{codeblock}
-iterator_traits<Iterator>::difference_type
-iterator_traits<Iterator>::value_type
-iterator_traits<Iterator>::reference
-iterator_traits<Iterator>::pointer
-\end{codeblock}
-
-may be defined as \tcode{void}.
-
-\setcounter{Paras}{5}
-\pnum
-\addedConcepts{For each iterator category, a partial specializations of the
- \mbox{\tcode{iterator_traits}} class template provide appropriate
- type definitions for programs that use the deprecated iterator
- traits mechanism. These partial specializations provide backward
- compatibility for unconstrained templates using iterators as
- specified by the corresponding requirements tables of ISO/IEC
- 14882:2003.}
-\color{ccadd}
-\begin{codeblock}
-concept IsReference<typename T> { } // exposition only
-template<typename T> concept_map IsReference<T&> { }
-
-concept IsPointer<typename T> { } // exposition only
-template<typename T> concept_map IsPointer<T*> { }
-
-template<Iterator Iter> struct iterator_traits<Iter> {
- typedef void difference_type;
- typedef void value_type;
- typedef void pointer;
- typedef void reference;
- typedef output_iterator_tag iterator_category;
-};
-
-template<InputIterator Iter> struct iterator_traits<Iter> {
- typedef Iter::difference_type difference_type;
- typedef Iter::value_type value_type;
- typedef Iter::pointer pointer;
- typedef Iter::reference reference;
- typedef input_iterator_tag iterator_category;
-};
-
-template<ForwardIterator Iter>
- requires IsReference<Iter::reference> && IsPointer<Iter::pointer>
- struct iterator_traits<Iter> {
- typedef Iter::difference_type difference_type;
- typedef Iter::value_type value_type;
- typedef Iter::pointer pointer;
- typedef Iter::reference reference;
- typedef forward_iterator_tag iterator_category;
- };
-
-template<BidirectionalIterator Iter>
- requires IsReference<Iter::reference> && IsPointer<Iter::pointer>
- struct iterator_traits<Iter> {
- typedef Iter::difference_type difference_type;
- typedef Iter::value_type value_type;
- typedef Iter::pointer pointer;
- typedef Iter::reference reference;
- typedef bidirectional_iterator_tag iterator_category;
- };
-
-template<RandomAccessIterator Iter>
- requires IsReference<Iter::reference> && IsPointer<Iter::pointer>
- struct iterator_traits<Iter> {
- typedef Iter::difference_type difference_type;
- typedef Iter::value_type value_type;
- typedef Iter::pointer pointer;
- typedef Iter::reference reference;
- typedef random_access_iterator_tag iterator_category;
- };
-\end{codeblock}
-\exitnote\
-\color{black}
-
-\rSec2[iterator.basic]{Basic iterator}
-
-\editorial{We deprecated the basic \tcode{iterator} template because
- it isn't really the right way to specify iterators any more. Even
- when using this template, users should write concept maps so that
- (1) their iterators will work when \tcode{iterator_traits} and the
- backward-compatibility models go away, and (2) so that their
- iterators will be checked against the iterator concepts as early as
- possible.}
-
-\pnum
-The
-\tcode{iterator}
-template may be used as a base class to ease the definition of required types
-for new iterators.
-
-\begin{codeblock}
-namespace std {
- template<class Category, class T, class Distance = ptrdiff_t,
- class Pointer = T*, class Reference = T&>
- struct iterator {
- typedef T value_type;
- typedef Distance difference_type;
- typedef Pointer pointer;
- typedef Reference reference;
- typedef Category iterator_category;
- };
-}
-\end{codeblock}
-
-\rSec2[std.iterator.tags]{Standard iterator tags}
-
-\pnum
-\index{input_iterator_tag@\tcode{input_iterator_tag}}%
-\index{output_iterator_tag@\tcode{output_iterator_tag}}%
-\index{forward_iterator_tag@\tcode{forward_iterator_tag}}%
-\index{bidirectional_iterator_tag@\tcode{bidirectional_iterator_tag}}%
-\index{random_access_iterator_tag@\tcode{random_access_iterator_tag}}%
-\changedConcepts{It is often desirable for a
-function template specialization
-to find out what is the most specific category of its iterator
-argument, so that the function can select the most efficient algorithm at compile time.
-To facilitate this, the}{The}
-library \textcolor{black}{}introduces
-\techterm{category tag}\
-classes which are used as compile time tags
-\changedConcepts{for algorithm selection.}{to distinguish the
- different iterator concepts when using the \mbox{\tcode{iterator_traits}} mechanism.}
-They are:
-\tcode{input_iterator_tag},
-\tcode{output_iterator_tag},
-\tcode{forward_iterator_tag},
-\tcode{bidirectional_iterator_tag}\
-and
-\tcode{random_access_iterator_tag}.
-For every iterator of type
-\tcode{Iterator},
-\tcode{iterator_traits<Iterator>::it\-er\-a\-tor_ca\-te\-go\-ry}
-shall be defined to be the most specific category tag that describes the
-iterator's behavior.
-
-\begin{codeblock}
-namespace std {
- struct input_iterator_tag {};
- struct output_iterator_tag {};
- @\color{black}@struct forward_iterator_tag: public input_iterator_tag {};
- struct bidirectional_iterator_tag: public forward_iterator_tag {};
- struct random_access_iterator_tag: public bidirectional_iterator_tag {};
-}
-\end{codeblock}
-
-\pnum
-\eremove{Remove this paragraph: It gives an example using
- \tcode{iterator_traits}, which we no longer encourage.}
-
-\color{addclr}
-\rSec2[iterator.backward]{Iterator backward compatibility}
-
-\pnum
-\addedConcepts{The library provides concept maps that allow iterators
- specified with \mbox{\tcode{iterator_traits}}
-to interoperate with algorithms that require iterator
-concepts. \enterexample}
-\begin{codeblock}
-struct random_iterator
-{
- typedef std::input_iterator_tag iterator_category;
- typedef int value_type;
- typedef int difference_type;
- typedef int* pointer;
- typedef int reference;
-
- random_iterator(int remaining = 0) : remaining(remaining) { }
-
- int operator*() const { return std::rand(); }
- int* operator->() const { return 0; }
-
- random_iterator& operator++() { --remaining; return *this; }
-
- random_iterator operator++(int) {
- random_iterator tmp(*this); ++(*this); return tmp;
- }
-
- int remaining;
-
- friend bool
- operator==(const random_iterator& i, const random_iterator& j)
- {
- return i.remaining == j.remaining;
- }
-
- friend bool
- operator!=(const random_iterator& i, const random_iterator& j)
- {
- return i.remaining != j.remaining;
- }
-};
-
-void f(random_iterator i, random_iterator j) {
- std::copy(i, j, std::ostream_iterator<int>(std::cout, " ")); // okay: standard library produces concept
- // map InputIterator<random_iterator>
-}
-\end{codeblock}
-\addedConcepts{\exitexample}
-
-\pnum
-\addedConcepts{For all iterator types except output iterators, the
-associated types
-\mbox{\tcode{difference_type}},
-\mbox{\tcode{value_type}},
-\mbox{\tcode{pointer}}
-and
-\mbox{\tcode{reference}}
-are given the same values as their counterparts in
-\mbox{\tcode{iterator_traits}}. For output iterators, the
-\mbox{\tcode{reference}} type is deduced from the type of the output
-iterator's dereference operator.}
-
-\pnum
-\color{addclr}
-\addedConcepts{When the
-\mbox{\tcode{iterator_traits}}
-specialization contains the nested types
-\mbox{\tcode{difference_type}},
-\mbox{\tcode{value_type}},
-\mbox{\tcode{pointer}},
-\mbox{\tcode{reference}}
-and
-\mbox{\tcode{iterator_category}}, the
-\mbox{\tcode{iterator_traits}} specialization is considered to be \mbox{\techterm{valid}}.}
-
-\addedConcepts{\enterexample}
-\addedConcepts{The following example is well-formed. The backward-compatbility
-concept map for \mbox{\tcode{InputIterator}} does not match because
-\mbox{\tcode{iterator_traits<int>}} is not valid.}
-\begin{codeblock}
-@\color{addclr}@template<IntegralLike T> void f(T);
-template<InputIterator T> void f(T);
-
-void g(int x) {
- f(x); // okay
-}
-\end{codeblock}
-\addedConcepts{\exitexample}
-
-\pnum
-\addedConcepts{The library shall provide a concept map
-\mbox{\tcode{Iterator<Iter>}}
-for any type \mbox{\tcode{Iter}} with a valid \mbox{\tcode{iterator_traits<Iter>}}, an
-\mbox{\tcode{iterator_traits<Iter>::it\-er\-a\-tor_ca\-te\-go\-ry}}
-convertible to
-\mbox{\tcode{output_iterator_tag}}, and that meets the
- syntactic requirements of the \mbox{\tcode{Iterator}}
- concept.}
-
-\pnum
-\addedConcepts{The library shall provide a concept map
-\mbox{\tcode{InputIterator<Iter>}}
-for any type \mbox{\tcode{Iter}} with a valid \mbox{\tcode{iterator_traits<Iter>}}, an \mbox{\tcode{iterator_traits<Iter>::it\-er\-a\-tor_ca\-te\-go\-ry}} convertible to
-\mbox{\tcode{input_iterator_tag}}, and that meets the
-syntactic requirements of the \mbox{\tcode{InputIterator}} concept.}
-
-\pnum
-\addedConcepts{The library shall provide a concept map
-\mbox{\tcode{ForwardIterator<Iter>}}
-for any type \mbox{\tcode{Iter}} with a valid
-\mbox{\tcode{iterator_traits<Iter>}}, an \mbox{\tcode{iterator_traits<Iterator>::it\-er\-a\-tor_ca\-te\-go\-ry}}
-convertible to
-\mbox{\tcode{forward_iterator_tag}}, and that meets the
-syntactic requirements of the \mbox{\tcode{ForwardIterator}} concept.}
-
-\pnum
-\addedConcepts{The library shall provide a concept map
-\mbox{\tcode{BidirectionalIterator<Iter>}}
-for any type \mbox{\tcode{Iter}} with a valid
-\mbox{\tcode{iterator_traits<Iter>}}, an
-\mbox{\tcode{iterator_traits<Iterator>::it\-er\-a\-tor_ca\-te\-go\-ry}}
-convertible to
-\mbox{\tcode{bidirectional_iterator_tag}}, and that meets the
-syntactic requirements of the \mbox{\tcode{BidirectionalIterator}} concept.}
-
-\pnum
-\addedConcepts{The library shall provide a concept map
-\mbox{\tcode{RandomAccessIterator<Iter>}}
-for any type \mbox{\tcode{Iter}} with a valid
-\mbox{\tcode{iterator_traits<Iter>}}, an
-\mbox{\tcode{iterator_traits<Iterator>::it\-er\-a\-tor_ca\-te\-go\-ry}}
-convertible to
-\mbox{\tcode{random_access_iterator_tag}}, and that meets the
-syntactic requirements of the \mbox{\tcode{RandomAccessIterator}} concept.}
-
-\section*{Acknowledgments}
-Thanks to Beman Dawes for alerting us to omissions from the iterator
-concepts and Daniel Kr\"ugler for many helpful comments. Both Mat
-Marcus and Jaakko J\"arvi were particularly helpful in the design of
-the new iterator taxonomy.
-
-\bibliographystyle{plain}
-\bibliography{../local}
-
-\end{document}
\ No newline at end of file

Date view Thread view Subject view Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk