Boost logo

Boost-Commit :

Date view Thread view Subject view Author view

From: chris_at_[hidden]
Date: 2008-04-30 12:40:41

Author: chrisj
Date: 2008-04-30 12:40:40 EDT (Wed, 30 Apr 2008)
New Revision: 44937
URL: http://svn.boost.org/trac/boost/changeset/44937

Log:
Use 'SwappableIterator' much more in clib-algorithms.tex, and add issue 29 documenting the change
Added:
   sandbox/committee/concepts/issues/issues/issue29.xml (contents, props changed)
Text files modified:
   sandbox/committee/concepts/stdlib/clib-algorithms.tex | 124 ++++++++++++++++++++++++---------------
   1 files changed, 76 insertions(+), 48 deletions(-)

Added: sandbox/committee/concepts/issues/issues/issue29.xml
==============================================================================
--- (empty file)
+++ sandbox/committee/concepts/issues/issues/issue29.xml 2008-04-30 12:40:40 EDT (Wed, 30 Apr 2008)
@@ -0,0 +1,37 @@
+<?xml version='1.0' encoding='iso-8859-1' standalone='no'?>
+<!DOCTYPE issue SYSTEM "lwg-issue.dtd" [
+ <!ENTITY nbsp "&#160;">
+] >
+
+<issue num="29" status="New">
+<title>Concepts on mutating algorithms are confusing</title>
+<section><sref ref="[algorithms]"/></section>
+<submitter>Christopher Jefferson</submitter>
+<date>29 Apr 2008</date>
+
+<discussion>
+ <p>The concepts on the mutating algorithms are confusing and leak too much about the implementation. For example <tt>push_heap</tt> requires <tt>MoveConstructible</tt> and <tt>MoveAssignable</tt>, but <tt>pop_heap</tt> also requires <tt>Swappable</tt>. These arise from the functions used in practical implementations, but mean using them in constrained templates requires looking up the exact concepts required. At the cost of a slightly less efficient implementation, all of the following algorithms can be implemented using just <tt>IteratorSwappable</tt>, along with a predicate or <tt>LessThanComparable</tt>:
+ </p>
+
+ <p>
+ <tt>reverse, rotate, random_shuffle, partition, stable_partition, sort, stable_sort, partial_sort, nth_element, inplace_merge, push_heap, pop_heap, make_heap, sort_heap, next_permutation, prev_permutation</tt>
+</p>
+
+
+<p>Further, <tt>partial_sort_copy</tt> can be implemented requiring only <tt>SwappableIterator</tt> on the result array. All of these changes have been tested with a modification of libstdc++. Of course implementations can implement optimised versions of these methods when <tt>MoveConstructable</tt> and <tt>MoveAssignable</tt> are available.
+</p>
+</discussion>
+
+<resolution>
+ <p>
+ Replace any references to <tt>MoveConstructible, MoveAssignable</tt> and <tt>Swappable</tt> in the requires section of <tt>reverse, rotate, random_shuffle, partition, stable_partition, sort, stable_sort, partial_sort, nth_element, inplace_merge, push_heap, pop_heap, make_heap, sort_heap, next_permutation, prev_permutation</tt> with <tt>SwappableIterator</tt>, and remove all references to <tt>SameType</tt>. Further, replace the concepts:
+ </p>
+
+ <pre>
+ <tt>SameType&lt;RAIter::value_type&amp;, RAIter::reference&gt; &amp;&amp; Swappable&lt;RAIter::value_type&gt; &amp;&amp;
+ MoveConstructible&lt;RAIter::value_type&gt; &amp;&amp; MoveAssignable&lt;RAIter::value_type&gt; &amp;&amp;</tt>
+ </pre>
+
+ <p> with <tt>SwappableIterator&lt;RAIter&gt;</tt> in both copies if <tt>partial_sort_copy</tt></p>
+</resolution>
+</issue>

Modified: sandbox/committee/concepts/stdlib/clib-algorithms.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-algorithms.tex (original)
+++ sandbox/committee/concepts/stdlib/clib-algorithms.tex 2008-04-30 12:40:40 EDT (Wed, 30 Apr 2008)
@@ -334,14 +334,16 @@
                         OutIter @\farg{result}@, Pred @\farg{pred}@);
 
   template<MutableBidirectionalIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void reverse(Iter @\farg{first}@, Iter @\farg{last}@);
   template<BidirectionalIterator InIter, OutputIterator<auto, InIter::value_type> OutIter>
     OutIter reverse_copy(InIter @\farg{first}@,
                          InIter @\farg{last}@, OutIter @\farg{result}@);
 
   template<ForwardIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void rotate(Iter @\farg{first}@, Iter @\farg{middle}@,
                 Iter @\farg{last}@);
   template<ForwardIterator InIter, OutputIterator<auto, InIter::value_type> OutIter>
@@ -349,12 +351,13 @@
                         InIter @\farg{last}@, OutIter @\farg{result}@);
 
   template<MutableRandomAccessIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void random_shuffle(Iter @\farg{first}@,
                         Iter @\farg{last}@);
   template<MutableRandomAccessIterator Iter, Callable<auto, Iter::difference_type> Rand>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- Convertible<Rand::result_type, Iter::difference_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\& }@
+ @\addedCC{SwappableIterator<Iter> \&\&}@ Convertible<Rand::result_type, Iter::difference_type>
     void random_shuffle(Iter @\farg{first}@,
                         Iter @\farg{last}@,
                         Rand& @\farg{rand}@);
@@ -365,58 +368,67 @@
 
   @\textcolor{black}{// \ref{alg.partitions}, partitions:}@
   template<BidirectionalIterator Iter, Predicate<auto, Iter::reference> Pred>
- @\color{addclr}@requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type>
+ @\color{addclr}@requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     Iter partition(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
   template<MutableBidirectionalIterator Iter, Predicate<auto Iter::reference> Pred>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     Iter stable_partition(Iter @\farg{first}@, Iter @\farg{last}@, Pred @\farg{pred}@);
 
   @\textcolor{black}{// \ref{alg.sorting}, sorting and related operations:}@
   @\textcolor{black}{// \ref{alg.sort}, sorting:}@
   template<MutableRandomAccessIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<Iter> \&\&}@
              LessThanComparable<Iter::value_type>
     void sort(Iter @\farg{first}@, Iter @\farg{last}@);
   template<MutableRandomAccessIterator Iter,
            Predicate<auto, Iter::value_type, Iter::value_type> Compare>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void sort(Iter @\farg{first}@, Iter @\farg{last}@,
               Compare @\farg{comp}@);
 
   template<MutableRandomAccessIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<Iter> \&\&}@
              LessThanComparable<Iter::value_type>
     void stable_sort(Iter @\farg{first}@, Iter @\farg{last}@);
   template<MutableRandomAccessIterator Iter,
            Predicate<auto, Iter::value_type, Iter::value_type> Compare>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void stable_sort(Iter @\farg{first}@, Iter @\farg{last}@,
                      Compare @\farg{comp}@);
 
   template<MutableRandomAccessIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> @\addedCC{\&\&}@
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@ @\addedCC{\&\&}@
              @\addedCC{LessThanComparable<Iter::value_type>}@
     void partial_sort(Iter @\farg{first}@,
                       Iter @\farg{middle}@,
                       Iter @\farg{last}@);
   template<MutableRandomAccessIterator Iter,
            Predicate<auto, Iter::value_type, Iter::value_type> Compare>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void partial_sort(Iter @\farg{first}@,
                       Iter @\farg{middle}@,
                       Iter @\farg{last}@,
                       Compare @\farg{comp}@);
   template<InputIterator InIter, MutableRandomAccessIterator RAIter>
     requires CopyAssignable<RAIter::reference, InIter::value_type> &&
- SameType<RAIter::value_type&, RAIter::reference> && Swappable<RAIter::value_type> &&
- MoveConstructible<RAIter::value_type> && MoveAssignable<RAIter::value_type> &&
+ @\removedCC{SameType<RAIter::value_type\&, RAIter::reference> \&\& Swappable<RAIter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<RAIter::value_type> \&\& MoveAssignable<RAIter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<RAIter> \&\&}@
              HasLess<InIter::value_type, RAIter::value_type> &&
              HasLess<RAIter::value_type, InIter::value_type> &&
              HasLess<RAIter::value_type>
@@ -424,8 +436,9 @@
                              RAIter @\farg{result_first}@, RAIter @\farg{result_last}@);
   template<InputIterator InIter, MutableRandomAccessIterator RAIter, class Compare>
     requires CopyAssignable<RAIter::reference, InIter::value_type> &&
- SameType<RAIter::value_type&, RAIter::reference> && Swappable<RAIter::value_type> &&
- MoveConstructible<RAIter::value_type> && MoveAssignable<RAIter::value_type> &&
+ @\removedCC{SameType<RAIter::value_type\&, RAIter::reference> \&\& Swappable<RAIter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<RAIter::value_type> \&\& MoveAssignable<RAIter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<RAIter> \&\&}@
              Predicate<Compare, InIter::value_type, RAIter::value_type> &&
              Predicate<Compare, RAIter::value_type, InIter::value_type> &&
              Predicate<Compare, RAIter::value_type>
@@ -447,15 +460,17 @@
                          Compare @\farg{comp}@);
 
   template<MutableRandomAccessIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<Iter> \&\&}@
              LessThanComparable<Iter::value_type>
     void nth_element(Iter @\farg{first}@, Iter @\farg{nth}@,
                      Iter @\farg{last}@);
   template<MutableRandomAccessIterator Iter,
            Predicate<auto, Iter::value_type, Iter::value_type> Compare>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void nth_element(Iter @\farg{first}@, Iter @\farg{nth}@,
                      Iter @\farg{last}@, Compare @\farg{comp}@);
 
@@ -518,16 +533,18 @@
                   OutIter @\farg{result}@, Compare @\farg{comp}@);
 
   template<MutableBidirectionalIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<Iter> \&\&}@
              LessThanComparable<Iter::value_type>
     void inplace_merge(Iter @\farg{first}@,
                        Iter @\farg{middle}@,
                        Iter @\farg{last}@);
   template<MutableBidirectionalIterator Iter,
            Predicate<auto, Iter::value_type, Iter::value_type> Compare>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
- MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void inplace_merge(Iter @\farg{first}@,
                        Iter @\farg{middle}@,
                        Iter @\farg{last}@, Compare @\farg{comp}@);
@@ -606,44 +623,51 @@
 
   @\textcolor{black}{// \ref{alg.heap.operations}, heap operations:}@
   template<MutableRandomAccessIterator Iter>
- requires MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
+ requires @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<Iter> \&\&}@
              LessThanComparable<Iter::value_type>
     void push_heap(Iter @\farg{first}@, Iter @\farg{last}@);
   template<MutableRandomAccessIterator Iter,
            Predicate<auto, Iter::value_type, Iter::value_type> Compare>
- requires MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type>
+ requires @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void push_heap(Iter @\farg{first}@, Iter @\farg{last}@,
                    Compare @\farg{comp}@);
 
   template<MutableRandomAccessIterator Iter>
- requires MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
- Swappable<Iter::value_type> && LessThanComparable<Iter::value_type>
+ requires @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type> \&\&}@
+ @\removedCC{Swappable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@ && LessThanComparable<Iter::value_type>
     void pop_heap(Iter @\farg{first}@, Iter @\farg{last}@);
   template<MutableRandomAccessIterator Iter,
            Predicate<auto, Iter::value_type, Iter::value_type> Compare>
- requires MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
- Swappable<Iter::value_type>
+ requires @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type> \&\&}@
+ @\removedCC{Swappable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void pop_heap(Iter @\farg{first}@, Iter @\farg{last}@,
                   Compare @\farg{comp}@);
 
   template<MutableRandomAccessIterator Iter>
- requires MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
+ requires @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<Iter> \&\&}@
              LessThanComparable<Iter::value_type>
     void make_heap(Iter @\farg{first}@, Iter @\farg{last}@);
   template<MutableRandomAccessIterator Iter,
            Predicate<auto, Iter::value_type, Iter::value_type> Compare>
- requires MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type>
+ requires @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void make_heap(Iter @\farg{first}@, Iter @\farg{last}@,
                    Compare @\farg{comp}@);
 
   template<MutableRandomAccessIterator Iter>
- requires MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
- Swappable<Iter::value_type> && LessThanComparable<Iter::value_type>
+ requires @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type> \&\&}@
+ @\removedCC{Swappable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@ && LessThanComparable<Iter::value_type>
     void sort_heap(Iter @\farg{first}@, Iter @\farg{last}@);
   template<MutableRandomAccessIterator Iter,
            Predicate<auto, Iter::value_type, Iter::value_type> Compare>
- requires MoveConstructible<Iter::value_type> && MoveAssignable<Iter::value_type> &&
- Swappable<Iter::value_type>
+ requires @\removedCC{MoveConstructible<Iter::value_type> \&\& MoveAssignable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     void sort_heap(Iter @\farg{first}@, Iter @\farg{last}@,
                    Compare @\farg{comp}@);
 
@@ -730,20 +754,24 @@
 
   @\textcolor{black}{// \ref{alg.permutation.generators}, permutations:}@
   template<MutableBidirectionalIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<Iter>}@
              @\textcolor{addclr}{LessThanComparable}@<Iter::reference>
     bool next_permutation(Iter @\farg{first}@, Iter @\farg{last}@);
   template<MutableBidirectionalIterator Iter,
            Predicate<auto, Iter::reference, Iter::reference> Compare>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     @\textcolor{addclr}{}@bool next_permutation(Iter @\farg{first}@, Iter @\farg{last}@, Compare @\farg{comp}@);
   template<MutableBidirectionalIterator Iter>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type> &&
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type> \&\&}@
+ @\addedCC{SwappableIterator<Iter>}@
              @\textcolor{addclr}{}@LessThanComparable<Iter::reference>
     bool prev_permutation(Iter @\farg{first}@, Iter @\farg{last}@);
   template<MutableBidirectionalIterator Iter,
            Predicate<auto, Iter::reference, Iter::reference> Compare>
- requires SameType<Iter::value_type&, Iter::reference> && Swappable<Iter::value_type>
+ requires @\removedCC{SameType<Iter::value_type\&, Iter::reference> \&\& Swappable<Iter::value_type>}@
+ @\addedCC{SwappableIterator<Iter>}@
     bool prev_permutation(Iter @\farg{first}@, Iter @\farg{last}@, Compare @\farg{comp}@);
 }
 \end{codeblock}

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