|
|
Boost-Commit : |
From: dgregor_at_[hidden]
Date: 2008-08-16 13:10:25
Author: dgregor
Date: 2008-08-16 13:10:24 EDT (Sat, 16 Aug 2008)
New Revision: 48176
URL: http://svn.boost.org/trac/boost/changeset/48176
Log:
Finished edits to the algorithms chapter
Text files modified:
sandbox/committee/concepts/stdlib/clib-algorithms.tex | 351 ++++++++++++++++++---------------------
sandbox/committee/concepts/stdlib/clib-concepts.tex | 99 +++++++---
sandbox/committee/concepts/stdlib/clib-containers.tex | 12
3 files changed, 236 insertions(+), 226 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-08-16 13:10:24 EDT (Sat, 16 Aug 2008)
@@ -78,6 +78,46 @@
\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.
\end{itemize}
\end{titlepage}
@@ -167,8 +207,7 @@
template<ForwardIterator Iter>
requires EqualityComparable<Iter::value_type>
Iter adjacent_find(Iter @\farg{first}@, Iter @\farg{last}@);
- template<ForwardIterator Iter,
- Predicate<auto, Iter::value_type, Iter::value_type> Pred>
+ template<ForwardIterator Iter, EquivalenceRelation<auto, Iter::value_type> Pred>
requires CopyConstructible<Pred>
Iter adjacent_find(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
@@ -241,13 +280,13 @@
@\textcolor{black}{// \ref{alg.swap}, swap:}@
template<class T>
- requires MoveAssignable<T> && MoveConstructible<T> && NothrowDestructible<T>
+ requires MoveAssignable<T> && MoveConstructible<T>
void swap(T& @\farg{a}@, T& @\farg{b}@);
template<ForwardIterator Iter1, ForwardIterator Iter2>
requires HasSwap<Iter1::reference, Iter2::reference>
Iter2 swap_ranges(Iter1 @\farg{first1}@, Iter1 @\farg{last1}@,
Iter2 @\farg{first2}@);
- template<ForwardIterator Iter1, ForwardIterator Iter2>
+ template<Iterator Iter1, Iterator Iter2>
requires HasSwap<Iter1::reference, Iter2::reference>
void iter_swap(Iter1 @\farg{a}@, Iter2 @\farg{b}@);
@@ -272,8 +311,7 @@
&& OutputIterator<Iter, const T&>
&& HasEqualTo<Iter::value_type, T>
void replace(Iter @\farg{first}@, Iter @\farg{last}@,
- const T& @\farg{old_value}@, const T&
- @\farg{new_value}@);
+ const T& @\farg{old_value}@, const T& @\farg{new_value}@);
template<ForwardIterator Iter, Predicate<auto, Iter::value_type> Pred, class T>
requires OutputIterator<Iter, Iter::reference>
&& OutputIterator<Iter::reference, const T&>
@@ -282,7 +320,7 @@
Pred @\farg{pred}@, const T& @\farg{new_value}@);
template<InputIterator InIter, typename OutIter, class T>
requires OutputIterator<OutIter, InIter::reference>
- && OutputIterator<Iter, const T&>
+ && OutputIterator<OutIter, const T&>
&& HasEqualTo<InIter::value_type, T>
OutIter replace_copy(InIter @\farg{first}@, InIter @\farg{last}@,
OutIter @\farg{result}@,
@@ -314,12 +352,12 @@
void generate_n(Iter @\farg{first}@, Size @\farg{n}@, Generator @\farg{gen}@);
template<ForwardIterator Iter, class T>
- requires OutputIterator<Iter, Iter::reference>
+ requires OutputIterator<Iter, RvalueOf<Iter::reference>::type>
&& HasEqualTo<Iter::value_type, T>
Iter remove(Iter @\farg{first}@, Iter @\farg{last}@,
const T& @\farg{value}@);
template<ForwardIterator Iter, Predicate<auto, Iter::value_type> Pred>
- requires OutputIterator<Iter, Iter::reference>
+ requires OutputIterator<Iter, RvalueOf<Iter::reference>::type>
&& CopyConstructible<Pred>
Iter remove_if(Iter @\farg{first}@, Iter @\farg{last}@,
Pred @\farg{pred}@);
@@ -334,12 +372,11 @@
OutIter @\farg{result}@, Pred @\farg{pred}@);
template<ForwardIterator Iter>
- requires OutputIterator<Iter, Iter::reference>
+ requires OutputIterator<Iter, RvalueOf<Iter::reference>::type>
&& EqualityComparable<Iter::value_type>
Iter unique(Iter @\farg{first}@, Iter @\farg{last}@);
- template<ForwardIterator Iter,
- Predicate<auto, Iter::value_type, Iter::value_type> Pred>
- requires OutputIterator<Iter, Iter::reference>
+ template<ForwardIterator Iter, EquivalenceRelation<auto, Iter::value_type> Pred>
+ requires OutputIterator<Iter, RvalueOf<Iter::reference>::type>
&& CopyConstructible<Pred>
Iter unique(Iter @\farg{first}@, Iter @\farg{last}@,
Pred @\farg{pred}@);
@@ -364,7 +401,7 @@
OutIter unique_copy(InIter @\farg{first}@, InIter @\farg{last}@,
OutIter @\farg{result}@);
template<InputIterator InIter, typename OutIter,
- Predicate<auto, InIter::value_type, InIter::value_type> Pred>
+ EquivalenceRelation<auto, InIter::value_type> Pred>
requires OutputIterator<OutIter, InIter::reference>
&& OutputIterator<OutIter, const InIter::value_type&>
&& CopyAssignable<InIter::value_type>
@@ -375,7 +412,7 @@
OutIter unique_copy(InIter @\farg{first}@, InIter @\farg{last}@,
OutIter @\farg{result}@, Pred @\farg{pred}@);
template<ForwardIterator InIter, OutputIterator<auto, InIter::reference> OutIter,
- Predicate<auto, InIter::value_type, InIter::value_type> Pred>
+ EquivalenceRelation<auto, InIter::value_type> Pred>
requires CopyConstructible<Pred>
OutIter unique_copy(InIter @\farg{first}@, InIter @\farg{last}@,
OutIter @\farg{result}@, Pred @\farg{pred}@);
@@ -394,32 +431,27 @@
OutIter reverse_copy(InIter @\farg{first}@, InIter @\farg{last}@, OutIter @\farg{result}@);
template<ForwardIterator Iter>
- requires HasSwap<Iter::reference, Iter::reference>
- void rotate(Iter @\farg{first}@, Iter @\farg{middle}@,
+ requires ShuffleIterator<Iter>
+ Iter rotate(Iter @\farg{first}@, Iter @\farg{middle}@,
Iter @\farg{last}@);
template<ForwardIterator InIter, OutputIterator<auto, InIter::reference> OutIter>
OutIter rotate_copy(InIter @\farg{first}@, InIter @\farg{middle}@,
InIter @\farg{last}@, OutIter @\farg{result}@);
template<RandomAccessIterator Iter>
- requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
void random_shuffle(Iter @\farg{first}@,
Iter @\farg{last}@);
template<RandomAccessIterator Iter, Callable<auto, Iter::difference_type> Rand>
- requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
&& Convertible<Rand::result_type, Iter::difference_type>
- && CopyConstructible<Rand>
void random_shuffle(Iter @\farg{first}@,
Iter @\farg{last}@,
Rand&& @\farg{rand}@);
- template<class RandomAccessIterator, class UniformRandomNumberGenerator>
- void random_shuffle(RandomAccessIterator @\farg{first}@,
- RandomAccessIterator @\farg{last}@,
- UniformRandomNumberGenerator& @\farg{rand}@);
@\textcolor{black}{// \ref{alg.partitions}, partitions:}@
template<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred>
- requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
&& CopyConstructible<Pred>
Iter partition(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
template<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred>
@@ -469,7 +501,6 @@
requires @\changedCCC{HasAssign<RAIter::reference, InIter::reference>}{ShuffleIterator<RAIter>}@
&& @\changedCCC{Swappable<RAIter::reference>}{OutputIterator<RAIter, InIter::reference>}@
&& HasLess<InIter::value_type, RAIter::value_type>
- && HasLess<RAIter::value_type, InIter::value_type>
&& @\changedCCC{HasLess}{LessThanComparable}@<RAIter::value_type>
RAIter partial_sort_copy(InIter @\farg{first}@, InIter @\farg{last}@,
RAIter @\farg{result_first}@, RAIter @\farg{result_last}@);
@@ -477,7 +508,6 @@
requires @\changedCCC{HasAssign<RAIter::reference, InIter::reference>}{ShuffleIterator<RAIter>}@
&& @\changedCCC{Swappable<RAIter::reference>}{OutputIterator<RAIter, InIter::reference>}@
&& Predicate<Compare, InIter::value_type, RAIter::value_type>
- && Predicate<Compare, RAIter::value_type, InIter::value_type>
&& StrictWeakOrder<Compare, RAIter::value_type>}
@\addedCC{\&\& CopyConstructible<Compare>}@
RAIter partial_sort_copy(InIter @\farg{first}@, InIter @\farg{last}@,
@@ -563,8 +593,6 @@
requires OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter merge(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -574,8 +602,6 @@
requires OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& CopyConstructible<Compare>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter merge(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -598,16 +624,12 @@
template<InputIterator Iter1, InputIterator Iter2>
requires HasLess<Iter1::value_type, Iter2::value_type>
&& HasLess<Iter2::value_type, Iter1::value_type>
- && LessThanComparable<Iter1::value_type>
- && LessThanComparable<Iter2::value_type>
bool includes(Iter1 @\farg{first1}@, Iter1 @\farg{last1}@,
Iter2 @\farg{first2}@, Iter2 @\farg{last2}@);
template<InputIterator Iter1, InputIterator Iter2,
typename Compare>
requires Predicate<Compare, Iter1::value_type, Iter2::value_type>
&& Predicate<Compare, Iter2::value_type, Iter1::value_type>
- && StrictWeakOrder<Compare, Iter1::value_type>
- && StrictWeakOrder<Compare, Iter2::value_type>
bool includes(Iter1 @\farg{first1}@, Iter1 @\farg{last1}@,
Iter2 @\farg{first2}@, Iter2 @\farg{last2}@,
Compare @\farg{comp}@);
@@ -618,8 +640,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
&& HasLess<InIter1::value_type, InIter2::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter set_union(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -629,8 +649,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& Predicate<Compare, InIter1::value_type, InIter2::value_type>
&& Predicate<Compare, InIter2::value_type, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter set_union(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -641,8 +659,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
&& HasLess<InIter1::value_type, InIter2::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter set_intersection(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -652,8 +668,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& Predicate<Compare, InIter1::value_type, InIter2::value_type>
&& Predicate<Compare, InIter2::value_type, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter set_intersection(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -664,8 +678,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
&& HasLess<InIter1::value_type, InIter2::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter set_difference(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -676,8 +688,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& Predicate<Compare, InIter1::value_type, InIter2::value_type>
&& Predicate<Compare, InIter2::value_type, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter set_difference(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -688,8 +698,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
&& HasLess<InIter1::value_type, InIter2::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter set_symmetric_difference(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -699,8 +707,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& Predicate<Compare, InIter1::value_type, InIter2::value_type>
&& Predicate<Compare, InIter2::value_type, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter set_symmetric_difference(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -774,8 +780,8 @@
template<LessThanComparable T, LessThanComparable... Args>
requires SameType<T, Args>...
const T& min(const T& @\farg{a}@, const Args&... @\farg{args}@);
- @\textcolor{black}{template<class T, class U, class... Args>}@
- @\textcolor{black}{const T\& min(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
+ @\removedConcepts{template<class T, class U, class... Args>}@
+ @\removedConcepts{const T\& min(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
template<LessThanComparable T> const T& max(const T& @\farg{a}@, const T& @\farg{b}@);
template<class T, StrictWeakOrder<auto, T> Compare>
@@ -785,8 +791,8 @@
template<LessThanComparable T, LessThanComparable... Args>
requires SameType<T, Args>...
const T& max(const T& @\farg{a}@, const Args&... @\farg{args}@);
- @\textcolor{black}{template<class T, class U, class... Args>}@
- @\textcolor{black}{const T\& max(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
+ @\removedConcepts{template<class T, class U, class... Args>}@
+ @\removedConcepts{const T\& max(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
template<LessThanComparable T> pair<const T&, const T&> minmax(const T& @\farg{a}@, const T& @\farg{b}@);
template<class T, StrictWeakOrder<auto, T> Compare>
@@ -798,8 +804,8 @@
template<LessThanComparable T, LessThanComparable... Args>
requires SameType<T, Args>...
pair<const T&, const T&> minmax(const T& @\farg{a}@, const Args&... @\farg{args}@);
- @\textcolor{black}{template<class T, class U, class... Args>}@
- @\textcolor{black}{pair<const T\&, const T\&> minmax(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
+ @\removedConcepts{template<class T, class U, class... Args>}@
+ @\removedConcepts{pair<const T\&, const T\&> minmax(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
template<ForwardIterator Iter>
requires LessThanComparable<Iter::value_type>
@@ -844,21 +850,21 @@
@\textcolor{black}{// \ref{alg.permutation.generators}, permutations:}@
template<BidirectionalIterator Iter>
- requires HasSwap<Iter::reference, Iter::reference>
- @\textcolor{addclr}{LessThanComparable}@<Iter::value_type>
+ requires ShuffleIterator<Iter>
+ && LessThanComparable<Iter::value_type>
bool next_permutation(Iter @\farg{first}@, Iter @\farg{last}@);
template<BidirectionalIterator Iter,
StrictWeakOrder<auto, Iter::value_type> Compare>
- requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
&& CopyConstructible<Compare>
bool next_permutation(Iter @\farg{first}@, Iter @\farg{last}@, Compare @\farg{comp}@);
template<BidirectionalIterator Iter>
- requires HasSwap<Iter::reference, Iter::reference>
- @\textcolor{addclr}{}@LessThanComparable<Iter::value_type>
+ requires ShuffleIterator<Iter>
+ && LessThanComparable<Iter::value_type>
bool prev_permutation(Iter @\farg{first}@, Iter @\farg{last}@);
template<BidirectionalIterator Iter,
StrictWeakOrder<auto, Iter::value_type> Compare>
- requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
&& CopyConstructible<Compare>
bool prev_permutation(Iter @\farg{first}@, Iter @\farg{last}@, Compare @\farg{comp}@);
}
@@ -1216,8 +1222,7 @@
requires EqualityComparable<Iter::value_type>
Iter adjacent_find(Iter @\farg{first}@, Iter @\farg{last}@);
-template<ForwardIterator Iter,
- Predicate<auto, Iter::value_type, Iter::value_type> Pred>
+template<ForwardIterator Iter, EquivalenceRelation<auto, Iter::value_type> Pred>
requires CopyConstructible<Pred>
Iter adjacent_find(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
\end{itemdecl}\color{black}
@@ -1641,7 +1646,7 @@
\color{addclr}
\begin{itemdecl}
template<class T>
- requires MoveAssignable<T> && MoveConstructible<T> && NothrowDestructible<T>
+ requires MoveAssignable<T> && MoveConstructible<T>
void swap(T& @\farg{a}@, T& @\farg{b}@);
\end{itemdecl}
\color{black}
@@ -1703,12 +1708,18 @@
\index{iter_swap@\tcode{iter_swap}}%
\color{addclr}
\begin{itemdecl}
-template<ForwardIterator Iter1, ForwardIterator Iter2>
+template<Iterator Iter1, Iterator Iter2>
requires HasSwap<Iter1::reference, Iter2::reference>
void iter_swap(Iter1 @\farg{a}@, Iter2 @\farg{b}@);
\end{itemdecl}
\color{black}
+\editorial{We have loosened the requirements on \tcode{iter_swap} from
+ \tcode{ForwardIterator} (required in C++03, which needed true
+ references and copy-constructible/copy-assignable value types) to
+ just \tcode{Iterator}, which represents the minimum requirement for
+ C++0x iterators.}
+
\begin{itemdescr}
\pnum
\effects\
@@ -1804,8 +1815,7 @@
&& OutputIterator<Iter, const T&>
&& HasEqualTo<Iter::value_type, T>
void replace(Iter @\farg{first}@, Iter @\farg{last}@,
- const T& @\farg{old_value}@, const T&
- @\farg{new_value}@);
+ const T& @\farg{old_value}@, const T& @\farg{new_value}@);
template<ForwardIterator Iter, Predicate<auto, Iter::value_type> Pred, class T>
requires OutputIterator<Iter, Iter::reference>
@@ -1843,7 +1853,7 @@
\color{addclr}\begin{itemdecl}
template<InputIterator InIter, typename OutIter, class T>
requires OutputIterator<OutIter, InIter::reference>
- && OutputIterator<Iter, const T&>
+ && OutputIterator<OutIter, const T&>
&& HasEqualTo<InIter::value_type, T>
OutIter replace_copy(InIter @\farg{first}@, InIter @\farg{last}@,
OutIter @\farg{result}@,
@@ -1994,13 +2004,13 @@
\index{remove_if@\tcode{remove_if}}%
\color{addclr}\begin{itemdecl}
template<ForwardIterator Iter, class T>
- requires OutputIterator<Iter, Iter::reference>
+ requires OutputIterator<Iter, RvalueOf<Iter::reference>::type>
&& HasEqualTo<Iter::value_type, T>
Iter remove(Iter @\farg{first}@, Iter @\farg{last}@,
const T& @\farg{value}@);
template<ForwardIterator Iter, Predicate<auto, Iter::value_type> Pred>
- requires OutputIterator<Iter, Iter::reference>
+ requires OutputIterator<Iter, RvalueOf<Iter::reference>::type>
&& CopyConstructible<Pred>
Iter remove_if(Iter @\farg{first}@, Iter @\farg{last}@,
Pred @\farg{pred}@);
@@ -2092,8 +2102,8 @@
&& EqualityComparable<Iter::value_type>
Iter unique(Iter @\farg{first}@, Iter @\farg{last}@);
-template<ForwardIterator Iter, Predicate<auto, Iter::value_type, Iter::value_type> Pred>
- requires OutputIterator<Iter, Iter::reference>
+template<ForwardIterator Iter, EquivalenceRelation<auto, Iter::value_type> Pred>
+ requires OutputIterator<Iter, RvalueOf<Iter::reference>::type>
&& CopyConstructible<Pred>
Iter unique(Iter @\farg{first}@, Iter @\farg{last}@,
Pred @\farg{pred}@);
@@ -2154,7 +2164,7 @@
OutIter @\farg{result}@);
template<InputIterator InIter, typename OutIter,
- Predicate<auto, InIter::value_type, InIter::value_type> Pred>
+ EquivalenceRelation<auto, InIter::value_type> Pred>
requires OutputIterator<OutIter, InIter::reference>
&& OutputIterator<OutIter, const InIter::value_type&>
&& CopyAssignable<InIter::value_type>
@@ -2166,7 +2176,7 @@
OutIter @\farg{result}@, Pred @\farg{pred}@);
template<ForwardIterator InIter, OutputIterator<auto, InIter::reference> OutIter,
- Predicate<auto, InIter::value_type, InIter::value_type> Pred>
+ EquivalenceRelation<auto, InIter::value_type> Pred>
requires CopyConstructible<Pred>
OutIter unique_copy(InIter @\farg{first}@, InIter @\farg{last}@,
OutIter @\farg{result}@);
@@ -2301,8 +2311,8 @@
\index{rotate@\tcode{rotate}}%
\color{addclr}\begin{itemdecl}
template<ForwardIterator Iter>
- requires HasSwap<Iter::reference, Iter::reference>
- void rotate(Iter @\farg{first}@, Iter @\farg{middle}@,
+ requires ShuffleIterator<Iter>
+ Iter rotate(Iter @\farg{first}@, Iter @\farg{middle}@,
Iter @\farg{last}@);
\end{itemdecl}\color{black}
@@ -2317,6 +2327,10 @@
\tcode{\farg{first}\ + (i + (\farg{last}\ - \farg{middle})) \% (\farg{last}\ - \farg{first})}.
\pnum
+\returns\
+\tcode{first + (last - middle)}.
+
+\pnum
\notes\
This is a left rotate.
@@ -2380,28 +2394,18 @@
\index{random_shuffle@\tcode{random_shuffle}}%
\color{addclr}\begin{itemdecl}
template<RandomAccessIterator Iter>
- requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
void random_shuffle(Iter @\farg{first}@,
Iter @\farg{last}@);
template<RandomAccessIterator Iter, Callable<auto, Iter::difference_type> Rand>
- requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
&& Convertible<Rand::result_type, Iter::difference_type>
- && CopyConstructible<Rand>
void random_shuffle(Iter @\farg{first}@,
Iter @\farg{last}@,
Rand&& @\farg{rand}@);
-
-template<class RandomAccessIterator, class UniformRandomNumberGenerator>
- void random_shuffle(RandomAccessIterator @\farg{first}@,
- RandomAccessIterator @\farg{last}@,
- UniformRandomNumberGenerator& @\farg{rand}@);
\end{itemdecl}\color{black}
-\editorial{TODO: We do not yet have the
-\tcode{UniformRandomNumberGenerator} concept, so we leave the third
-\tcode{random_shuffle} without concept constraints for now.}
-
\begin{itemdescr}
\pnum
\effects\
@@ -2448,7 +2452,7 @@
\index{partition@\tcode{partition}}%
\color{addclr}\begin{itemdecl}
@\textcolor{addclr}{}@template<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred>
- @\color{addclr}@requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
&& CopyConstructible<Pred>
Iter partition(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
\end{itemdecl}\color{black}
@@ -2697,7 +2701,6 @@
requires @\changedCCC{HasAssign<RAIter::reference, InIter::reference>}{ShuffleIterator<RAIter>}@
&& @\changedCCC{Swappable<RAIter::reference>}{OutputIterator<RAIter, InIter::reference>}@
&& HasLess<InIter::value_type, RAIter::value_type>
- && HasLess<RAIter::value_type, InIter::value_type>
&& @\changedCCC{HasLess}{LessThanComparable}@<RAIter::value_type>
RAIter partial_sort_copy(InIter @\farg{first}@, InIter @\farg{last}@,
RAIter @\farg{result_first}@, RAIter @\farg{result_last}@);
@@ -2706,7 +2709,6 @@
requires @\changedCCC{HasAssign<RAIter::reference, InIter::reference>}{ShuffleIterator<RAIter>}@
&& @\changedCCC{Swappable<RAIter::reference>}{OutputIterator<RAIter, InIter::reference>}@
&& Predicate<Compare, InIter::value_type, RAIter::value_type>
- && Predicate<Compare, RAIter::value_type, InIter::value_type>
&& StrictWeakOrder<Compare, RAIter::value_type>}
@\addedCC{\&\& CopyConstructible<Compare>}@
RAIter partial_sort_copy(InIter @\farg{first}@, InIter @\farg{last}@,
@@ -3104,8 +3106,6 @@
OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter merge(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -3117,8 +3117,6 @@
OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& CopyConstructible<Compare>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter merge(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -3255,8 +3253,6 @@
template<InputIterator Iter1, InputIterator Iter2>
requires HasLess<Iter1::value_type, Iter2::value_type>
&& HasLess<Iter2::value_type, Iter1::value_type>
- && LessThanComparable<Iter1::value_type>
- && LessThanComparable<Iter2::value_type>
bool includes(Iter1 @\farg{first1}@, Iter1 @\farg{last1}@,
Iter2 @\farg{first2}@, Iter2 @\farg{last2}@);
@@ -3264,8 +3260,6 @@
typename Compare>
requires Predicate<Compare, Iter1::value_type, Iter2::value_type>
&& Predicate<Compare, Iter2::value_type, Iter1::value_type>
- && StrictWeakOrder<Compare, Iter1::value_type>
- && StrictWeakOrder<Compare, Iter2::value_type>
bool includes(Iter1 @\farg{first1}@, Iter1 @\farg{last1}@,
Iter2 @\farg{first2}@, Iter2 @\farg{last2}@,
Compare @\farg{comp}@);
@@ -3296,14 +3290,10 @@
\color{addclr}\begin{itemdecl}
template<InputIterator InIter1, InputIterator InIter2,
typename OutIter>
- requires
-
- OutputIterator<OutIter, InIter1::reference>
+ requires OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
&& HasLess<InIter1::value_type, InIter2::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter set_union(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -3311,13 +3301,10 @@
template<InputIterator InIter1, InputIterator InIter2,
typename OutIter,
CopyConstructible Compare>
- requires
- OutputIterator<OutIter, InIter1::reference>
+ requires OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& Predicate<Compare, InIter1::value_type, InIter2::value_type>
&& Predicate<Compare, InIter2::value_type, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter set_union(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -3357,14 +3344,10 @@
\color{addclr}\begin{itemdecl}
template<InputIterator InIter1, InputIterator InIter2,
typename OutIter>
- requires
-
- OutputIterator<OutIter, InIter1::reference>
+ requires OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
&& HasLess<InIter1::value_type, InIter2::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter set_intersection(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -3372,13 +3355,10 @@
template<InputIterator InIter1, InputIterator InIter2,
typename OutIter,
CopyConstructible Compare>
- requires
- OutputIterator<OutIter, InIter1::reference>
+ requires OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& Predicate<Compare, InIter1::value_type, InIter2::value_type>
&& Predicate<Compare, InIter2::value_type, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter set_intersection(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -3417,14 +3397,10 @@
\color{addclr}\begin{itemdecl}
template<InputIterator InIter1, InputIterator InIter2,
typename OutIter>
- requires
-
- OutputIterator<OutIter, InIter1::reference>
+ requires OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
&& HasLess<InIter1::value_type, InIter2::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter set_difference(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -3432,13 +3408,10 @@
template<InputIterator InIter1, InputIterator InIter2,
typename OutIter,
CopyConstructible Compare>
- requires
- OutputIterator<OutIter, InIter1::reference>
+ requires OutputIterator<OutIter, InIter1::reference>
&& OutputIterator<OutIter, InIter2::reference>
&& Predicate<Compare, InIter1::value_type, InIter2::value_type>
&& Predicate<Compare, InIter2::value_type, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter set_difference(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -3494,8 +3467,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& HasLess<InIter2::value_type, InIter1::value_type>
&& HasLess<InIter1::value_type, InIter2::value_type>
- && LessThanComparable<InIter1::value_type>
- && LessThanComparable<InIter2::value_type>
OutIter set_symmetric_difference(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@);
@@ -3506,8 +3477,6 @@
&& OutputIterator<OutIter, InIter2::reference>
&& Predicate<Compare, InIter1::value_type, InIter2::value_type>
&& Predicate<Compare, InIter2::value_type, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter1::value_type>
- && StrictWeakOrder<Compare, InIter2::value_type>
OutIter set_symmetric_difference(InIter1 @\farg{first1}@, InIter1 @\farg{last1}@,
InIter2 @\farg{first2}@, InIter2 @\farg{last2}@,
OutIter @\farg{result}@, Compare @\farg{comp}@);
@@ -3851,36 +3820,37 @@
\end{itemdescr}
\begin{itemdecl}
-template<class T, class U, class... Args>
- const T& min(const T& @\farg{a}@, const U& @\farg{b}@, const Args&... @\farg{args}@);
+@\removedConcepts{template<class T, class U, class... Args>}@
+ @\removedConcepts{const T\& min(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
\end{itemdecl}
-\editorial{At present, we do not know how to write concept constraints
- for this variant of \mbox{\tcode{min}}, because we cannot directly
- express the idea of splitting \mbox{\tcode{Args}} into its first N-1
- arguments (all of which are the same at \mbox{\tcode{T}}) and its
- Nth argument (the binary predicate). Most likely this is possible
- with what is effectively metaprogramming of the concept system to
- ``walk'' through the arguments, but such an implementation would
- make a poor specification. For now, we leave this version
- unconstrained.}
+\editorial{We have removed this version of the variadic \tcode{min}
+ function because its requirements cannot be specified in any natural
+ way. The fundamental problem is that the parameter pack \tcode{args}
+ is used to contain N-1 arguments followed by the comparison
+ operator, unless \tcode{args} is empty, in which case \tcode{b} is
+ the comparison operator and is unused. Such a specification requires
+ significant metaprogramming that would need to be exposed in the
+ specification itself. The standard library concepts drafting group
+ strongly believes that, in light of concepts, the complexity of this
+ routine far outweighs its benefits.}
\begin{itemdescr}
\pnum
-\requires\
-The types of all arguments except the last one are the same as \tcode{T}.
-The last argument is a binary predicate over \tcode{T}.
+\removedConcepts{\requires
+The types of all arguments except the last one are the same as \mbox{\tcode{T}}.
+The last argument is a binary predicate over \mbox{\tcode{T}}.}
\pnum
-\returns\
+\removedConcepts{\returns
The first element in a partial ordering of all the arguments except
-the last one, where the ordering is defined by the predicate.
+the last one, where the ordering is defined by the predicate.}
\pnum
-\notes\
+\removedConcepts{\notes
Returns the leftmost argument when several arguments are equivalent to
-the first element in the ordering. Returns \farg{a} if
-\tcode{sizeof...(Args)} is 0.
+the first element in the ordering. Returns \mbox{\farg{a}} if
+\mbox{\tcode{sizeof...(Args)}} is 0.}
\end{itemdescr}
\index{max@\tcode{max}}%
@@ -3932,30 +3902,29 @@
\end{itemdescr}
\begin{itemdecl}
-template<class T, class U, class... Args>
- const T& max(const T& @\farg{a}@, const U& @\farg{b}@, const Args&... @\farg{args}@);
+@\removedConcepts{template<class T, class U, class... Args>}@
+ @\removedConcepts{const T\& max(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
\end{itemdecl}
\editorial{As with the corresponding \mbox{\tcode{min}} function, we
- do not know how to write the constraints, so we leave this version
- unconstrained.}
+ have removed this variant of the \mbox{\tcode{max}} function.}
\begin{itemdescr}
\pnum
-\requires\
-The types of all arguments except the last one are the same as \tcode{T}.
-The last argument is a binary predicate over \tcode{T}.
+\removedConcepts{\requires
+The types of all arguments except the last one are the same as \mbox{\tcode{T}}.
+The last argument is a binary predicate over \mbox{\tcode{T}}.}
\pnum
-\returns\
+\removedConcepts{\returns\
The last element in a partial ordering of all the arguments except
-the last one, where the ordering is defined by the predicate.
+the last one, where the ordering is defined by the predicate.}
\pnum
-\notes\
+\removedConcepts{\notes\
Returns the leftmost argument when several arguments are equivalent to
-the last element in the ordering. Returns \farg{a} if
-\tcode{sizeof...(Args)} is 0.
+the last element in the ordering. Returns \mbox{\farg{a}} if
+\mbox{\tcode{sizeof...(Args)}} is 0.}
\end{itemdescr}
\index{minmax@\tcode{minmax}}%
@@ -4032,40 +4001,39 @@
\end{itemdescr}
\begin{itemdecl}
-@\textcolor{black}{template<class T, class U, class... Args>}@
- @\textcolor{black}{pair<const T\&, const T\&> minmax(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
+@\removedConcepts{template<class T, class U, class... Args>}@
+ @\removedConcepts{pair<const T\&, const T\&> minmax(const T\& \mbox{\farg{a}}, const U\& \mbox{\farg{b}}, const Args\&... \mbox{\farg{args}});}@
\end{itemdecl}
\editorial{As with the corresponding \mbox{\tcode{min}} and
- \mbox{\tcode{max}} functions, we
- do not know how to write the constraints, so we leave this version
- unconstrained.}
+ \mbox{\tcode{max}} functions, we have removed this variant of \mbox{\tcode{minmax}}.}
\begin{itemdescr}
\pnum
-\requires\
+\removedConcepts{\requires
The types of all arguments except the last one are the same as
-\tcode{T}. The last argument is a binary predicate over \tcode{T}.
+\mbox{\tcode{T}}. The last argument is a binary predicate over
+\mbox{\tcode{T}}.}
\pnum
-\returns\
-\tcode{pair<const T\&, const T\&>(x, y)}\
-where \tcode{x} is the first element and \tcode{y} the last element in
-a partial ordering of all the arguments defined by the predicate.
+\removedConcepts{\returns\
+\mbox{\tcode{pair<const T\&, const T\&>(x, y)}}
+where \mbox{\tcode{x}} is the first element and \mbox{\tcode{y}} the last element in
+a partial ordering of all the arguments defined by the predicate.}
\pnum
-\notes\
-\tcode{x} is the leftmost argument when several arguments would order
+\removedConcepts{\notes\
+\mbox{\tcode{x}} is the leftmost argument when several arguments would order
equivalent as the first in the ordering.
-\tcode{y} is the rightmost argument when several arguments would order
+\mbox{\tcode{y}} is the rightmost argument when several arguments would order
equivalent as the last in the ordering.
-Returns \tcode{pair<const T\&, const T\&>(a, a)} if
-\tcode{sizeof...(Args)} is 0.
+Returns \mbox{\tcode{pair<const T\&, const T\&>(a, a)}} if
+\mbox{\tcode{sizeof...(Args)}} is 0.}
\pnum
-\complexity\
-At most (3/2)\tcode{sizeof...(Args)} applications of the corresponding
-predicate.
+\removedConcepts{\complexity\
+At most (3/2)\mbox{\tcode{sizeof...(Args)}} applications of the corresponding
+predicate.}
\end{itemdescr}
\index{min_element@\tcode{min_element}}%
@@ -4241,13 +4209,13 @@
\index{next_permutation@\tcode{next_permutation}}%
\color{addclr}\begin{itemdecl}
template<BidirectionalIterator Iter>
- requires HasSwap<Iter::reference, Iter::reference>
- @\textcolor{addclr}{LessThanComparable}@<Iter::value_type>
+ requires ShuffleIterator<Iter>
+ && LessThanComparable<Iter::value_type>
bool next_permutation(Iter @\farg{first}@, Iter @\farg{last}@);
template<BidirectionalIterator Iter,
StrictWeakOrder<auto, Iter::value_type> Compare>
- requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
&& CopyConstructible<Compare>
bool next_permutation(Iter @\farg{first}@, Iter @\farg{last}@, Compare @\farg{comp}@);
\end{itemdecl}\color{black}
@@ -4283,13 +4251,13 @@
\index{prev_permutation@\tcode{prev_permutation}}%
\color{addclr}\begin{itemdecl}
template<BidirectionalIterator Iter>
- requires HasSwap<Iter::reference, Iter::reference>
- @\textcolor{addclr}{}@LessThanComparable<Iter::value_type>
+ requires ShuffleIterator<Iter>
+ && LessThanComparable<Iter::value_type>
bool prev_permutation(Iter @\farg{first}@, Iter @\farg{last}@);
template<BidirectionalIterator Iter,
StrictWeakOrder<auto, Iter::value_type> Compare>
- requires HasSwap<Iter::reference, Iter::reference>
+ requires ShuffleIterator<Iter>
&& CopyConstructible<Compare>
bool prev_permutation(Iter @\farg{first}@, Iter @\farg{last}@, Compare @\farg{comp}@);
\end{itemdecl}\color{black}
@@ -4328,7 +4296,12 @@
\end{paras}
\section*{Acknowledgments}
-Chris Jefferson provided fixes for the \tcode{partial_sort_copy} algorithm.
+Chris Jefferson provided fixes for the \tcode{partial_sort_copy}
+algorithm. Sean Parent described the view of permutation algorithms as
+cycles of data movement, which gave us an implementation-agnostic way
+to determine which mutating algorithms required
+\tcode{ShuffleIterator} and which required \tcode{HasSwap} on the
+iterator's reference types.
\bibliographystyle{plain}
\bibliography{local}
Modified: sandbox/committee/concepts/stdlib/clib-concepts.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-concepts.tex (original)
+++ sandbox/committee/concepts/stdlib/clib-concepts.tex 2008-08-16 13:10:24 EDT (Sat, 16 Aug 2008)
@@ -115,6 +115,11 @@
constructor and copy-assignment operator requirement, respectively,
that accept an \tcode{RvalueOf<T>::type} on the right-hand side, to
account for uses of \tcode{std::move}.
+
+\item Added some introductory text describing the naming conventions
+ used for concepts (\ref{utility.concepts}).
+
+\item Added a new concept \tcode{EquivalenceRelation}.
\end{itemize}
\end{titlepage}
@@ -166,8 +171,18 @@
\color{addclr}
\rSec1[utility.concepts]{Concepts}
-\pnum The \tcode{<concepts>} header describes requirements on template
-arguments used throughout the \Cpp\ Standard Library.
+\pnum
+This subclause describes concepts that specify requirements on
+template arguments used throughout the \Cpp\ Standard
+Library. Concepts whose name is prefixed with \tcode{Has} provide
+detection of a specific syntax (e.g., \tcode{HasConstructor}), but do
+not imply the semantics of the corresponding operation. Concepts whose
+name has the \tcode{able} or \tcode{ible} suffix (e.g.,
+\tcode{Constructible}) require both a specific syntax and semantics of
+the associated operations. These semantic concepts refine the
+corresponding syntax-detection concepts, for example, the
+\tcode{Constructible} concept refines the \tcode{HasConstructor}
+concept.
\synopsis{Header \tcode{<concepts>}\ synopsis}
\begin{codeblock}
@@ -252,6 +267,7 @@
auto concept EqualityComparable<typename T> @\textit{see below}@;
concept TriviallyEqualityComparable<typename T> @\textit{see below}@;
auto concept StrictWeakOrder<typename F, typename T> @\textit{see below}@;
+ auto concept EquivalenceRelation<typename F, typename T> @\textit{see below}@;
// \ref{concept.construct}, construction:
auto concept HasConstructor<typename T, typename... Args> @\textit{see below}@;
@@ -1202,36 +1218,6 @@
is a strict weak ordering relation (\mbox{\ref{alg.sorting}}).}
\end{itemdescr}
-\color{ccadd}
-\begin{itemdecl}
-auto concept StrictWeakOrder<typename F, typename T> : Predicate<F, T, T> {
-
- axiom Irreflexivity(F f, T a) { f(a, a) == false; }
-
- axiom Antisymmetry(F f, T a, T b) {
- if (f(a, b))
- f(b, a) == false;
- }
-
- axiom Transitivity(F f, T a, T b, T c) {
- if (f(a, b) && f(b, c))
- f(a, c) == true;
- }
-
- axiom TransitivityOfEquivalence(F f, T a, T b, T c) {
- if (!f(a, b) && !f(b, a) && !f(b, c) && !f(c, b))
- (!f(a, c) && !f(c, a)) == true;
- }
-}
-\end{itemdecl}
-\color{addclr}
-
-\begin{itemdescr}
-\pnum
-\addedConcepts{\mbox{\reallynote} describes a strict weak ordering
- relation (\mbox{\ref{alg.sorting}}), \mbox{\tcode{F}}, on a type \mbox{\tcode{T}}.}
-\end{itemdescr}
-
\begin{itemdecl}
auto concept EqualityComparable<typename T> : HasEqualTo<T, T> {
bool operator!=(const T& a, const T& b) { return !(a == b); }
@@ -1282,6 +1268,55 @@
defined in namespace \mbox{\tcode{std}}.}
\end{itemdescr}
+\begin{itemdecl}
+auto concept StrictWeakOrder<typename F, typename T> : Predicate<F, T, T> {
+
+ axiom Irreflexivity(F f, T a) { f(a, a) == false; }
+
+ axiom Antisymmetry(F f, T a, T b) {
+ if (f(a, b))
+ f(b, a) == false;
+ }
+
+ axiom Transitivity(F f, T a, T b, T c) {
+ if (f(a, b) && f(b, c))
+ f(a, c) == true;
+ }
+
+ axiom TransitivityOfEquivalence(F f, T a, T b, T c) {
+ if (!f(a, b) && !f(b, a) && !f(b, c) && !f(c, b))
+ (!f(a, c) && !f(c, a)) == true;
+ }
+}
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\addedConcepts{\mbox{\reallynote} describes a strict weak ordering
+ relation (\mbox{\ref{alg.sorting}}), \mbox{\tcode{F}}, on a type \mbox{\tcode{T}}.}
+\end{itemdescr}
+
+\begin{itemdecl}
+auto concept EquivalenceRelation<typename F, typename T> : Predicate<F, T, T> {
+ axiom Reflexivity(F f, T a) { f(a, a) == true; }
+
+ axiom Symmetry(F f, T a, T b) {
+ if (f(a, b))
+ f(b, a) == true;
+ }
+
+ axiom Transitivity(F f, T a, T b, T c) {
+ if (f(a, b) && f(b, c))
+ f(a, c) == true;
+ }
+}
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\addedConcepts{\mbox{\reallynote} describes an equivalence relation, \mbox{\tcode{F}}, on a type \mbox{\tcode{T}}.}
+\end{itemdescr}
+
\rSec2[concept.construct]{Construction}
\begin{itemdecl}
auto concept HasConstructor<typename T, typename... Args> {
Modified: sandbox/committee/concepts/stdlib/clib-containers.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-containers.tex (original)
+++ sandbox/committee/concepts/stdlib/clib-containers.tex 2008-08-16 13:10:24 EDT (Sat, 16 Aug 2008)
@@ -81,6 +81,8 @@
\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}.
\end{itemize}
\end{titlepage}
@@ -2225,8 +2227,8 @@
template <@\changedConcepts{class}{Predicate<auto, T>}@ Pred@\removedConcepts{icate}@> void remove_if(Pred@\removedConcepts{icate}@ pred);
@\addedConcepts{requires EqualityComparable<T>}@ void unique();
- template <@\changedConcepts{class}{Predicate<auto, T, T>}@ BinaryPredicate>
- void unique(BinaryPredicate binary_pred);
+ template <@\changedConcepts{class}{EquivalenceRelation<auto, T>}@ BinaryPredicate>
+ void unique(BinaryPredicate binary_pred);
@\addedConcepts{requires LessThanComparable<T>}@ void merge(forward_list<T,Alloc@\removedConcepts{ator}@>&& x);
template <@\removedCC{class}\changedCCC{Predicate<auto, T, T>}{StrictWeakOrder<auto, T>}@ Compare>
@@ -2573,7 +2575,7 @@
\begin{itemdecl}
@\addedConcepts{requires EqualityComparable<T>}@ void unique();
-template <@\changedConcepts{class}{Predicate<auto, T, T>}@ BinaryPredicate>
+template <@\changedConcepts{class}{EquivalenceRelation<auto, T>}@ BinaryPredicate>
void unique(BinaryPredicate pred);
\end{itemdecl}
@@ -2799,7 +2801,7 @@
template <@\changedConcepts{class}{Predicate<auto, T>}@ Pred@\removedConcepts{icate}@> void remove_if(Pred@\removedConcepts{icate}@ @\farg{pred}@);
@\addedConcepts{requires EqualityComparable<T>}@ void unique();
- template <@\changedConcepts{class}{Predicate<auto, T, T>}@ BinaryPredicate>
+ template <@\changedConcepts{class}{EquivalenceRelation<auto, T>}@ BinaryPredicate>
void unique(BinaryPredicate @\farg{binary_pred}@);
@\addedConcepts{requires LessThanComparable<T>}@ void merge(list<T,Alloc@\removedConcepts{ator}@>&& @\farg{x}@);
@@ -3245,7 +3247,7 @@
\index{unique@\tcode{unique}!\tcode{list}}%
\begin{itemdecl}
@\addedConcepts{requires EqualityComparable<T>}@ void unique();
-template <@\changedConcepts{class}{Predicate<auto, T, T>}@ BinaryPredicate> void unique(BinaryPredicate @\farg{binary_pred}@);
+template <@\changedConcepts{class}{EquivalenceRelation<auto, T>}@ BinaryPredicate> void unique(BinaryPredicate @\farg{binary_pred}@);
\end{itemdecl}
\begin{itemdescr}
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