|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r48703 - sandbox/committee/concepts/stdlib
From: dgregor_at_[hidden]
Date: 2008-09-10 15:54:49
Author: dgregor
Date: 2008-09-10 15:54:48 EDT (Wed, 10 Sep 2008)
New Revision: 48703
URL: http://svn.boost.org/trac/boost/changeset/48703
Log:
Remove uses of the term "iterator category" outside of the deprecated iterator primitives section. Define the term there
Text files modified:
sandbox/committee/concepts/stdlib/clib-algorithms.tex | 89 +++++++-----------------------
sandbox/committee/concepts/stdlib/clib-containers.tex | 115 +++++++++++++++++----------------------
sandbox/committee/concepts/stdlib/clib-iterconcepts.tex | 66 ++++++++--------------
3 files changed, 96 insertions(+), 174 deletions(-)
Modified: sandbox/committee/concepts/stdlib/clib-algorithms.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-algorithms.tex (original)
+++ sandbox/committee/concepts/stdlib/clib-algorithms.tex 2008-09-10 15:54:48 EDT (Wed, 10 Sep 2008)
@@ -52,7 +52,7 @@
\begin{center}
\huge
Concepts for the C++0x Standard Library: Algorithms \\
-(Revision 4)
+(Revision 5)
\normalsize
\end{center}
@@ -64,65 +64,20 @@
Thomas Witt, Zephyr Associates, Inc.\\
Andrew Lumsdaine, Indiana University
\end{tabular}\vspace{-6pt}
-\par\noindent Document number: N2740=08-0250\vspace{-6pt}
-\par\noindent Revises document number: N2696=08-0206\vspace{-6pt}
+\par\noindent Document number: DRAFT\vspace{-6pt}
+\par\noindent Revises document number: N2740=08-0250\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}
\libintrotext{Chapter 25}
-\section*{Changes from N2696}
+\section*{Changes from N2740}
\begin{itemize}
-\item Fixed requirements for \tcode{partial_sort_copy}.
-\item Replaced uses of the \tcode{HasStdMove} concept with uses of
- \tcode{RvalueOf}, and reverted back to using \tcode{std::move} (that
- than \tcode{std_move}) for semantic descriptions.
-\item Use the \tcode{EquivalenceRelation} concept in
- \tcode{adjacent_find}, \tcode{unique}, and \tcode{unique_copy}.
-\item Removed the \tcode{NothrowDestructible} requirement from
- \tcode{swap}, since it is now implied by \tcode{MoveConstructible}
- (again).
-\item Updated the requirements on \tcode{remove}, \tcode{remove_if},
- and \tcode{unique} to support move semantics.
-\item Removed the erroneous \tcode{CopyConstructible<Rand>}
- requirement from \tcode{random_shuffle}.
-\item Removed the \tcode{UniformRandomNumberGenerator} variant of
- \tcode{random_shuffle}, because it is (and has always been)
- ambiguous with the second variant.
-\item Remove the ``extra''
- \tcode{LessThanComparable}/\tcode{StrictWeakOrder} requirements on
- the algorithms \tcode{merge}, \tcode{includes}, \tcode{set_union},
- \tcode{set_intersection}, \tcode{set_difference}, and
- \tcode{set_symmetric_difference}. These requirements were only used
- to enable standard library ``debug modes'', but we have found an
- alternative solution that does not push additional requirements into
- the specification.
-\item The algorithms \tcode{random_shuffle}, \tcode{partition},
- \tcode{rotate}, \tcode{next_permutation}, and
- \tcode{prev_permutation} now use the \tcode{ShuffleIterator} concept
- rather than \tcode{HasSwap}. We applied the following reasoning to
- determine when to use \tcode{ShuffleIterator<Iter>} rather than
- \tcode{HasSwap<Iter::reference, Iter::reference>}: the requirement
- occurs when the algorithm is performing a permutation on the
- elements of the sequence. One can view the permutation of the
- elements as a cycle along which the elements move, e.g., the element
- at index 1 moves to index 3, the element at index 3 moves to index
- 7, the element at index 7 moves to index 9, and finally the element
- at index 9 moves to index 1. Any cycle can be implemented via swaps,
- but with cycles of length greater than two the cycle can be more
- efficiently implemented via a series of move operations. Thus, for
- algorithms with only cycles of length two (e.g., \tcode{reverse},
- \tcode{swap_ranges}) we specify the \tcode{HasSwap<Iter::reference,
- Iter::reference>} requirement; for algorithms that may have cycles
- of length greater than two (e.g., \tcode{random_shuffle},
- \tcode{sort}, \tcode{partition}), we specify the
- \tcode{ShuffleIterator} requirement.
-\item Added conceptualized versions of the algorithms in N2666, from
- Daniel Kr\"ugler: \tcode{all_of}, \tcode{any_of}, \tcode{none_of},
- \tcode{find_if_not}, \tcode{copy_n}, \tcode{copy_if},
- \tcode{partition_copy}, \tcode{is_partitioned}, and
- \tcode{partition_point}.
+\item Eliminate the use of the term ``iterator category'', instead
+ referring to the appropriate iterator concept
+ (Clause~\ref{alg.algorithms}). Thanks to Alisdair Meredith for
+ pointing out the inconsistency.
\end{itemize}
\end{titlepage}
@@ -554,18 +509,18 @@
Iter @\farg{last}@,
Compare @\farg{comp}@);
template<InputIterator InIter, RandomAccessIterator RAIter>
- requires @\changedCCC{HasAssign<RAIter::reference, InIter::reference>}{ShuffleIterator<RAIter>}@
- && @\changedCCC{Swappable<RAIter::reference>}{OutputIterator<RAIter, InIter::reference>}@
+ requires ShuffleIterator<RAIter>
+ && OutputIterator<RAIter, InIter::reference>
&& HasLess<InIter::value_type, RAIter::value_type>
- && @\changedCCC{HasLess}{LessThanComparable}@<RAIter::value_type>
+ && LessThanComparable<RAIter::value_type>
RAIter partial_sort_copy(InIter @\farg{first}@, InIter @\farg{last}@,
RAIter @\farg{result_first}@, RAIter @\farg{result_last}@);
template<InputIterator InIter, RandomAccessIterator RAIter, class Compare>
- requires @\changedCCC{HasAssign<RAIter::reference, InIter::reference>}{ShuffleIterator<RAIter>}@
- && @\changedCCC{Swappable<RAIter::reference>}{OutputIterator<RAIter, InIter::reference>}@
+ requires ShuffleIterator<RAIter>
+ && OutputIterator<RAIter, InIter::reference>
&& Predicate<Compare, InIter::value_type, RAIter::value_type>
&& StrictWeakOrder<Compare, RAIter::value_type>}
- @\addedCC{\&\& CopyConstructible<Compare>}@
+ && CopyConstructible<Compare>
RAIter partial_sort_copy(InIter @\farg{first}@, InIter @\farg{last}@,
RAIter @\farg{result_first}@, RAIter @\farg{result_last}@,
Compare @\farg{comp}@);
@@ -1080,8 +1035,8 @@
\tcode{+}\
and
\tcode{-}\
-are used for some of the iterator categories for which
-they do not have to be defined.
+are used \changedConcepts{for some of the iterator categories for which
+they do not have to be defined}{with iterators that do not necessarily define these operators}.
In these cases the semantics of
\tcode{a+n}\
is the same as that of
@@ -2947,19 +2902,19 @@
\index{partial_sort_copy@\tcode{partial_sort_copy}}%
\color{addclr}\begin{itemdecl}
template<InputIterator InIter, RandomAccessIterator RAIter>
- requires @\changedCCC{HasAssign<RAIter::reference, InIter::reference>}{ShuffleIterator<RAIter>}@
- && @\changedCCC{Swappable<RAIter::reference>}{OutputIterator<RAIter, InIter::reference>}@
+ requires ShuffleIterator<RAIter>
+ && OutputIterator<RAIter, InIter::reference>
&& HasLess<InIter::value_type, RAIter::value_type>
- && @\changedCCC{HasLess}{LessThanComparable}@<RAIter::value_type>
+ && LessThanComparable<RAIter::value_type>
RAIter partial_sort_copy(InIter @\farg{first}@, InIter @\farg{last}@,
RAIter @\farg{result_first}@, RAIter @\farg{result_last}@);
template<InputIterator InIter, RandomAccessIterator RAIter, class Compare>
- requires @\changedCCC{HasAssign<RAIter::reference, InIter::reference>}{ShuffleIterator<RAIter>}@
- && @\changedCCC{Swappable<RAIter::reference>}{OutputIterator<RAIter, InIter::reference>}@
+ requires ShuffleIterator<RAIter>
+ && OutputIterator<RAIter, InIter::reference>
&& Predicate<Compare, InIter::value_type, RAIter::value_type>
&& StrictWeakOrder<Compare, RAIter::value_type>}
- @\addedCC{\&\& CopyConstructible<Compare>}@
+ && CopyConstructible<Compare>
RAIter partial_sort_copy(InIter @\farg{first}@, InIter @\farg{last}@,
RAIter @\farg{result_first}@, RAIter @\farg{result_last}@,
Compare @\farg{comp}@);
Modified: sandbox/committee/concepts/stdlib/clib-containers.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-containers.tex (original)
+++ sandbox/committee/concepts/stdlib/clib-containers.tex 2008-09-10 15:54:48 EDT (Wed, 10 Sep 2008)
@@ -52,7 +52,7 @@
\begin{center}
\huge
Concepts for the C++0x Standard Library: Containers\\
-(Revision 3)
+(Revision 4)
\end{center}
\normalsize
@@ -64,8 +64,8 @@
Mat Marcus, Adobe Systems, Inc.\\
Pablo Halpern, Bloomberg, L.P.
\end{tabular}\vspace{-6pt}
-\par\noindent Document number: N2738=08-0248\vspace{-6pt}
-\par\noindent Revises document number: N2694=08-0204\vspace{-6pt}
+\par\noindent Document number: DRAFT\vspace{-6pt}
+\par\noindent Revises document number: N2738=08-0248\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}
@@ -73,65 +73,17 @@
\section*{Introduction}
\libintrotext{Chapter 23}
-\section*{Changes from N2694}
+\section*{Changes from N2738}
\begin{itemize}
-\item Added the \tcode{NothrowDestructible<Cont>} requirement to each
- of the container adaptors (\tcode{queue}, \tcode{priority_queue},
- \tcode{stack}).
-\item Changed all of the \tcode{HasConstructible} requirements to
- \tcode{Constructible} requirements, since we always need a no-throw
- destructor.
-\item Use the \tcode{EquivalenceRelation} concept instead of
- \tcode{Predicate} for the \tcode{unique} member in \tcode{forward_list}.
-\item Changed the \tcode{Callable} requirements on the hash functions
- to accept their value by reference-to-const.
-\item Added the \tcode{ConstructibleAsElement<Alloc, value_type,
- value_type\&\&>} requirement to the move constructors for all of
- the associative containers.
-\item Added the \tcode{CopyAssignable<value_type>} requirement to the
- copy-assignment operators of all of the associative containers.
-\item Added the \tcode{MoveConstructible<value_type>} requirement to
- the range-insertion functions and range constructors of the
- associative containers, to account for the move-construction one
- must perform to actually insert the value into the container (if an
- equivalent value isn't already there).
-\item Fixed the requirements on \tcode{operator[]} for \tcode{map} and
- \tcode{unordered_map}.
-\item The \tcode{rehash} member of the unordered associative
- containers now requires the value type to be
- \tcode{MoveConstructible}, rather than using the
- \tcode{ConstructibleAsElement} form, because \tcode{rehash} is only
- dealing with values already constructed with the container's
- allocator.
-\item The value type of a \tcode{vector} must now be
- \tcode{MoveConstructible}. Previously, only those member functions
- that could cause reallocation required
- \tcode{MoveConstructible}. However, the concepts drafting group
- determined that, since nearly every interesting member of
- \tcode{vector} required \tcode{MoveConstructible<T>}, this approach
- was far simpler and better represented the behavior and expectations
- of \tcode{vector}.
-\item Removed the \tcode{SequenceContainer} and
- \tcode{MemberSequenceContainer} concepts, which weren't useful in
- classifying containers because they excluded
- \tcode{forward_list}. The members and axioms have been redistributed
- to \tcode{FrontInsertionSequence} and \tcode{BackInsertionSequence}.
-\item Renamed \tcode{FrontInsertionSequence},
- \tcode{BackInsertionSequence}, and \tcode{InsertionSequence} to
- \tcode{FrontInsertionContainer}, \tcode{BackInsertionContainer}, and
- \tcode{InsertionContainer}, respectively.
-\item Added the \tcode{RangeInsertionContainer} and
- \tcode{MemberRangeInsertionContainer} concepts, along with a concept
- map to adapt from member- to free-function syntax, which is
- necessary for \tcode{priority_queue}'s constructors.
-\item Updated the base wording to reflect the changes in N2691,
- including support for initializer lists and changes to emplace.
-\item Added the \tcode{BackEmplacementContainer} concept, to support the
- new \tcode{emplace} operations in the container adaptors, along with
- its \tcode{Member} version and appropriate concept map
- template. Added \tcode{FrontEmplacementContainer} and
- \tcode{EmplacementContainer}, their \tcode{Member} versions and concept
- map templates, for symmetry.
+\item Fix definition of \tcode{push_front} in the
+ \tcode{FrontInsertionContainer} concept map
+ (\ref{container.concepts.maps}).
+\item Removed all uses of the term ``iterator category'', in favor of
+ explicit mentions of iterator concept names
+ (\ref{container.requirements.general}, \ref{sequence.reqmts},
+ \ref{associative.reqmts}, \ref{unord.req},
+ \ref{vector.cons}). Thanks to Alisdair Meredith for pointing out
+ this inconsistency!
\end{itemize}
\end{titlepage}
@@ -317,14 +269,14 @@
\tcode{X::iterator} &
iterator type whose value type is \tcode{T} &
&
- any iterator category except output iterator.
+ \changedConcepts{any iterator category except output iterator}{meets the requirements of the \mbox{\tcode{InputIterator}} concept}.
convertible to \tcode{X::const_iterator}. &
compile time \\ \rowsep
\tcode{X::const_iterator} &
constant iterator type whose value type is \tcode{T} &
&
- any iterator category except output iterator &
+\changedConcepts{any iterator category except output iterator}{meets the requirements of the \mbox{\tcode{InputIterator}} concept} &
compile time \\ \rowsep
\tcode{X::dif\-ference_type} &
@@ -526,6 +478,14 @@
\tcode{get_allocator()} returns a copy of the \tcode{Allocator} object
used to construct the container, or to replace the allocator.
+\setcounter{Paras}{10}
+\pnum
+If the iterator type of a container \changedConcepts{belongs to the
+ bidirectional or random access iterator categories (24.1)}{meets the
+ requirements of the \mbox{\tcode{BidirectionalIterator}} concept},
+the container is called reversible and satisfies the additional
+requirements in Table 91.
+
\rSec2[sequence.reqmts]{Sequence containers}
\setcounter{Paras}{3}
\pnum
@@ -636,6 +596,13 @@
Replaces elements in \tcode{a}\ with \tcode{n}\ copies of \tcode{t}. \\
\end{libreqtab3}
+\setcounter{Paras}{4}
+\pnum
+\tcode{iterator} and \tcode{const_iterator} types for sequence
+containers shall \changedConcepts{be at least of the forward iterator
+ category}{meet the requirements of the
+ \mbox{\tcode{ForwardIterator}} concept}.
+
\setcounter{Paras}{11}
\pnum
@@ -732,7 +699,16 @@
\end{libreqtab4a}
\rSec2[associative.reqmts]{Associative containers}
-\setcounter{Paras}{6}
+\setcounter{Paras}{5}
+\pnum
+\tcode{iterator} of an associative container \changedConcepts{is of
+ the bidirectional iterator category}{meets the requirements of the
+ \mbox{\tcode{BidirectionalIterator}} concept}. For associative
+containers where
+the value type is the same as the key type, both \tcode{iterator} and
+\tcode{const_iterator} are constant iterators. It
+is unspecified whether or not \tcode{iterator} and
+\tcode{const_iterator} are the same type.
\pnum
In Table~\ref{tab:containers.associative.requirements},
@@ -884,6 +860,13 @@
\multicolumn{4}{c}{\editorial{No additional changes to this table.}} \\ \rowsep
\end{libreqtab4d}
+\setcounter{Paras}{10}
+\pnum
+The iterator types \tcode{iterator} and \tcode{const_iterator} of an unordered associative container \changedConcepts{are of at least the
+forward iterator category}{meet the requirements of the
+\mbox{\tcode{ForwardIterator}} concept}. For unordered associative containers where the key type and value type are the
+same, both \tcode{iterator} and \tcode{const_iterator} are const\addedConcepts{ant} iterators.
+
\editorial{Add the following new section [container.concepts]}
\color{addclr}
\rSec2[container.concepts]{Container concepts}
@@ -1316,7 +1299,7 @@
reference front(C& c) { return c.front(); }
const_reference front(const C& c) { return c.front(); }
- void push_front(C& c, const Container<C>::value_type &v) { c.front(v); }
+ void push_front(C& c, const Container<C>::value_type &v) { c.push_front(v); }
void pop_front(C& c) { c.pop_front(); }
}
\end{itemdecl}
@@ -4614,7 +4597,7 @@
\tcode{first}\
and
\tcode{last})
-and no reallocations if iterators first and last are of forward, bidirectional, or random access categories.
+and no reallocations if \changedConcepts{iterators first and last are of forward, bidirectional, or random access categories}{\mbox{\tcode{Iter}} meets the requirements of the \mbox{\tcode{ForwardIterator}} concept}.
It makes order
\tcode{N}\
calls to the copy constructor of
Modified: sandbox/committee/concepts/stdlib/clib-iterconcepts.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-iterconcepts.tex (original)
+++ sandbox/committee/concepts/stdlib/clib-iterconcepts.tex 2008-09-10 15:54:48 EDT (Wed, 10 Sep 2008)
@@ -263,39 +263,11 @@
used.
\item Fixed the associated function default implementations in
\tcode{RandomAccessIterator}.
+\item Defined the term ``iterator category'' within the (deprecated)
+ iterator traits section, so that others of these deprecated
+ constructs can refer to iterator categories. Thanks to Alisdair
+ Meredith for noting this omission.
\end{itemize}
-
-\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.
-\item Added the \tcode{subscript_reference} associated type to the
- \tcode{RandomAccessIterator} concept, to capture the result of
- \tcode{operator[]}. This type may need to be a proxy that is
- different from the \tcode{reference} type, for, e.g., a
- \tcode{counting_iterator} that meets the \Cpp03
- \tcode{RandomAccessIterator} requirements. See the reflector thread
- starting at c++std-lib-22126 for more information.
-\end{itemize}
-
-
\end{titlepage}
\section*{Proposed Wording}
@@ -615,7 +587,7 @@
o
denotes a value of some type that is writable to the output iterator.}
-\color{ccadd}
+\color{addclr}
\begin{codeblock}
concept Iterator<typename X> : Semiregular<X> {
MoveConstructible reference = typename X::reference;
@@ -1176,7 +1148,7 @@
requirements of a shuffle iterator if it meets the syntactic and
semantic requirements of the \mbox{\tcode{ShuffleIterator}} concept.}
-\color{ccadd}
+\color{addclr}
\begin{codeblock}
auto concept ShuffleIterator<typename X> {
requires InputIterator<X>
@@ -1249,7 +1221,7 @@
\end{codeblock}
\addedConcepts{shall} be defined as the iterator's difference type, value type and iterator
-category \addedConcepts{(24.3.3)}, respectively.
+category \addedConcepts{(described below)}, respectively.
In addition, the types
\begin{codeblock}
@@ -1270,18 +1242,30 @@
may be defined as \tcode{void}.
-\editorial{Paragraphs 2--5 of this section are unchanged.}
+\editorial{Add the following new paragraph}
+\pnum
+\addedConcepts{The \mbox{\techterm{category}} of an iterator roughly
+ describes which of the iterator concepts
+ (\mbox{\ref{iterator.concepts}}) the iterator satisfies. Iterator
+ categories refer to iterators as defined by ISO/IEC
+ 14882:2003, and can be one of \mbox{\techterm{input iterator}},
+ \mbox{\techterm{output iterator}}, \mbox{\techterm{forward
+ iterator}}, \mbox{\techterm{bidirectional iterator}}, or
+ \mbox{\techterm{random access iterator}}.}
+
+\editorial{The existing paragraphs 2--5 of this section are
+ unchanged. Add a new paragraph at the end of this section:}
-\setcounter{Paras}{5}
+\setcounter{Paras}{6}
\pnum
-\addedConcepts{For each iterator category, a partial specializations of the
+\addedConcepts{For each iterator category, a partial specialization 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}
+\color{addclr}
\begin{codeblock}
concept IsReference<typename T> { } // exposition only
template<typename T> concept_map IsReference<T&> { }
@@ -1302,7 +1286,7 @@
typedef Iter::value_type value_type;
typedef Iter::pointer pointer;
typedef Iter::reference reference;
- typedef input_iterator_tag iterator_category;
+ typedef input_iterator_tag iterator_category;
};
template<ForwardIterator Iter>
@@ -1312,7 +1296,7 @@
typedef Iter::value_type value_type;
typedef Iter::pointer pointer;
typedef Iter::reference reference;
- typedef forward_iterator_tag iterator_category;
+ typedef forward_iterator_tag iterator_category;
};
template<BidirectionalIterator Iter>
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